연결 리스트( Linked List )

연결 리스트는 추상 자료형인 리스트를 구현한 자료 구조이다.

 

1. 특징

 

- 각 원소는 순서를 가지지만 배열과는 다르게 연속적인 메모리 공간에서 관리되는 것은 아니다.

- 특정 원소에 접근하기 위해 순차 탐색을 해야 한다.

- 연속적으로 관리되는 제약이 없기 때문에 리스트 크기를 동적으로 변경 가능하다.

- 삽입, 삭제 연산이 배열보다 유리하다.

 

2. 종류

 

- 단일 연결 리스트(Singly Linked List) : 다음 노드에 대한 참조만을 가지는 형태

< Singly Linked List >

 

- 이중 연결 리스트(Doubly Linked List) : 이전 노드와 다음 노드에 대한 참조를 함께 가지는 형태

< Doubly Linked List >

 

- 원형 연결 리스트(Circular Linked List) : 마지막 노드가 첫 번째 노드에 대한 참조를 가지는 형태

< Circular Linked List >

 

3. 구조체

: 연결 리스트는 노드라고 하는 구조체를 정의하여 원소로 사용한다.

 

struct Node {

    data_t data;    // 실 데이터

    struct Node *pNext;    // 다음 노드를 가리키는 포인터

    // struct Node *pPrevious;

    // 이전 노드를 가리키는 포인터( 이중 연결 리스트 )

};