리스트(List)

배열을 사용한 리스트의 문제점

1. 고정된 크기에 따른 메모리 사용의 비효율성

2. 각 원소의 인접한 메모리 사용에 따른 삽입 및 삭제 연산의 비효율성 문제

3. 정해진 리스트의 크기를 동적으로 증가시킬 수 없다는 점

 

위에서 언급한 배열이 갖는 문제점들은 연결 리스트(Linked List)에 의해 해결 될 수 있다.

 

연결리스트에서 각 원소들은 배열에서와는 다르게 메모리 상에서 서로 인접해 있거나 일정한 거리만큼 떨어져 있을 필요가 없다.

또, 연결 리스트에서는 각 원소의 물리적 순서는 의미가 없다.

 

연결리스트에서 각원소는 반드시 값(Value, data)과 다음 원소에 해당하는 위치를 가리키는 링크(link)의 쌍으로 표현된다.

이렇게 하나의 원소를 표현하기 위한 단위를 노드(node)라고 한다.

 

노드는 구조체를 통해 구현 가능하다.

데이터 영역은 다시 여러개의 필드로 확장 될 수 있으며, link 필드는 포인터에 의해 구현 가능하다.

typedef struct node *node_ptr; typedef struct node {     char data[8];        /* data field1 */     int value;              /* data field2 */     node_ptr link;        /* link field */ };

 

연결 리스트에서 하나의 원소를 표현하기 위한 노드는 필요에 따라 동적으로 만들수 있으며,  (allocation)

필요 없게 되면 시스템에게 해당 메모리 영역을 반환하기 위해 해제할 수 있다. (release) 

node_ptr n; n = (node_ptr)malloc(sizeof(node_ptr);     /* allocation, 할당 */    : free(n);                                               /* release, 해제 */

 

연결리스트는 사용되는 링크의 성질에따라

1. 단순 연결 리스트(Simply linked list)

2. 이중 연결 리스트(Doubly linked list)