연결 리스트(Linked List)

연결 리스트란

선형 자료구조의 하나로, 데이터를 노드로 묶고 포인터로 서로 연결한 구조이다. 각 노드는 값(data)과 다음 노드의 주소를 가리키는 포인터(next)를 가진다.

연산	시간 복잡도	이유
탐색	O(n)	처음부터 순서대로 노드를 따라가야 한다
삽입 / 삭제 (위치를 아는 경우)	O(1)	주변 노드의 포인터만 바꾸면 된다
삽입 / 삭제 (위치를 찾아야 하는 경우)	O(n)	탐색한 뒤에 삽입 / 삭제를 해야 한다

삽입과 삭제가 O(1)이라는 것은 대상 위치를 이미 알고 있을 때의 이야기이다. 현실적으로는 탐색이 먼저 필요하므로 O(n)이 된다. 또한 데이터 외에 포인터를 저장할 추가 메모리가 필요하다는 단점이 있다.

배열과 연결 리스트

	배열	연결 리스트
메모리 배치	연속된 공간에 순차적으로 저장	불연속적으로 저장
인덱스 접근	O(1)	O(n)
삽입 / 삭제	O(n)	O(1) (위치를 아는 경우)

• 배열은 원소가 연속된 공간에 있어 인덱스로 주소를 바로 계산할 수 있으므로 접근이 O(1)이다.
• 대신 중간에 삽입하거나 삭제하면 뒤의 원소들을 옮겨야 하고, 공간이 부족하면 더 큰 배열을 만들어 복사해야 하므로 O(n)이다.

탐색이 많고 수정이 적으면 배열을, 탐색은 드물고 수정이 많으면 연결 리스트를 사용한다.

원형 연결 리스트

tail의 포인터가 head의 주소를 가리키게 한 연결 리스트이다.

• 계속 순환하며 값을 읽어야 하는 경우에 쓰인다. 예를 들어 1초마다 다음 값을 계속 찍어내야 하는 경우이다.
• head와 tail을 구분할 필요 없이 다음 노드의 정보만 알면 된다.
• tail 하나만 알고 있으면 tail.next로 head에도 바로 접근할 수 있다. 단순 연결 리스트에서 tail 뒤에 추가할 때 끝까지 따라가느라 발생하는 O(n)이 없다.

삽입

삭제

이중 연결 리스트

각 노드가 이전 노드(prev)와 다음 노드(next)를 모두 가리킨다.

• 장점: 양방향 탐색이 가능하다. 특정 인덱스의 원소를 가져올 때 인덱스가 중간보다 크면 tail부터 거꾸로 탐색할 수 있다.
• 단점: 포인터가 두 개이므로 메모리가 더 필요하다.

구현

파이썬으로 단순 연결 리스트를 구현하면 다음과 같다.

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


class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_index(self, data):
        cur = self.head
        cnt = 0
        while cur is not None:
            if cur.data == data:
                return cnt
            cur = cur.next
            cnt += 1
        return -1


s1 = SinglyLinkedList()
s1.append(1)
s1.append(1)
s1.append(2)
print(s1.get_index(2))  # 2

연결 리스트를 뒤집는 문제는 LeetCode 206 풀이가 애니메이션과 함께 설명되어 있어 인상 깊었다.

더 생각해 볼 질문

• Array와 ArrayList의 차이는 무엇인가
• 연결 리스트의 노드는 메모리의 어느 영역에 저장되는가