Linked List

Array

• 배열(array)은 같은 타입의 여러 변수를 하나의 묶음으로 다루는 자료구조입니다.

시간복잡도

• 접근(Access)
  • 배열은 랜덤 접근(random access)가 가능
  • 특정 인덱스에 위치한 원소에 접근하는 경우 $O(1)$의 시간복잡도
• 검색(Search) ← 순차 접근이라도 함
  • 선형 검색(Linear Search): 특정 값이 있는 인덱스를 찾는 경우로 $O(n)$
  • 이진 탐색(Binary Search): 정렬된 배열에서 특정 값을 찾는 경우 $O(\log n)$
• 삽입(Insertion)
  • 배열의 시작에 원소를 삽입하는 경우: $O(n)$
  • 배열의 중간 위치에 원소를 삽입하는 경우: $O(n)$
  • 배열의 끝 위치에 원소를 삽입하는 경우: $O(1)$
    • (동적 배열의 경우, 배열이 가득찬 상태에서 요소가 추가될 경우 배열의 크기를 두배로 늘리고 모든 요소를 기존에 데이터를 복제하는데, 이때 비용이 발생하고 불필요한 공간이 낭비될 수 있는 문제가 있습니다.)
• 삭제(Deletion)
  • 배열의 시작에 원소를 삭제하는 경우: $O(n)$
  • 배열의 중간에 원소를 삭제하는 경우: $O(n)$
  • 배열의 끝에 원소를 삭제하는 경우: $O(1)$

Linked List

• 연결 리스트(Linked List)는 배열과 비교했을 때, 삽입/삭제 연산에 효율적인 자료구조입니다.

시간복잡도

• 접근(Access)

  • 특정 인덱스에 위치한 원소에 접근하는 경우 $O(n)$의 시간복잡도
  • 검색(Search)
  • 특정 값의 노드를 찾는 경우: $O(n)$

• 삽입(Insertion)

  • 연결 리스트의 시작에 원소를 삽입하는 경우: $O(1)$
  • 연결 리스트의 중간에 원소를 삽입하는 경우: $O(n)$
    • (삽입할 위치를 찾기 위해서 최악의 경우 n번 순회)
  • 연결 리스트의 마지막에 원소를 삽입하는 경우: $O(n)$

• 삭제(Deletion)

  • 연결 리스트의 시작에 원소를 삭제하는 경우: $O(1)$
  • 연결 리스트의 중간에 원소를 삭제하는 경우: $O(n)$
  • 연결 리스트의 끝에 원소를 삭제하는 경우: $O(n)$ (마지막 이전의 노드를 찾기 위해서 n번 순회 필요)

Linked List의 장점과 단점?

장점

• 동적 크기: 배열과 달리 링크드 리스트는 고정된 크기를 갖지 않습니다. 따라서, 메모리 사용이 효율적이며 필요에 따라 리스트의 크기를 동적으로 변경할 수 있습니다.
• 삽입 및 삭제 용이: 배열에서는 원소를 삽입하거나 삭제할 때 해당 위치 뒤의 모든 원소를 이동해야 합니다. 반면, 링크드 리스트에서는 특정 위치에 원소를 삽입하거나 삭제할 때 해당 노드의 포인터만 변경하면 되므로 O(1)의 시간 복잡도로 연산을 수행할 수 있습니다 (단, 삭제나 삽입을 위해 특정 노드를 찾는 데는 추가적인 시간이 필요합니다).
• 메모리 할당: 링크드 리스트는 노드를 필요에 따라 동적으로 할당하므로, 초기 메모리 할당이 필요하지 않습니다.

단점

• 메모리 사용: 각 노드는 데이터와 포인터(다음 노드를 가리키는)를 저장해야 하므로 추가적인 메모리가 필요합니다. 이로 인해 배열에 비해 메모리 사용이 비효율적일 수 있습니다.
• 순차 접근: 링크드 리스트는 인덱스 기반의 접근을 제공하지 않습니다. 따라서, 특정 노드에 접근하려면 헤드부터 순차적으로 탐색해야 합니다. 이는 배열에 비해 접근 시간이 길어질 수 있습니다.
• 복잡성: 링크드 리스트는 포인터를 사용하여 노드들이 연결되어 있기 때문에, 연산이 배열보다 복잡해질 수 있습니다. 특히 이중 연결 리스트나 원형 연결 리스트에서는 더 복잡한 연산이 필요합니다.
• 역순 탐색의 어려움: 단일 연결 리스트의 경우, 역순으로 리스트를 탐색하는 것이 어렵습니다. 이를 해결하기 위해 이중 연결 리스트를 사용할 수 있지만, 이는 추가적인 메모리를 필요로 합니다.

