[Algorithm] 내가 보려고 정리하는 파이썬 연결 리스트(Linked List) 기초

1. 연결 리스트 (Linked List) 기본 개념

---

연결 리스트(Linked List)란 선형 자료구조 중 배열과 함께 가장 기본이 되는 개념으로,
"물리 메모리 어딘가에 흩뿌려진 노드(Node)들이 서로 연결된 형태로 구성된 자료구조"를 의미한다.

그럼 잠깐, 여기서 노드(Node)가 무엇인지 설명이 필요할 수도 있겠다.
노드(node)는 "데이터(값) + 다음 노드의 주소(포인터)"를 담고 있는 형태로 이루어져 있는 녀석이다.

즉 다시 연결 리스트의 개념으로 돌아가자면, 다음 노드의 주소를 노드 자체에서 담고 있기 때문에 물리 메모리 상에서는 데이터가 여기저기 흩어져 있더라도, 서로 연결된 구조로 사용할 수 있는 것이다.

이러한 특징 때문에 연결 리스트(Linked List)는 동적으로 새로운 노드를 삽입하거나 삭제하기가 편하며, 그 관리 또한 편하다는 장점이 있다.
파이썬의 경우에는 리스트(List) 자료형에 연결 리스트의 기능이 포함되어 있는 형태이고, 더 정확하게는 C, C++ 등에서 배열과 연결 리스트는 엄격하게 구분돼서 사용된다.

연결 리스트 예시 이미지 (출처: 코딩 도장)

 

2. 노드 (Node) 생성하기

---

노드(Node) 클래스는 기본적으로 아래와 같이 작성할 수 있다.

값을 의미하는 data, 다음 노드의 주소를 의미하는 next 값을 모두 파라미터로 받으며, data는 0으로 next는 None으로 초깃값이 지정되어 있다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # 값
        self.next = next    # 다음 노드의 주소

그러면 실제 노드 생성과 값과 포인터 출력은 아래 코드와 같이 해줄 수 있다. 

# Node 생성 (data = 1)
node1 = ListNode(1)

# Node의 값과 포인터 출력
print(node1.val)     # 1
print(node1.next)    # None

 

3. 연결 리스트 (Linked List) 구현하기

---

그럼 위에서 생성해준 노드를 바탕으로 연결 리스트(Linked List) 클래스를 구현해주자.
여기서 보이는 헤드(head)는 연결 리스트 중에서도 가장 앞에 있는 노드를 의미한다.

새로운 노드를 추가하는 append 메서드 같은 경우에는
계속 노드를 헤드부터 반복/갱신하면서, 노드의 next값이 None이 나올 때 그 위치 노드의 next값에 새로운 데이터를 추가해주는 방식이다.

마찬가지로 모든 노드 값을 추가하는 print_all 메서드도 계속 노드를 헤드부터 반복/갱신하면서, val값을 출력해주는 방식인 것을 확인할 수 있겠다.

class LinkedList:
    def __init__(self, data):
        self.head = ListNode(data)
        
    # 새로운 노드 추가
    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = ListNode(data)
	
    # 모든 노드 값 출력
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.val)
            cur = cur.next

 

4. 노드 삽입하기 (add_node)

---

add_node 함수를 확인하기 전에는 노드를 가져올 수 있는 get_node 함수를 먼저 알아두어야 한다.

def get_node(self, index):
    count = 0
    node = self.head
    while count < index:
        count += 1
        node = node.next
    return node

자 이제 원하는 위치에 노드를 삽입하는 add_node 함수를 확인해보자.

여기서는 여러분들의 이해를 돕기 위해 조금 예시를 들어보도록 하겠다.
1 -> 2 -> 3으로 되어 있는 연결 리스트에 노드 4를 추가해서 1 -> 2 -> 4 -> 3으로 구성되어 있는 연결 리스트를 만들어주고 싶다고 해보자.

이때 필요한 것은 노드 2 위치("내가 삽입하고 싶은 위치-1"의 인덱스)를 파악해서, next를 3에서 4로 바꿔줘야 한다는 것.
그리고 새로 추가된 노드 4의 next는 3이 연결되도록 해야 한다는 것이다. 

아래 코드는 가장 첫 위치에 추가하는 경우에만 예외 처리를 해 두었고, 위의 순서 그대로 구현을 해준 모습이다. 

def add_node(self, index, value):
    new_node = ListNode(value)
    if index == 0:
        new_node.next = self.head
        self.head = new_node
        return
    node = self.get_node(index-1)
    next_node = node.next
    node.next = new_node
    new_node.next = next_node

 

5. 노드 삭제하기 (delete_node)

---

삭제도 마찬가지다.

삭제하고 싶은 위치의 인덱스를 받으면, "그 위치-1"의 노드를 찾아가 next값을 삭제하고 싶은 위치의 다음 노드로 연결을 시켜주기만 하면 된다.

def delete_node(self, index):
    if index == 0:
        self.head = self.head.next
        return
    node = self.get_node(index-1)
    node.next = node.next.next

 

6. 마무리

---

연결 리스트는 배열과는 달리 특정 인덱스에 접근하기 위해 전체를 순서대로 읽어야 하기 때문에 상수 시간에 접근하는 것이 불가능하다고 한다. 그러므로, 연결 리스트의 탐색 시간은 O(n)이 소요된다.

하지만, 연결 리스트의 장점이었던 노드의 삽입/삭제 같은 경우에는 O(1)이 가능하게 된다.

이 글 하나에 연결 리스트의 모든 기능과 특징을 살펴보기는 다소 부족할 수 있었지만,
앞으로 포스팅될 알고리즘 문제에서 더 자세하게 연결 리스트에 대해 알아보도록 하겠다 ^__^