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

연결 리스트(Linked List)란 데이터 요소의 선형 집합으로, 데이터의 순서가 꼭 메모리에 물리적인 순서대로 저장되지는 않는다.

연결 리스트는 컴퓨터과학에서 배열(Array)과 함께 가장 대표적인 선형 자료구조 중 하나로, 다양한 추상 자료형(Abstract Data Type) 구현의 기반이 된다.

---

• 장점 및 단점
  데이터를 삽입/삭제할 때마다 메모리를 사용/반환하므로 배열에 비해 경제적이다.
  또한 연결 리스트는 (시작 또는 끝 지점에) 데이터를 삽입/삭제하는 작업을 O(1)에 실행할 수 있다.
  그러나 특정 인덱스에 접근하기 위해서는 데이터를 앞에서부터 하나씩 순서대로 다 읽어나가야 하므로 O(N)이 소요된다.

따라서 삽입/삭제하는 작업이 많다면 연결 리스트를, 탐색/정렬하는 작업이 많다면 배열을 사용하는 것이 유리하다.

---

종류

• 단일 연결 리스트(Single Linked List)

• 이중 연결 리스트(Double Linked List)

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

---

구현 [Python]

class Node:
    def __init__(self, val, next):
        self.val = val
        self.next = next


n3 = Node(3, None)
n2 = Node(2, n3)
n1 = Node(1, n2)  # head is n1.

node = n1
while node:
    print('{}->'.format(node.val), end='')
    node = node.next
print('NULL')

# output : 1->2->3->NULL