단일/이중/원형 연결 리스트 비교

Singly Linked List (단일 연결 리스트)

• 각 요소가 다음 요소만 가리키는 단일 방향 구조
  노드가 데이터와 다음 노드를 가리키는 포인터 하나로 이루어짐
• 단점: 마지막 요소의 포인터가 null 값을 가지고 있는 구조에서는 첫 노드와 마지막 노드에 대한 접근성이 극적으로 차이납니다.

사용 사례

• 스택과 큐의 구현: 단일 연결 리스트는 스택 및 큐의 구현에 주로 사용됩니다. 이는 삽입 및 삭제 연산이 $O(1)$의 시간 복잡도를 가지기 때문입니다.
• 재귀 알고리즘: 단일 연결 리스트는 재귀 알고리즘이나 함수 호출을 구현하는 데 유용합니다. 노드를 쉽게 추가하거나 제거할 수 있기 때문입니다.
• Memory Management: 연속적인 메모리 할당이 필요하지 않은 경우에 단일 연결 리스트를 사용하여 메모리를 효율적으로 관리할 수 있습니다.

Doubly Linked List (이중 연결 리스트)

• 각 노드가 데이터와 이전 노드, 다음 노드를 가리키는 두 개의 포인터로 구성되어 있습니다.
• 양방향으로 탐색이 가능한 구조로, 노드의 이전 노드에 대한 참조를 가지고 있어 역방향 탐색이 용이합니다.

사용 사례

• 양방향 탐색이 필요한 경우: 텍스트 에디터, 브라우저의 앞/뒤로 가기 기능 등에서 사용됩니다. 또한, 작업 큐의 관리와 같이 양방향으로 탐색이 필요한 상황에 적합합니다.
• 데이터의 삽입 및 삭제가 빈번한 경우: 데이터를 중간에 삽입하거나 삭제하는 작업을 빠르게 처리할 수 있습니다. 데이터의 순서를 변경하거나 재정렬할 때도 유용합니다.
• 캐시 구현 (LRU Cache 등): LRU (Least Recently Used) 캐시에서는 이중 연결 리스트를 활용하여 캐시 항목을 관리합니다.

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

• 마지막 요소의 포인터가 첫 요소를 가리키는 형태로 구성된 연결 리스트입니다.
• 원형 구조로 인해 순환적인 작업이 필요한 상황에서 사용됩니다.

사용 사례

• 순환 버퍼 (Circular Buffer)의 구현: 데이터 스트림을 저장하거나 원형 구조의 데이터를 관리할 때 유용합니다. 실시간 스트리밍, 데이터 유지 기간 등에 활용됩니다.
• 프로세스 스케줄링: 프로세스 스케줄링 알고리즘 중 Round Robin 알고리즘에서 사용됩니다.
• Task Scheduling: 정기적으로 반복되는 작업을 스케줄링하는 시스템에서 사용됩니다.
• Load Balancing: 서버에 도착하는 요청을 순환적으로 다른 서버에 분배하는 로드 밸런싱 알고리즘을 구현할 때 활용됩니다.

Single Linked List 구현

Node 클래스

• Node 클래스는 연결 리스트의 노드를 나타냅니다.
• __init__ 메서드는 노드를 초기화하고 데이터를 저장하며, 다음 노드에 대한 참조 (next)를 초기화합니다.

SinglyLinkedList 클래스

• SinglyLinkedList 클래스는 단일 연결 리스트를 나타냅니다.
• __init__ 메서드는 연결 리스트의 헤드 (head)와 테일 (tail) 노드, 그리고 리스트의 크기를 초기화합니다.
• addFirst(e) : 연결 리스트의 맨 앞에 요소를 추가합니다. 새로운 노드를 생성하고, 헤드를 업데이트하여 요소를 추가합니다.
• addLast(e) : 연결 리스트의 맨 끝에 요소를 추가합니다. 새로운 노드를 생성하고, 테일을 업데이트하여 요소를 추가합니다.
• add(index, e) : 특정 위치에 요소를 추가합니다. 인덱스가 유효한 경우, 해당 위치에 요소를 추가하고 이전 노드와 다음 노드의 연결을 업데이트합니다.
• get_node(index) : 주어진 인덱스에 해당하는 노드를 반환합니다.
• get(index) : 주어진 인덱스에 해당하는 요소를 반환합니다.
• set(index, e) : 주어진 인덱스에 있는 요소를 새로운 값으로 대체하고 이전 값을 반환합니다.
• remove(index) : 주어진 인덱스에 있는 요소를 제거하고 제거된 요소를 반환합니다. 요소를 제거하면 연결 리스트의 구조가 조정됩니다.
• print_list() : 연결 리스트의 요소를 출력합니다.

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

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

    def addFirst(self, e):
        new_node = Node(e)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.size += 1

    def addLast(self, e):
        new_node = Node(e)
        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def add(self, index, e):
        if not (0 <= index <= self.size):
            raise IndexError("Index: {}, Size: {}".format(index, self.size))

        if index == self.size:
            self.addLast(e)
        elif index == 0:
            self.addFirst(e)
        else:
            prev_node = self.get_node(index - 1)
            new_node = Node(e)
            new_node.next = prev_node.next
            prev_node.next = new_node
            self.size += 1

    def get_node(self, index):
        if not (0 <= index < self.size):
            raise IndexError("Index: {}, Size: {}".format(index, self.size))
        current_node = self.head
        for _ in range(index):
            current_node = current_node.next
        return current_node

    def get(self, index):
        return self.get_node(index).data

    def set(self, index, e):
        if not (0 <= index < self.size):
            raise IndexError("Index: {}, Size: {}".format(index, self.size))
        current_node = self.get_node(index)
        old_data = current_node.data
        current_node.data = e
        return old_data

    def remove(self, index):
        if not (0 <= index < self.size):
            raise IndexError("Index: {}, Size: {}".format(index, self.size))

        if index == 0:
            removed_node = self.head
            self.head = self.head.next
            if self.size == 1:
                self.tail = None
        elif index == self.size - 1:
            prev_node = self.get_node(index - 1)
            removed_node = prev_node.next
            prev_node.next = None
            self.tail = prev_node
        else:
            prev_node = self.get_node(index - 1)
            removed_node = prev_node.next
            prev_node.next = removed_node.next

        self.size -= 1
        return removed_node.data

    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

테스트 결과

if __name__ == "__main__":
    linked_list = SinglyLinkedList()

    linked_list.addFirst("A-")
    linked_list.addFirst("A")
    linked_list.addLast("A+")
    linked_list.print_list()  # (0) A, (1) A-, (2) A+

    node = linked_list.get_node(2)
    print("node =", node.data)

    linked_list.add(0, "N")
    linked_list.add(2, "P")
    linked_list.add(5, "Q")
    print(" ======================== ")
    linked_list.print_list()

    print(" ======================== ")
    linked_list.set(5, "New Q")
    linked_list.set(0, "New N")
    linked_list.print_list()

    print(" ======================== ")
    remove1 = linked_list.remove(5)
    remove2 = linked_list.remove(3)
    remove3 = linked_list.remove(0)
    linked_list.print_list()

A -> A- -> A+ -> None
node = A+
 ======================== 
N -> A -> P -> A- -> A+ -> Q -> None
 ======================== 
New N -> A -> P -> A- -> A+ -> New Q -> None
 ========================
A -> P -> A+ -> None

Double Linked List 구현

BidirectionalNode 클래스

• BidirectionalNode 클래스는 더블 링크드 리스트의 노드를 나타냅니다.
• __init__ 메서드는 노드를 초기화하고 데이터를 저장하며, 이전과 다음 노드에 대한 참조 (prev, next)를 초기화합니다.

DoublyLinkedList 클래스

• DoublyLinkedList 클래스는 양방향 연결 리스트를 나타냅니다.
• init(self): 이중 연결 리스트를 초기화하는 생성자 메서드입니다. 더미 헤드와 더미 테일을 생성하고, 리스트 크기를 0으로 초기화합니다.
• add_first(e): 리스트의 맨 앞에 요소를 추가하는 메서드입니다. 새로운 노드를 생성하여 맨 앞에 추가하고, 리스트 크기를 증가시킵니다.
• add_last(e): 리스트의 맨 뒤에 요소를 추가하는 메서드입니다. 새로운 노드를 생성하여 맨 뒤에 추가하고, 리스트 크기를 증가시킵니다.
• add(index, e): 지정된 위치에 요소를 추가하는 메서드입니다. 인덱스를 확인하고 새로운 노드를 생성하여 해당 위치에 추가하고, 리스트 크기를 증가시킵니다.
• get_node(index): 주어진 인덱스에 해당하는 노드를 반환하는 메서드입니다. 인덱스를 확인하고 해당 노드를 찾아서 반환합니다.
• get(index): 주어진 인덱스에 해당하는 요소를 반환하는 메서드입니다. get_node를 사용하여 해당 노드를 찾아 데이터를 반환합니다.
• set(index, e): 주어진 인덱스에 해당하는 요소를 새로운 값으로 변경하는 메서드입니다. 인덱스를 확인하고 해당 노드의 데이터를 업데이트한 후 이전 데이터를 반환합니다.
• remove(index): 주어진 인덱스에 해당하는 요소를 제거하는 메서드입니다. 인덱스를 확인하고 해당 노드를 연결 리스트에서 제거하며, 리스트 크기를 감소시킵니다.
• print_list(): 연결 리스트를 출력하는 메서드입니다. 더미 헤드부터 더미 테일까지 순회하며 각 노드의 데이터를 화면에 출력합니다.

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


