[자료구조] 링크드 리스트 (Linked List)

 

링크드 리스트란 데이터와 포인터를 담은 노드를 연결시킨, 연결 자료구조다. 다음 노드만 가리키는 포인터만 있다면 단순 연결 리스트(Single Linked List)라 하고, 다음 노드와 이전 노드를 가리키는 포인터 두 개가 있다면 이중 연결 리스트(Doubly Linked List)라고 한다. 만약 두 링크드 리스트에서 head와 tail이 서로 앞 뒤로 연결되어 있다면 환형 연결 리스트(Circular Linked List)이다. 

 

링크드리스트는 순차 자료구조인 배열과 달리 포인터를 사용하기에 삽입과 삭제가 용이하다. 또한 배열과 달리 크기를 동적으로 조절할 수 있는 것도 장점이다. 반면 링크드 리스트는 특정 노드를 바로 접근할 수 없는 것이 단점이다. 링크드 리스트를 전부를 탐색해야 할 수 있도 있다. 따라서 링크드 리스트와 배열은 경우에 따라 나누어 사용해야 한다. 데이터가 빈번히 추가되거나 삭제될 경우 링크드리스트를 쓰는 것이 적합하고, 데이터 탐색과 정렬이 위주라면 배열을 쓰는 것이 적합하다. 참고로 윈도우 작업 관리자가 대표적인 링크드 리스트를 사용한 구현물이다. 하나의 프로세스는 앞 뒤로 다른 프로세스들과 연결되어 있는 Circular Linked List 구조로 되어 있다. 첫 번째 프로세스부터 다음 포인터를 계속 탐색하면 모든 프로세스 리스트를 가져올 수 있다.

 

단순 연결 리스트의 경우 기능은 크게 삽입/삭제/조회/탐색으로 구성된다. 이를 구현하기 위해 노드에 정보를 담을 Node 클래스와 기능을 구현할 SinglyLinkedList 클래스가 필요하다. 구현물은 다음과 같다.

 

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

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

    def size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_front(self, data):
        if self.is_empty():
            self.head = Node(data, None)
        else:
            self.head = Node(data, self.head)
        self.size += 1

    def insert_back(self, data, current):
        current.next = Node(data, current.next)
        self.size += 1
        
    def delete_front(self):
        if self.is_empty():
            raise LookupError("There is no node in the linked list")
        self.head = self.head.next
        self.size -= 1

    def delete_back(self, current):
        if self.is_empty():
            raise LookupError("There is no node in the linked list")
        temp = current.next
        current.next = temp.next
        self.size -= 1

    def traverse(self):
        array = []
        current = self.head
        while current:
            array.append(current.data)
            current = current.next
        return array

    def search(self, target):
        current = self.head
        for i in range(self.size):
            if current.data == target:
                return i
            current = current.next
        return None

    def print_list(self):
        current = self.head
        while current:
            if current.next != None:
                print (current.data, '→ ', end='')
            else:
                print (current.data)
            
            current = current.next

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

    # Insert
    S.insert_front('apple')
    S.insert_front('bear')
    S.insert_front('cat')
    S.insert_back('dog', S.head.next)
    S.insert_front('egg')
    S.insert_front('fish')

    # Search
    S.print_list() # fish → egg → cat → bear → dog → apple
    print(f"Index: {S.search('dog')}") # Index: 4
    
    # Delete
    S.delete_front() 
    S.print_list() # egg → cat → bear → dog → apple

    S.delete_back(S.head)
    S.print_list() # egg → bear → dog → apple

    # Traverse
    print (S.traverse()) # ['egg', 'bear', 'dog', 'apple']

 

더블 링크드 리스트 또한 구현을 위해 노드에 정보를 담을 Node 클래스와 기능을 구현할 SinglyLinkedList 클래스가 필요하다. 구현물은 다음과 같다.

 

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

class DoublyLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node(prev=self.head)
        self.head.next = self.tail
        self.size = 0

    def size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_front(self, current, data):
        temp = current.prev
        next = Node(data, temp, current)
        current.prev = next
        temp.next = next 
        self.size += 1 

    def insert_back(self, current, data):
        temp = current.next
        next = Node(data, current, temp)
        temp.prev = next
        current.next = next
        self.size += 1

    def delete(self, current):
        front = current.prev
        back = current.next
        front.next = back
        front.prev = back
        self.size -= 1
        return current.data

    def print_list(self):
        if self.is_empty():
            raise LookupError('There is no node in the linked list')
        else:
            current = self.head.next
            while current != self.tail:
                if current.next != self.tail:
                    print(current.data, '←→ ', end='')
                else:
                    print(current.data)
                current = current.next

D = DoublyLinkedList()
D.insert_back(D.head, 'apple') 
D.insert_front(D.tail, 'bear')
D.insert_front(D.tail, 'cat')
D.insert_back(D.head.next, 'dog')
D.print_list() # apple ←→ dog ←→ bear ←→ cat

D.delete(D.tail.prev)
D.print_list() # apple ←→ dog ←→ bear

D.insert_front(D.tail.prev, 'fish') # apple ←→ dog ←→ bear ←→ fish ←→ cat
D.print_list()

D.delete(D.head.next) # dog ←→ bear ←→ fish ←→ cat
D.print_list()

D.delete(D.tail.prev) # dog ←→ bear ←→ fish
D.print_list()

 

 

Reference

[1] https://reakwon.tistory.com/25

[2] https://daimhada.tistory.com/72

[3] https://it-garden.tistory.com/318

[4] https://it-garden.tistory.com/326