[자료구조] 연결리스트(Linked List) - C언어

★ 연결리스트 : Data와 Link로 구성된 Node들을 순차적으로 연결시킨 자료구조

 

 - 장점

 1) 노드 추가/삭제 시 추가연산 불필요

 2) 최대 노드 갯수 지정 불필요->메모리 효율성 좋음 (배열리스트는 리스트 생성 시에 최대 원소 갯수를 지정해야 함)

 - 단점

 1) 특정 노드 탐색이 어려움 -> 원하는 노드를 찾을 때까지 포인터로 노드를 탐색해야하기 때문 

    (배열리스트는 인덱스로 접근이 가능하므로 한번에 탐색 가능)

 

<연결리스트 자료>

 

1. 이중연결리스트 노드 구조

- 저장하려는 Data와, 이전 노드를 가리키는 포인터 Left link, 다음 노드를 가리키는 포인터 Right link로 구성된다.

 

typedef struct __Node
{
     void *data;
     Node *llink;
     Node *rlink;
} Node;

 

2. 이중연결리스트 구조

- Head, Tail : 가장 첫 노드를 Head Node, 마지막 노드를 Tail Node로 지정한다. Head Node의 Left Link와 Tail Node의 Right Link는 자기 자신을 가리킨다.

- length : Head와 Tail Node를 제외한 Node의 총 갯수 (처음 리스트 생성 시 length = 0)

- datasize : Data 자료형의 크기

- current : 현재 가리키고 있는 Node 포인터. (현재 가리키고 있는 노드를 바로 찾기 위해 추가함)

typedef struct __List
{
     Node *head;
     Node *tail;
     int length;            // Node의 갯수
     int datasize;          // Data 자료형의 크기  
     Node *current;      // 현재 가리키고 있는 Node 포인터
} List; 

 

※ GitHub : https://github.com/waves123/Doubly-Linked-List

 

 

자료구조 더보기

2017/07/23 - [자료구조] - [자료구조] 배열로 구현한 원형 큐(Circular Queue) - C/C++

2017/07/20 - [자료구조] - [자료구조] 연결리스트로 구현한 큐(Linked Queue) - C/C++

2017/07/15 - [자료구조] - [자료구조] 스택(Stack) - C/C++

2017/07/02 - [자료구조] - [자료구조] 연결리스트(Linked List) - C언어