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

연결 리스트란?

배열과의 비교

• 연결리스트는 배열과 마찬가지로 선형적인 자료 구조이다. 
• 하지만 연속된 메모리 공간에 구성 요소들이 할당되어 있는 배열과 달리, 연결리스트는 각 요소가 임의의 공간에 분리되어 존재한다. 
• 연결리스트의 각 노드(node)는 다음 노드를 가리키는 포인터(pointer)를 가지고 있다.
• 따라서, 각 노드에 대한 직접적인 접근은 불가능하다.

Linked List

연결 리스트의 효용

• 동적인 자료구조 - 요소의 삽입 및 삭제에 따라 자료의 크기를 동적으로 관리할 수 있다. 
• 효율적인 삽입/삭제 -  요소의 삽입 및 삭제 시, 배열에서와 같이 따라 다른 요소들의 위치를 이동시킬 필요 없이 요소들 간의 연결 정보를 업데이트 해주는 것만으로 해당 작업을 수행할 수 있다.
• 효율적인 메모리 사용  - 자료구조의 크기가 동적으로 관리되므로 낭비되는 메모리가 없다.
• 구현 시 용이함 - 연결 리스트를 사용해서 다양한 자료구조를 구현할 수 있다.(스택, 큐, 그래프, 해쉬맵 등)

연결 리스트의 단점

• 메모리 사용 - 각 노드마다 포인터를 갖고 있음으로써 더 많은 메모리를 사용한다.
• 임의 노드에 대한 직접적인 접근 불가 - 메모리 할당이 불규칙적이기 때문에 어떤 노드를 탐색하기 위해서는 순차적인 방식으로 접근해야 한다.
• 요소 검색에 드는 비용 - O(n)의 시간복잡도를 가진다.
• 역순으로 탐색 불가능 - singly linked list에서는 역순 탐색이 불가능하다.