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

연결 리스트란?

원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 이곳저곳에 흩어져 있다.

• 파이썬에서는 배열과 연결 리스트의 장점을 합친 리스트를 사용한다.

 

연결 리스트의 성질

• k 번째 원소를 확인/변경하기 위해 O(k)가 필요함
• 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

 

연결 리스트의 종류

배열과 다르게 리스트에는 몇 개의 종류가 있다.

• 단일 연결 리스트(Singly Linked list)
  • 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트

[데이터1] -> [데이터2] -> [데이터3] -> None

• 이중 연결 리스트(Doubly Linked list)
  • 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고있다. 단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데 이중 연결 리스트에서는 알 수 있다. 다만 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 쓴다는 단점이 있다.

None <- [데이터1] <-> [데이터2] <-> [데이터3] -> None

• 원형 연결 리스트(Circular Linked list)
  • 끝이 처음과 연결되어 있다. 

[데이터1] -> [데이터2] -> [데이터3] -> [첫 번째 데이터] -> ...

 

 

배열과 연결 리스트 비교하기

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(Overhead)	-	O(N)

 

 

기능과 구현

임의의 위치에 있는 원소를 확인/변경 = O(N)

임의의 위치에 원소를 추가/임의 위치에 원소 제거 = O(1)