연결리스트

연결리스트는 데이터를 순서대로 저장하는 자료구조이다. 각각의 데이터는 노드(node)라는 단위로 구성되어 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(pointer)로 이루어져 있다.

연결리스트는 배열과 달리 데이터를 연속적으로 저장하지 않기 때문에 삽입, 삭제 작업이 용이하다. 또한, 배열과 달리 크기를 미리 지정하지 않아도 되기 때문에 동적으로 메모리를 할당할 수 있다.

예시

다음은 정수형 데이터를 저장하는 단순 연결리스트의 예시이다.

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

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

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

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data)
            current_node = current_node.next

연결리스트의 장점

• 삽입 및 삭제 작업이 배열에 비해 용이
• 동적으로 메모리를 할당

연결리스트의 단점

• 특정 인덱스에 직접 접근 불가
• 노드마다 포인터를 저장해야 하므로, 저장공간이 배열에 비해 더 많이 필요
• 배열과 달리 캐시 지역성(cache locality)을 가지지 않아, 메모리 접근이 느림

연결리스트의 삽입과 삭제 과정

삽입 과정은 다음과 같다:

1. 삽입할 데이터를 담은 새로운 노드를 만든다.
2. 새로운 노드가 삽입될 위치를 가리키는 포인터를 찾는다. (ex. 새로운 노드가 3번째에 삽입될 경우, 2번째 노드의 포인터를 찾는다.)
3. 새로운 노드가 삽입될 위치를 가리키는 포인터를 새로운 노드가 가리키게 한다.
4. 이전 노드의 포인터를 새로운 노드가 가리키게 한다.

삭제 과정은 다음과 같다: