본문 바로가기

Data structure & Algorithms study

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

이중 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고 있는 선형 자료 구조이다. 한 포인터는 다음 노드를 가리키고, 다른 포인터는 이전 노드를 가리킨다. 이를 통해 리스트를 양방향으로 순회할 수 있다. 이중 연결 리스트는 단일 연결 리스트(Singly Linked List)에 비해 더 많은 메모리를 사용하지만, 삽입 및 삭제 연산이 더 유연하고 효율적이다.

구조

  1. 노드 (Node): 이중 연결 리스트의 기본 구성 요소로, 데이터와 두 개의 포인터(이전 노드와 다음 노드를 가리키는 포인터)를 포함한다.
    • 데이터 (Data): 노드가 저장하는 값.
    • 이전 (Prev): 이전 노드를 가리키는 포인터.
    • 다음 (Next): 다음 노드를 가리키는 포인터.
  2. 헤드 (Head): 리스트의 첫 번째 노드를 가리키는 포인터. 리스트의 시작점이다.
  3. 꼬리 (Tail): 리스트의 마지막 노드를 가리키는 포인터. 리스트의 끝점이다.

이중 연결 리스트의 주요 연산

  1. 삽입 (Insertion):
    • 앞쪽 삽입 (Insert at the Beginning): 새 노드를 헤드 앞에 추가하고, 헤드를 새 노드로 갱신한다.
    • 끝쪽 삽입 (Insert at the End): 새 노드를 리스트의 끝에 추가한다.
    • 중간 삽입 (Insert in the Middle): 특정 위치에 새 노드를 삽입한다.
  2. 삭제 (Deletion):
    • 앞쪽 삭제 (Delete from the Beginning): 첫 번째 노드를 삭제하고, 헤드를 다음 노드로 갱신한다.
    • 끝쪽 삭제 (Delete from the End): 마지막 노드를 삭제한다.
    • 중간 삭제 (Delete in the Middle): 특정 위치의 노드를 삭제한다.
  3. 탐색 (Search): 리스트를 순회하면서 특정 값을 가진 노드를 찾는다.
  4. 길이 반환 (Get Length): 리스트에 포함된 노드의 개수를 반환한다.
  5. 출력 (Display): 리스트의 모든 노드를 순서대로 출력한다.

이중 연결 리스트의 장단점

장점:

  1. 양방향 순회 가능: 이전 노드를 가리키는 포인터가 있어 양방향으로 리스트를 순회할 수 있다.
  2. 삽입과 삭제가 용이: 단일 연결 리스트에 비해 중간에 노드를 삽입하거나 삭제하는 연산이 더 간단하고 효율적이다.

단점:

  1. 추가 메모리 사용: 각 노드가 두 개의 포인터(이전과 다음)를 저장해야 하므로 추가 메모리를 사용한다.
  2. 구현 복잡도 증가: 단일 연결 리스트에 비해 구조가 복잡하여 구현이 더 어렵다.

이중 연결 리스트의 활용 예

  1. 이중 방향 순회가 필요한 경우: 양방향 순회가 필요한 경우에 유용하다. 예를 들어, 웹 브라우저의 앞뒤 탐색 기능, 이미지 뷰어에서 이전 및 다음 이미지 보기 등.
  2. 삽입 및 삭제 연산이 빈번한 경우: 중간 삽입과 삭제가 빈번하게 일어나는 경우 단일 연결 리스트보다 효율적이다.
  3. 캐시 구현: LRU(Least Recently Used) 캐시와 같은 알고리즘에서 사용될 수 있다.
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insertBeginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_node

    def insertEnd(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def insertMiddle(self, data, index):
        if index < 0:
            print("Invalid position")
            return
        new_node = Node(data)
        if index == 0:
            self.insertBeginning(data)
            return
        cur = self.head
        for i in range(index - 1):
            if cur is None:
                print("Index out of bounds")
                return
            cur = cur.next
        if cur is None:
            print("Index out of bounds")
            return
        new_node.next = cur.next
        new_node.prev = cur
        if cur.next is not None:
            cur.next.prev = new_node
        cur.next = new_node
        if new_node.next is None:
            self.tail = new_node

    def deleteNode(self, key):
        temp = self.head
        while temp is not None:
            if temp.data == key:
                if temp.prev is not None:
                    temp.prev.next = temp.next
                else:
                    self.head = temp.next
                if temp.next is not None:
                    temp.next.prev = temp.prev
                else:
                    self.tail = temp.prev
                return
            temp = temp.next
        print("Key not found")

    def search(self, key):
        cur = self.head
        while cur is not None:
            if cur.data == key:
                return True
            cur = cur.next
        return False

    def getLength(self) -> int:
        count = 0
        cur = self.head
        while cur:
            count += 1
            cur = cur.next
        return count

    def display(self):
        cur = self.head
        while cur:
            print(cur.data, end=" <-> ")
            cur = cur.next
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.insertEnd(10)
dll.insertEnd(20)
dll.insertBeginning(5)
dll.insertMiddle(2, 15)  # Insert 15 at position 2
dll.display()  # Output: 5 <-> 10 <-> 15 <-> 20 <-> None
print(dll.search(10))  # Output: True
print(dll.getLength())  # Output: 4
dll.deleteNode(10)
dll.display()  # Output: 5 <-> 15 <-> 20 <-> None

코드 설명

Node 클래스

  • data: 노드가 저장하는 데이터.
  • next: 다음 노드를 가리키는 포인터.
  • prev: 이전 노드를 가리키는 포인터.

DoublyLinkedList 클래스

초기화

  • head: 리스트의 첫 번째 노드를 가리킨다.
  • tail: 리스트의 마지막 노드를 가리킨다.

insertBeginning 메서드

  • 리스트의 맨 앞에 노드를 삽입합니다.
  • 새로운 노드를 head로 설정하고, 기존 head의 prev 포인터를 업데이트한다.
  • 리스트가 비어있을 경우, tail도 업데이트한다.

insertEnd 메서드

  • 리스트의 끝에 노드를 삽입한다.
  • 리스트가 비어있을 경우, head와 tail을 새로운 노드로 설정한다.
  • 그렇지 않은 경우, tail을 업데이트하고, 새로운 노드의 prev를 설정한다.

insertMiddle 메서드

  • 리스트의 특정 위치에 노드를 삽입한다.
  • 인덱스가 0일 경우, insertBeginning 메서드를 호출한다.
  • 인덱스가 리스트의 범위를 벗어나지 않도록 검사하고, 삽입 위치에 따라 next와 prev 포인터를 업데이트한다.

deleteNode 메서드

  • 특정 값을 가진 노드를 삭제한다.
  • 삭제할 노드의 prev와 next 포인터를 업데이트하여 노드를 리스트에서 제거한다.

search 메서드

  • 리스트에서 특정 값을 가진 노드를 검색한다.

getLength 메서드

  • 리스트의 노드 개수를 반환한다.

display 메서드

  • 리스트의 모든 노드를 순서대로 출력한다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms

728x90