[자료구조] 연결 리스트(Linked List)

1. 연결리스트(Linked List)란

각 노드가 데이터와 포인터를 가지고, 각 노드의 포인터가 다음 노드를 가리키게 하여 한 줄로 연결되도록 데이터를 저장하는 자료구조이다.

연결리스트 추상도

가장 첫 노드는 head, 마지막 노드느 tail이라고 한다.

각 노드의 앞쪽 노드를 전임 노드 (Predecessor Node), 뒤쪽 노드를 후임 노드 (Successor Node) 라고 한다

 

2. 연결리스트 특징(사용하는 이유)

• 데이터를 연속적인 물리 메모리에 저장하지 않아도 된다.
• 배열은 크기가 가변적이지 않기 때문에, 지정한 크기를 넘어가게 될 경우 메모리를 재할당하고, 배열 데이터를 복사하는 작업이 일어나게 되는데 연결리스트는 이러한 작업 없이 독립된 공간에 새로운 데이터를 할당하고 연결만 해주면 된다.
• 탐색은 \(O(n)\), 시작 및 끝 지점에 데이터 삽입/추출 작업은 \(O(1)\)이 소요된다.
• 탐색을 자주 해야 할 경우에는 배열, 데이터 삽입/추출을 자주 해야 할 경우에는 연결 리스트를 사용하는 것이 유리할 것이다.

 

3. 연결리스트 유형

1. 단일 연결 리스트(singly linked list)

후임 노드에 대한 포인터만을 갖는 가장 단순한 연결 리스트 형태이다.  큐를 구현할 때 사용하는 방식이다.

 

2. 이중 연결 리스트(doubly linked list)

단일 연결 리스트는 후임 노드에 대한 포인터만을 갖는 것에 비해, 이중 연결 리스트는 전임, 후임 양 방향에 대한 포인터를 갖고 있다.

 

3. 환형 연결리스트(circular linked list)

단일 연결리스트에서 마지막 노드(tail)가 첫 노드(head)를 가리키는 연결리스트를 말한다. 

 

4. 연결리스트 구현

class ListNode:
    def __init__(self, data, next=None) -> None:
        self.data = data
        self.next = next
    
class SinglyLinkedList:
    def __init__(self) -> None:
        self.head = ListNode(None)
        self.size = 0
        
    def size(self):
        return self.size
    
    def get_node(self, idx):
        if self.size == 0:
            print("It's empty Linked List")
            return
        elif idx + 1 > self.size:
            print("idx is bigger than size")
            return
        
        node = self.head
        for _ in range(idx):
            node = node.next
        return node
    
    def append(self, data):
        if self.size == 0:
            self.head = ListNode(data)
        else:
            node = self.get_node(self.size-1)
            node.next = ListNode(data)
        self.size += 1
    
    def appendleft(self, data):
        if self.size == 0:
            self.head = ListNode(data)
        else:
            node = ListNode(data)
            node.next = self.head
            self.head = node
        
        self.size += 1
    
    def insert(self, data, idx):
        if idx > self.size:
            print("out of range")
            return

        elif idx == 0:
            self.appendleft(data)
        
        else:
            node = self.get_node(idx-1)
            successor = node.next    
            node.next = ListNode(data)
            node.next.next = successor
            self.size += 1
        
    def pop(self):
        out = None
        if self.size == 0:
            print("It's empty Linked List")
            return
        
        elif self.size == 1:
            out = self.head.data
            self.head = ListNode(None)
            
        else:
            node = self.get_node(self.size-2)
            out = node.next.data
            node.next = None

        self.size -= 1
        return out        
            

    def popleft(self):
        if self.size == 0:
            print("It's empty Linked List")
            return
        
        elif self.size == 1:
            out = self.head.data
            self.head = ListNode(None)
        
        else:
            node = self.head
            out = node.data
            self.head = node.next

        self.size -= 1
        return out
        
    
    def delete(self, idx):
        if self.size == 0:
            print("It's empty Linked List")
            return
        
        elif idx >= self.size:
            print("out of range")
            return

        elif self.size == 1:
            self.popleft()
        
        else:
            node = self.get_node(idx-1)
            node.next = node.next.next
        
        self.size -= 1
        return
    
    def print(self):
        node = self.head
        while node:            
            if node.next is not None:
                print(f'{node.data}->', end="")
            else:
                print(f'{node.data}')
            node = node.next
        

linked_list = SinglyLinkedList()
linked_list.print()

linked_list.appendleft(2)
linked_list.print()
linked_list.append(1)
linked_list.print()
linked_list.popleft()
linked_list.print()
linked_list.insert(3,1)
linked_list.print()
linked_list.insert(2,1)
linked_list.print()
linked_list.popleft()
linked_list.print()
linked_list.pop()
linked_list.print()