class DoublyLinkedList:
    def __init__(self):
        self.dummy_head = BidirectionalNode(None)
        self.dummy_tail = BidirectionalNode(None)
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head
        self.size = 0

    def add_first(self, e):
        new_node = BidirectionalNode(e)
        new_node.next = self.dummy_head.next
        new_node.prev = self.dummy_head
        self.dummy_head.next.prev = new_node
        self.dummy_head.next = new_node
        self.size += 1

    def add_last(self, e):
        new_node = BidirectionalNode(e)
        new_node.next = self.dummy_tail
        new_node.prev = self.dummy_tail.prev
        self.dummy_tail.prev.next = new_node
        self.dummy_tail.prev = new_node
        self.size += 1

    def add(self, index, e):
        if not (0 <= index <= self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")

        prev_node = self.get_node(index - 1)
        new_node = BidirectionalNode(e)
        new_node.prev = prev_node
        new_node.next = prev_node.next
        prev_node.next.prev = new_node
        prev_node.next = new_node
        self.size += 1

    def get_node(self, index):
        if not (-1 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")

        current_node = None

        if index < self.size // 2:
            current_node = self.dummy_head
            for i in range(-1, index + 1):
                current_node = current_node.next
        else:
            current_node = self.dummy_tail
            for i in range(self.size, index, -1):
                current_node = current_node.prev

        return current_node

    def get(self, index):
        return self.get_node(index).data

    def set(self, index, e):
        if not (0 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")

        current_node = self.get_node(index)
        old_data = current_node.data
        current_node.data = e
        return old_data

    def remove(self, index):
        if not (0 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")

        current_node = self.get_node(index)
        current_node.prev.next = current_node.next
        current_node.next.prev = current_node.prev
        self.size -= 1

    def print_list(self):
        current_node = self.dummy_head
        print("dummy head <->", end=" ")

        while current_node.next != self.dummy_tail:
            current_node = current_node.next
            print(current_node.data, end=" <-> ")

        print("dummy tail")

테스트 코드

if __name__ == "__main__":
    linked_list = DoublyLinkedList()

    # add_first() 테스트
    linked_list.add_first(3)
    linked_list.add_first(2)
    linked_list.add_first(1)
    print("add_first() 후: ")
    linked_list.print_list()

    # add_last() 테스트
    linked_list.add_last(4)
    linked_list.add_last(5)
    print("add_last() 후: ")
    linked_list.print_list()

    # add(index, element) 테스트
    linked_list.add(0, 0)  # 처음에 0 추가
    linked_list.add(6, 6)  # 마지막에 6 추가
    linked_list.add(4, 99)  # 4번 인덱스에 99 추가
    print("add(index, element) 후: ")
    linked_list.print_list()

    # get(index) 테스트
    print("인덱스 3의 요소: " + str(linked_list.get(3)))  # 예상 결과: 인덱스 3의 요소: 99

    # set(index, element) 테스트
    linked_list.set(4, 100)  # 인덱스 4의 요소를 100으로 변경
    print("set(index, element) 후: ")
    linked_list.print_list()

    # remove(index) 테스트
    linked_list.remove(0)  # 첫 번째 요소 제거
    linked_list.remove(6)  # 마지막 요소 제거
    print("remove(index) 후: ")
    linked_list.print_list()

add_first() 후: 
dummy head <-> 1 <-> 2 <-> 3 <-> dummy tail
add_last() 후:
dummy head <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> dummy tail
add(index, element) 후:
dummy head <-> 1 <-> 0 <-> 2 <-> 3 <-> 99 <-> 4 <-> 5 <-> 6 <-> dummy tail
인덱스 3의 요소: 99
set(index, element) 후:
dummy head <-> 1 <-> 0 <-> 2 <-> 3 <-> 100 <-> 4 <-> 5 <-> 6 <-> dummy tail
remove(index) 후:
dummy head <-> 1 <-> 2 <-> 3 <-> 100 <-> 4 <-> 5 <-> dummy tail

Circular Linked List 구현

CircularNode 클래스

• CircularNode 클래스는 원형 링크드 리스트의 노드를 나타냅니다.
• __init__ 메서드는 노드를 초기화하고 데이터를 저장하며, 다음 노드에 대한 참조 (next)를 초기화합니다.

CircularLinkedList 클래스

• CircularLinkedList 클래스는 원형 연결 리스트를 나타냅니다.
• init(self): 원형 연결 리스트를 초기화하는 생성자 메서드입니다. 더미 헤드를 생성하고, 리스트 크기를 0으로 초기화합니다.
• add_first(e): 리스트의 맨 앞에 요소를 추가하는 메서드입니다. 새로운 노드를 생성하여 맨 앞에 추가하고, 리스트 크기를 증가시킵니다.
• add_last(e): 리스트의 맨 뒤에 요소를 추가하는 메서드입니다. 새로운 노드를 생성하여 맨 뒤에 추가하고, 리스트 크기를 증가시킵니다.
• add(index, e): 지정된 위치에 요소를 추가하는 메서드입니다. 인덱스를 확인하고 새로운 노드를 생성하여 해당 위치에 추가하고, 리스트 크기를 증가시킵니다.
• get_node(index): 주어진 인덱스에 해당하는 노드를 반환하는 메서드입니다. 인덱스를 확인하고 해당 노드를 찾아서 반환합니다.
• get(index): 주어진 인덱스에 해당하는 요소를 반환하는 메서드입니다. get_node를 사용하여 해당 노드를 찾아 데이터를 반환합니다.
• set(index, e): 주어진 인덱스에 해당하는 요소를 새로운 값으로 변경하는 메서드입니다. 인덱스를 확인하고 해당 노드의 데이터를 업데이트한 후 이전 데이터를 반환합니다.
• remove(index): 주어진 인덱스에 해당하는 요소를 제거하는 메서드입니다. 인덱스를 확인하고 해당 노드를 연결 리스트에서 제거하며, 리스트 크기를 감소시킵니다.
• print_list(): 연결 리스트를 출력하는 메서드입니다. 더미 헤드부터 순회하며 각 노드의 데이터를 화면에 출력합니다.

class BidirectionalNode:
    def __init__(self, data=None, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next
        
class CircularDoublyLinkedList:
    def __init__(self):
        self.dummyHead = BidirectionalNode()
        self.dummyTail = BidirectionalNode()
        self.dummyHead.next = self.dummyTail
        self.dummyTail.prev = self.dummyHead
        self.dummyHead.prev = self.dummyTail
        self.dummyTail.next = self.dummyHead
        self.size = 0
        
    def addFirst(self, e):
        new_node = BidirectionalNode(e)
        new_node.next = self.dummyHead.next
        new_node.prev = self.dummyHead
        self.dummyHead.next.prev = new_node
        self.dummyHead.next = new_node
        self.size += 1
        
    def addLast(self, e):
        new_node = BidirectionalNode(e)
        new_node.next = self.dummyTail
        new_node.prev = self.dummyTail.prev
        self.dummyTail.prev.next = new_node
        self.dummyTail.prev = new_node
        self.size += 1
        
	def add(self, index, e):
        if not (0 <= index <= self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")
        prev_node = self.getNode(index - 1)
        new_node = BidirectionalNode(e)
        new_node.prev = prev_node
        new_node.next = prev_node.next
        prev_node.next.prev = new_node
        prev_node.next = new_node
        self.size += 1

    def getNode(self, index):
        if not (-1 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")
        if index < self.size // 2:
            current_node = self.dummyHead
            for _ in range(index + 1):
                current_node = current_node.next
            return current_node
        else:
            current_node = self.dummyTail
            for _ in range(self.size - index):
                current_node = current_node.prev
            return current_node

    def get(self, index):
        if not (0 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")
        return self.getNode(index).data

    def set(self, index, e):
        if not (0 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")
        current_node = self.getNode(index)
        old_data = current_node.data
        current_node.data = e
        return old_data

    def remove(self, index):
        if not (0 <= index < self.size):
            raise IndexError(f"Index: {index}, Size: {self.size}")
        current_node = self.getNode(index)
        current_node.prev.next = current_node.next
        current_node.next.prev = current_node.prev
        self.size -= 1
        return current_node.data

    def print(self):
        curr_node = self.dummyHead
        print("dummy head <-> ", end="")
        while curr_node.next != self.dummyTail:
            curr_node = curr_node.next
            print(f"{curr_node.data} <-> ", end="")
        print("dummy tail <-> dummy head")