[자료구조-리스트] 1. 링크드 리스트_개념

# 리스트 특징

- 배열과 달리 유연하게 크기를 바꿀 수 있는 자료 구조

- 리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다

@ 링크드 리스트

 - 링크드 리스는 리스트를 구현하는 여러 가지 기법 중에서도 가장 간단한 방법으로 꼽히는 자료구조입니다.

 # 노드(Node) : 리스트 내의 각요소

 - 노드를 연결해서 만드는 리스트를 링크드 리스트라고 합니다.

 # 노드 구성

데이터	포인터 (다음 노드)

- 데이터와 포인터로 이루어진 노드들을 연결시켜놓으면 링크드 리스트가 됩니다.

- 첫번째 노드를 헤드라하고 마지막 노드를 테일이라고 합니다.

# C언어로 표현하는 링크드 리스트의 노드

- 링크드 리스트의 노드는 C언어로 표현하면 다음과 같은 구조체로 나타낼 수 있습니다.

- 노드 구조체 방식 1[정의]

 struct Node  
 {  
      int Data;  
      struct Node* NextNode;  
 }  

- 노드 구조체 방식 1[선언]

 struct Node MyNode;  

- 노드 구조체 방식 2 [정의]

 typeof struct tagNode  
 {  
      int Data;  
      struct tagNode* NextNode;  
 } Node;  

- 노드 구조체 방식 2 [선언]

 Node MyNode;  

# 링크드 리스트의 주요 연산

- 노드 생성/소멸
- 노드 추가
- 노드 탐색
- 노드 삭제
- 노드 삽입

# 링크드 리스트 단점

- 다음 노드를 가리키려는 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 필요합니다.
- 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도도 느립니다.

# 링크드 리스트 장점

- 새로운 노드의 추가/삽입/삭제가 쉽고 빠릅니다. 배열은 요소를 삽입하거나 제거하기가 어렵습니다.
- 현재 노드의 다음 노드를 얻어오는 연산에 대해서는 비용이 발생하지 않습니다.