연결 리스트

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조이다.

연결 리스트(linked list)는 각 데이터를 포인터로 연결하여 관리하는 자료구조이다.

연결 리스트에서 각각의 원소를 노드라고 한다.

노드가 갖고 있는 것은 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터이다.

맨 앞에 있는 노드를 머리 노드(head node), 맨 끝에 있는 노드를 꼬리 노드(tail node)라고 한다.

각 노드에서 바로 앞에 있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 뒤쪽 노드(successor node)라고 한다.

배열의 각 원소하는 순서대로 데이터가 저장되어 있다.

필요한 뒤쪽 노드 꺼내기는 인덱스 값이 1만큼 큰 원소에 접근하여 얻을 수 있다.

포인터를 이용한 연결 리스트

데이터를 삽입 및 삭제함에 따라 데이터를 옮겨야 하므로 효율적이지 않다.

연결 리스트에 데이터를 삽입할 때 노드용 인스턴스를 생성하고, 데이터를 삭제할 때 노드용 인스턴스를 없애면 데이터를 옮기는 문제를 해결할 수 있다.

커서를 이용한 연결 리스트

포인터를 이용한 연결 리스트는 노드를 삽입 및 삭제할 때마다 내부에서 노드용 인스턴스를 생성하고 소멸한다.

노드용 인스턴스를 생성하고 소멸할 때마다 메모리를 확보하고 해제한다.

프로그램을 실행하면서 데이터 개수가 크게 변하지 않거나 데이터 최대 개수를 예측할 수 있는 경우라면 배열 안의 원소를 사용하여 효율적으로 운용할 수 있다.

데이터 다음에 위치한 뒤쪽 포인터는 뒤쪽 노드가 저장되는 원소의 인덱스이다.

int형 정숫값인 인덱스로 나타낸 포인터를 커서(cursor)라 부른다.

커서를 이용한 연결 리스트는 노드의 삽입과 삭제에 따른 원소의 이동이 처음부터 불필요하다는 점에서 포인터를 이용한 연결 리스트와 다르다.

프리 리스트

프리 리스트(free list)는 삭제된 레코드 그룹을 관리할 때 사용하는 자료구조이다.

원형 이중 연결 리스트

원형 리스트(circular list)는 연결 리스트의 꼬리 노드(F)가 다시 머리 노드(A)를 가리키는 형태이다.

원형 리스트가 연결 리스트와 다른 점은 꼬리 노드(F)의 뒤쪽 포인터가 None이 아니라 머리 노드의 포인터값이 된다는 것이다.

이중 연결 리스트

연결 리스트의 가장 큰 단점은 뒤쪽 노드를 찾기 쉬운 반면 앞쪽 노드를 찾기 어렵다는 것이다.

이러한 단점을 개선한 리스트 구조가 이중 연결 리스트다.

이중 연결 리스트(double linked list)는 각 노드에는 뒤쪽 노드에 대한 포인터 뿐만 아니라 앞쪽 노드에 대한 포인터가 주어진 구조이다.

이중 연결 리스트의 노드는 데이터 data, 앞쪽 노드 prev, 뒤쪽 노드 next로 이루어진다.

원형 이중 연결 리스트

원형 이중 연결 리스트(circular doubly linked list)는 원형 리스트와 이중 연결 리스트를 결합한 자료구조다.