[자료 구조] 연결 리스트(Linked list)

리스트(List)란?

---

1. 데이터를 순서대로 나열한 자료구조이다.
2. 선형 구조를 갖는 리스트에는 선형 리스트(linear list)와 연결 리스트(linked list)가 있다.
3. 리스트에 있는 개별 요소를 노드(node)라고 한다. 노드의 구성 요소는 데이터와 다음 노드를 가리키는 포인터이다. 

 

선형 리스트(Linear List)

데이터가 배열처럼 연속하는 메모리 공간에 저장되어 순서를 갖는다.

 

연결 리스트(Linked List)

https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2013/03/Linkedlist.png

데이터가 메모리 공간에 연속적으로 저장되어있지 않더라도 각각의 데이터안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결(linked)된다.

연결 리스트의 구성 요소

• 머리 노드(head node): 리스트의 처음에 있는 노드
• 꼬리 노드(tail node): 리스트의 끝에 있는 노드
• 앞쪽 노드(predecessor node): 하나의 노드를 기준으로 바로 앞쪽에 있는 노드
• 다음 노드(successor node): 하나의 노드를 기준으로 바로 뒤쪽에 있는 노드

포인터로 연결 리스트 구현

• 노드의 삽입, 삭제를 데이터 이동없이 수행한다는 장점이 있지만, 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 확보하고 해제하는 과정이 필요하다.

 

배열 커서로 연결 리스트 구현

• 프로그램 실행 중에 데이터 수가 크게 바뀌지 않는 경우, 또는 데이터 수의 최댓값을 미리 알 수 있는 경우에 배열을 사용해 연결 리스트를 효율적으로 운용할 수 있다.
• 다음 노드를 가리키는 뒤쪽 포인터는 다음 노드에 대한 포인터가 아니라 다음 노드가 들어있는 배열 요소의 인덱스(커서, cursor)이다.
• 노드를 삽입, 삭제할 때 요소를 옮길 필요가 없다.

 

프리 연결 리스트(Free Linked List)

1. 삭제한 여러 레코드를 관리(할당되지 않은 메모리의 영역을 관리)하기 위해 그 순서를 넣어두는 연결리스트이다.
2. 연결 리스트에서 노드가 삭제되면, 배열에는 빈 레코드가 생긴다. 따라서 프리 리스트를 사용하여 메모리 낭비를 방지할 수 있다.
3. 즉 삭제된 노드만 따로 모아서 관리하는 연결 리스트이다. 노드 삽입시, 프리 리스트를 먼저 확인하고 프리 리스트가 비어있지 않다면 프리 리스트의 머리 노드(head node)에 레코드를 저장한다. 프리 리스트가 비어있다면 배열 꼬리쪽의 새 레코드에 삽입한다. 

 

원형 연결 리스트(Circular Syngly Linked List)

https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglyLinkedList.png

1. 꼬리 노드가 머리 노드를 가리키는 연결 리스트이다.
2. 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조이다.
3. 꼬리 노드의 다음 노드를 가리키는 포인터가 null이 아니라 머리 노드의 포인터이다.

 

이중 연결 리스트(Doubly Linked List)

https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/03/DLL1.png

1. 연결 리스트의 단점은, 다음 노드는 찾기 쉽지만 앞쪽 노드는 찾기 어렵다는 점이다.
2. 이중 연결 리스트는 이러한 단점을 개선하여 앞쪽 노드를 쉽게 찾을 수 있는 자료구조이다.
3. 각 노드에는 다음 노드에 대한 포인터와 앞쪽 노드에 대한 포인터가 주어진다.

이중 연결 리스트의 노드 구성

data: 데이터(데이터 참조: 형(type)은 E)
prev: 앞쪽 포인터(앞쪽 노드 참조: 형(type)은 Node<E>)
next: 뒤쪽 포인터(뒤쪽 노드 참조: 형(type)은 Node<E>)

 

원형 이중 연결 리스트(Circular Doubly Linked List)

https://media.geeksforgeeks.org/wp-content/uploads/Delete_first_node.png

1. 원형 이중 연결 리스트는 원형 리스트와 이중 연결 리스트를 조합한 자료구조이다.
2. 리스트의 머리에 더미노드(dummy node)가 위치한다. 더미 노드는 노드의 삽입과 삭제를 원활하게 처리하기 위해 리스트의 머리에 계속 존재한다.