링크드 리스트 (Linked List)

코딩 테스트에 단골로 나오는 자료구조인 링크드 리스트(linked list)에 대해서 알아보겠습니다.

링크드 리스트란?

링크드 리스트는 배열(array)의 사촌뻘되는 자료구조로서 유난히 코딩 시험에 자주 등장하는 자료구조입니다. 링크드 리스트를 다음과 같이 마치 데이터가 사슬로 연결된 모습으로 시각화됩니다.

head

-->

null

링크드 리스트는 소위, 노드(node)라고 일컽는 객체의 일부로 데이터를 저장합니다. 링크드 리스트 상에서 각 노드에는 다음 노드를 가리키고 있는 레퍼런스(reference) 또는 포인터(pointer)도 함께 저장되어 있습니다.

즉, 하나의 노드에는 다음 2가지 정보를 담겨있습니다.

데이터 값 (value)
다음 노드의 레퍼런스 (next)

링크드 리스트는 어떤 일련의 데이터를 처음부터 끝까지 쭈욱 탐색하기 매우 적합한 구조를 가지고 있습니다.

링크드 리스트에는 Singly Linked List, Doubly Linked List, Circular Linked List 등 다양한 종류가 있는데요. 본 가이드에서는 코딩 시험에서 많이 나오는 Singly Linked List 기준으로만 살펴보도록 하겠습니다.

배열과 비교

링크드 리스트와 배열은 여러 개의 데이터를 차례대로 저장할 수 있다는 점에서 상당히 유사하지만 이 두 자료구조는 흥미로운 차이점이 있습니다.

배열은 일반적으로 많은 언어에서 크기가 고정되어 있으며, 데이터를 추가하거나 삭제하는데 불리한 자료구조입니다. 왜냐하면 배열은 메모리 상의 연속된 영역을 차지해야하기 때문에 유연하게 크기를 줄이거나 늘리기가 어려운 구조이기 때문입니다. 대신에 배열은 인덱스를 통해 데이터를 매우 빠르게 접근할 수 있습니다.

반면에 링크드 리스트는 크기에 제한이 없는 경우가 많으며, 데이터를 추가하거나 삭제하기 유리한 자료구조입니다. 링크드 리스트에 저장되어 있는 노드들은 메모리 상에서 좀 더 자유롭게 위치할 수 있습니다. 이전 노드에 다음 노드가 메모리 상에 어디에 위치하는지 저장이 되어있기 때문입니다.

데이터 무작위 접근(random access)에 최적화되어 있는 배열과 달리 링크드 리스트는 특정 데이터에 접근하는데 시간이 오래 걸립니다. 왜냐하면 맨 첫 번째 노드부터 원하는 값을 찾을 때까지 자료구조를 전체를 순회를 해야하기 때문에 시간 복잡도가 O(n)입니다.

한마디로 정리하면 성능 측면에서 링크드 리스트는 데이터의 추가와 삭제에 강점이 있는 반면에 배열은 데이터의 접근에 강점이 있습니다. 따라서 데이터를 단순히 읽는 작업이 많은 프로그램에서는 배열이 유리하고, 데이터의 추가/삭제가 잦은 프로그램에서는 링크드 리스트가 유리합니다.

코딩 테스트에서 활용

코딩 테스트에서 링크드 리스트를 만날 가능성은 상당히 높은데요. 아무래도 비교적 간단한 자료구조이지만 여러가지 방법으로 응용해서 문제를 내기가 좋기 때문인 것 같습니다.

그럼, 파이썬으로 간단하게 링크드 리스트를 한번 구현해볼까요?

먼저 링크드 리스트에 저장되는 각 노드를 나타내는 클래스로 정의합니다. 데이터 값을 저장하기 위해서 value 인스턴스 변수가 필요하고, 다음 노드의 레퍼런스를 저장하기 위해서 next 인스턴스 변수가 필요합니다.

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

이제 링크드 리스트 자료구조 자체를 나타내는 클래스로 필요할까요?

적어도 코딩 시험에 한해서는 링크드 리스트 자료구조 자체를 나타내는 클래스는 정의할 일이 거의 없습니다. 온라인 코딩 시험이라면 위와 같은 클래스에 대한 코드가 미리 작성되어 제공되는 경우도 많을 것입니다.

링크드 리스트와 관련된 코딩 문제에서는 대부분의 경우 링크드 리스트의 첫 번째 노드가 입력으로 주어지는데요. 이 첫 번째 노드를 이용해서 링크드 리스트 상의 모든 노드를 하나씩 순회해야하는 경우가 많습니다.

이럴 때는 다음 코딩 패턴을 매우 유용하게 쓸 수 있습니다.

node = head # 첫 번째 노드를 `node` 변수에 저장
while node: # `node` 변수에 저장된 노드가 있는 동안 반복
  do_something(node) # 현재 노드를 대상으로 어떤 작업을 수행
  node = node.next # 다음 노드를 `node` 변수에 저장

여기서 node 변수에 저장된 노드가 있는 동안만 반복하는 이유는 node에 저장된 노드가 없다면 링크드 리스트의 제일 마지막에 도달하여 더 이상 처리할 노드가 없다는 뜻이기 때문입니다.

링크드 리스트와 관련된 코딩 문제를 풀때는 보통 이러한 반복문이 필요하기 때문에 모범 답안의 시간 복잡도가 O(n)인 경우가 많습니다.

시간 복잡도

링크드 리스트의 맨 앞에서 데이터를 추가하거나 삭제하는 것은 단순히 포인터를 바꿔주는 작업어서 시간 복잡도가 O(1)입니다. 데이터에 접근할 때는 링크드 리스트의 각 노드를 하나씩 하나씩 순회해야하기 때문에 시간 복잡도가 O(n)입니다.

링크드 리스트 (Linked List)

링크드 리스트란?

배열과 비교

코딩 테스트에서 활용

시간 복잡도

추천 문제