[자료구조] 6.연결된 구조

연결된 구조

연결된 구조(Linked Structure)는 자료구조의 한 종류로, 데이터를 노드(node)라는 단위로 구성하고, 노드들이 링크(link)를 통해 연결된 형태를 말합니다. 연결된 구조는 배열이나 리스트와 같은 선형 구조보다 복잡한 데이터 구조를 표현하는 데에 적합합니다.

연결된 구조 종류

단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드를 가리키는 링크 하나 만을 가지는 구조
이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리키는 링크 두 개를 가지는 구조
원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 링크를 가지는 구조
스택, 큐, 덱 등: 링크를 이용하여 연산을 수행하는 구조

연결된 구조는 데이터를 삽입하거나 삭제할 때 다른 자료구조와 비교하여 효율적입니다. 예를 들어, 단일 연결 리스트에서는 중간에 새로운 노드를 삽입하거나 삭제할 때, 이전 노드의 링크를 변경하는 것만으로도 구현이 가능합니다. 따라서 선형 구조와 달리 데이터를 삽입하거나 삭제할 때마다 모든 데이터를 이동시키는 것이 필요하지 않습니다.

하지만 연결된 구조는 각 노드의 링크가 메모리 상에 분산되어 저장되기 때문에, 선형 구조에 비해 데이터에 직접적인 접근이 어려울 수 있습니다. 또한 연결된 구조에서는 특정 위치에 있는 데이터를 탐색하기 위해서는 처음부터 노드를 순서대로 탐색해야 하기 때문에, 선형 구조에 비해 탐색 속도가 느릴 수 있습니다.

다양한 연결된 구조의 형태와 특징

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

각 노드(node)가 데이터와 다음 노드를 가리키는 링크(link)를 가지고, 이를 연결하여 구성하는 자료구조입니다. 이 구조에서는 각 노드에 대해 데이터와 다음 노드를 가리키는 링크가 함께 저장됩니다.

단일 연결 리스트는 다음과 같은 특징을 가집니다.

연결 구조: 각 노드가 다음 노드를 가리키는 링크를 가지고, 이를 연결하여 리스트를 구성합니다.
삽입/삭제가 용이: 중간에 새로운 노드를 삽입하거나 삭제할 때, 이전 노드의 링크를 변경하는 것만으로도 구현이 가능합니다.
데이터에 대한 무작위 접근이 어려움: 각 노드의 링크가 메모리 상에 분산되어 저장되기 때문에, 데이터에 직접적인 접근이 어려울 수 있습니다.
단방향 탐색: 각 노드는 다음 노드를 가리키는 링크만을 가지고 있기 때문에, 특정 위치에 있는 데이터를 탐색하기 위해서는 처음부터 노드를 순서대로 탐색해야 합니다.
구현이 간단: 단일 연결 리스트는 구현이 간단하기 때문에, 다른 자료구조를 구현할 때 기본적인 구성요소로 활용됩니다.

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

이중 연결 리스트(Doubly Linked List)는 각 노드(node)가 데이터와 이전 노드, 다음 노드를 가리키는 링크(link)를 가지고, 이를 연결하여 구성하는 자료구조입니다. 이 구조에서는 각 노드에 대해 데이터와 이전 노드를 가리키는 링크, 다음 노드를 가리키는 링크가 함께 저장됩니다.

이중 연결 리스트는 다음과 같은 특징을 가집니다.

양방향 연결 구조: 각 노드가 이전 노드와 다음 노드를 가리키는 링크를 가지고, 이를 양방향으로 연결하여 리스트를 구성합니다.
삽입/삭제가 용이: 중간에 새로운 노드를 삽입하거나 삭제할 때, 이전 노드의 링크와 다음 노드의 링크를 변경하는 것만으로도 구현이 가능합니다.
데이터에 대한 무작위 접근이 양방향으로 용이함: 각 노드의 이전 노드와 다음 노드를 가리키는 링크가 모두 저장되어 있기 때문에, 양방향으로 데이터에 직접적인 접근이 용이합니다.
구현이 복잡: 이중 연결 리스트는 구현이 복잡하기 때문에, 단일 연결 리스트보다는 더 많은 자원이 필요합니다.
단일 연결 리스트보다 기능이 향상됨: 이전 노드를 가리키는 링크를 추가하여, 단일 연결 리스트보다 더 많은 기능을 제공합니다. 예를 들어, 단일 연결 리스트에서는 이전 노드를 탐색하는 것이 어렵지만, 이중 연결 리스트에서는 이전 노드를 가리키는 링크를 활용하여 간단하게 이전 노드를 탐색할 수 있습니다.

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

원형 연결 리스트(Circular Linked List)는 각 노드(node)가 데이터와 다음 노드를 가리키는 링크(link)를 가지고, 마지막 노드가 첫 번째 노드를 가리키는 링크를 가지고 구성된 자료구조입니다.

원형 연결 리스트는 다음과 같은 특징을 가집니다.

마지막 노드와 첫 번째 노드를 연결: 마지막 노드가 첫 번째 노드를 가리키는 링크를 가지고 있어, 원형적으로 연결되어 있습니다.
시작과 끝이 없음: 시작과 끝이 없는 구조이기 때문에, 언제든지 어느 노드에서든 시작점으로 선언 가능합니다.
삽입/삭제가 용이: 중간에 새로운 노드를 삽입하거나 삭제할 때, 이전 노드의 링크와 다음 노드의 링크를 변경하는 것만으로도 구현이 가능합니다.
데이터에 대한 무작위 접근이 어려움: 원형 연결 리스트는 순환 구조이기 때문에, 무작위로 데이터에 접근하기 어렵습니다.
단일 연결 리스트나 이중 연결 리스트보다 기능이 제한적: 시작과 끝이 없는 구조이기 때문에, 리스트의 전체 길이를 구하는 것이 어렵습니다.

원형 연결 리스트는 메모리를 동적으로 할당할 때 많이 사용되며, 순환 구조를 가지고 있어서 삽입/삭제가 용이하다는 장점이 있습니다. 또한, 마지막 노드가 첫 번째 노드를 가리키기 때문에, 리스트의 끝에서 첫 번째 노드로 바로 이동할 수 있어 구현이 간편합니다. 그러나, 데이터에 대한 무작위 접근이 어렵다는 단점이 있습니다. 따라서, 특정한 순서가 필요하지 않은 경우에 주로 사용됩니다.

파이썬을 이용한 연결된 형태의 자료구조 구현

노드

# 노드 클래스
class Node:
    def __init__(self, elem, link=None):
        self.data = elem
        self.link = link

연결된 스택

# 연결된 스택 클래스
class LinkedStack:
    def __init__(self):
        self.top = None
    def isEmpty(self):
        return self.top == None
    def clear(self):
        while self.top is not None:
            temp = self.top
            self.top = self.top.link
            temp = None
    def push(self, item):
        n = Node(item, self.top)
        self.top = n
    def pop(self):
        if not self.isEmpty():
            n = self.top
            self.top = self.n.link
            return n.data
    def size(self):
        node = self.top
        count = 0
        while not node == None:
            node = node.link
            count += 1
        return count

연결 리스트

class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None
    def clear(self):
        while self.head is not None:
            temp = self.head
            self.head = self.head.link
            temp = None
    def size(self):
        node = self.head
        count = 0
        while not node == None:
            node = node.link
            count += 1
        return count
    # pos번째 노드 반환
    def getNode(self,pos):
        if pos < 0:
            return None
        node = self.head
        while pos > 0 and node != None:
            node = node.link
            pos -= 1
        return node
    # pos번째 항목의 데이터만을 반환
    def getEntry(self, pos):
        node = self.getNode(pos)
        if node == None:
            return None
        else:
            return node.data
    # 어떤 위치의 항목을 다른 데이터로 변경
    def replace(self, pos, elem):
        node = self.getNode(pos)
        if node != None:
            node.data = elem
    # 원하는 데이터를 가진 노드를 찾는 함수
    def find(self,data):
        node = self.head
        while node != None:
            if node.data == data:
                return node
            node = node.link
        # 찾아지지 않으면 None(node) 반환
        return node
    # 삽입 연산
    def insert(self, pos, elem):
        before = self.getNode(pos-1)
        if before == None:
            self.head = Node(elem, self.head)
        else:
        	node = Node(elem, before.link)
            before.link = node
    # 삭제 연산
    def delete(self, pos):
        before = self.getNode(pos - 1)
        if before == None:
            if self.head != None:
                self.head = self.head.link
        elif before.link != None:
            before.link = before.link.link

연결된 큐

이중연결리스트 노드

연결된 덱

덱을 이중 연결 리스트로 구현하는 이유

덱(Double-Ended Queue)은 큐와 스택의 기능을 모두 가진 자료구조로, 양쪽 끝에서 데이터를 삽입하거나 삭제할 수 있어야 합니다. 이 때문에 덱을 구현할 때는 이중 연결 리스트(Double Linked List)를 사용하는 것이 일반적입니다.

단일 연결 리스트(Single Linked List)는 각 노드가 다음 노드를 가리키는 링크만을 가지고 있습니다. 따라서, 단일 연결 리스트로 덱을 구현하려면 양쪽 끝에서 데이터를 삽입하거나 삭제하기 위해 항상 리스트의 처음부터 끝까지 순회하면서 원하는 위치를 찾아야 합니다. 이는 매우 비효율적이며, 덱의 기능을 제대로 활용하기 어렵습니다.

반면에 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 링크를 모두 가지고 있어서, 양쪽 끝에서 데이터를 삽입하거나 삭제하는 것이 매우 용이합니다. 이러한 이유로, 덱을 구현할 때는 일반적으로 이중 연결 리스트를 사용합니다.

또한, 이중 연결 리스트는 노드 하나당 링크 2개를 가지고 있어서, 노드 하나당 메모리 사용량이 더 많습니다. 그러나, 이는 덱에서 필요한 기능을 제대로 활용할 수 있도록 하는 데 큰 역할을 합니다. 따라서, 덱을 단일 연결 리스트가 아닌 이중 연결 리스트로 구현하는 것이 일반적입니다.