[자료구조] 연결된 구조 (Linked Structure)

앞에서 우리는 스택과 큐, 덱을 구현할 때 배열을 이용했다.
배열을 이용하면 쉽고 간단하게 구현할 수 있어서 편리하지만 일정 크기로 용량이 고정되고 메모리가 불필요하게 낭비된다는 단점이 있다. 이러한 문제점들을 해결할 수 있게 고안된 자료구조가 바로 연결된 구조이다!

 

연결된 구조는 노드(node)를 여러 개 연결시켜 구현하는데, 노드 하나에는 요소를 담는 데이터 필드와 다음 노드를 가리키는 링크 필드를 갖는다.
즉 가장 처음 노드만 알면 링크 필드를 거치고 거쳐 배열을 사용하지 않고도 해당 자료구조의 모든 요소에 접근할 수 있다는 것이다! (물론 n번째 요소에 접근하는 데에는 O(n)이 소요될 것이다)
이 때 가장 처음 노드를 가리키는 변수를 ‘헤드 포인터(head pointer)’라고 한다.

 

연결 리스트의 종류

• 단순 연결 리스트: 하나의 방향으로만 연결되어 있는 구조. 마지막 노드의 링크는 None을 가리킨다.
• 원형 연결 리스트: 하나의 방향으로 연결되어 있지만 마지막 노드가 다시 첫 번째 링크를 가리키는 구조.
• 이중 연결 리스트: 하나의 노드가 다음 노드 뿐 아니라 이전 노드까지 가리킬 수 있는 구조.

---

연결 리스트의 구현

class Node: # 단순 연결 리스트와 원형 연결 리스트의 경우 사용하는 노드
    def __init__(self, data, link = None):
        self.data = data
        self.link = link


class DNode: # 이중 연결 리스트의 경우 사용하는 노드
    def __init__(self, data, prev = None, next = None):
        self.data = data
        self.prev = prev
        self.next = next # 이전 노드의 주소(prev)와 다음 노드의 주소(next) 두 개의 생성 변수를 가진다.

---

단순 연결 리스트의 응용) 연결된 리스트

class LinkedList:
    def __init__(self):
        self.top = None # 헤드 포인터

    def isEmpty(self):
        return self.top == None

    def clear(self):
        self.top = None

    def size(self):
        count = 0
        add = self.top

        while add is not None:
            count += 1
            add = add.link
        return count
            
    def display(self, msg = ""):
        add = self.top

        while add is not None:
            print(add.data, end = " ")
            add = add.link
        print()

    def getNode(self, pos):
        if pos < 0:
            return None

        node = self.top
        while pos > 0 and node != None:
            node = node.link
            pos -= 1

        return node

    def getEntry(self, pos):
        add = sel.getNode(pos)

        if add == None:
            return None
        else:
            return add.data

    def replace(self, pos, elem):
        add = self.getNode(pos)

        if not add == None:
            add.data = elem

    def find(self, data):
        add = self.top
        while not add == None:
            if add.data == data:
                return add
            else:
                add = add.link
        return None

    def insert(self, pos, elem):
        before = self.getNode(pos-1)

        if before == None:
            n = Node(elem, self.top)
            self.top = n
        else:
            n = Node(elem, before.link)
            before.link = n

    def delete(self, pos):
        before = self.getNode(pos-1)

        if before == None:
            if self.top is not None:
                self.top = self.top.link
        else:
            before.link = before.link.link

 

시간복잡도
getNode(pos), getEntry(pos), replace(pos, elem), find(Val): pos번째 노드를 찾아야 하므로 O(n).

insert(pos, elem), delete(pos): before의 위치를 알고 있다면 O(1), 그렇지 않다면 O(n).

 

단순 연결 리스트의 응용) 연결된 스택

class LinkedStack:
    def __init__(self):
        self.top = None

    def isEmpty(self):
        return self.top == None

    def clear(self):
        self.top = None

    def push(self, item):
        n = Node(item, self.top) # top에 있는 주소값을 n.link로 준다.
        self.top = n # top의 값을 n의 주소값으로 변경한다.

    def pop(self):
        if not self.isEmpty():      
            n = self.top # top에 있던 삭제할 노드의 주소(첫번째 노드 주소)를 미리 저장해둔다.
            self.top = n.link # top을 2번째 노드의 주소로 바꾼다.
            return n.data # 미리 저장해둔 n을 통해 삭제한 노드의 값을 반환한다.

    def peek(self):
        if not self.isEmpty():
            return self.top.data

    def size(self):
        node = self.top
        count = 0
        while not node == None:
            node = node.link
            count += 1
        return count

    def display(self):
        node = self.top
        while not node == None:
            print(node.data, end=' ')
            node = node.link

 

시간복잡도
size(), display(): O(n)
그 외 모든 연산: O(1)

 

원형 연결 리스트의 응용) 연결된 큐

class CircularQueue:
    def __init__(self):
        self.tail = None

    def isEmpty(self):
        return self.tail == None

    def clear(self):
        self.tail = None

    def peek(self):
        if not self.isEmpty():
            return self.tail.link.data

    def enqueue(self, elem):
        n = Node(elem, None)
        
        if self.isEmpty():
            n.link = n # self.tail.link = n 이렇게 하면 안되는 게 tail보다 위에 선언돼서...
            self.tail = n
        else:
            n.link = self.tail.link # 이제 내가 맨 마지막이니 맨 처음 가리키게 해야한다.
            self.tail.link = n # 원래 맨 마지막이었던 애(내 앞에)가 날 가리키게 한다.
            self.tail = n # tail이 날 가리키게 한다.

    def dequeue(self):
        if not self.isEmpty():
            a = self.tail.link
            if self.tail.link == self.tail: # 하나밖에 없을 때 잘 생각해라!
                self.tail = None
            else:
                self.tail.link = self.tail.link.link
            return a.data

    def size(self):
        if not self.isEmpty():
            count = 1
            add = self.tail.link
            while add is not self.tail:
                add = add.link
                count += 1
        else:
            return 0

    def display(self):
        if not self.isEmpty():
            add = self.tail.link
            while not add == self.tail:
                print(add.data, end=" ")
                add = add.link
            print(add.data, end=" ") # self.tail.data는 출력이 안 됐으니까 그걸 출력해준다.
            print()

 

시간복잡도
enqueue(elem), dequeue(): O(1)
size(), display(): O(n)

 

이중 연결 리스트의 응용) 연결된 덱

class DLDeque:
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        return self.front == None
    def clear(self):
        self.front = None
        self.rear = None
    def size(self):
        if self.isEmpty():
            return 0
        else:
            count = 1
            add = self.front
            while add is not self.rear:
                add = add.next
                count += 1
            return count
    def display(self):
        if not self.isEmpty():
            add = self.front
            while add is not self.rear:
                print(add.data, end=" ")
                add = add.next
            print(add.data)
            print()
    
    def addFront(self, e):
        node = Node(e, None, self.front)
        if self.isEmpty():
            self.rear=self.front=node
        else:
            self.front.prev = node
            self.front = node

    def addRear(self, e):
        node = Node(e, self.rear, None)
        if self.isEmpty():
            self.rear=self.front=node
        else:
            self.rear.next = node
            self.rear = node

    def deleteFront(self):
        if not self.isEmpty():
            data = self.front.data
            self.front = self.front.next
            if self.front == None: # 이제 더 없을 경우
                self.rear = None # rear도 None으로
            else:
                self.front.prev = None
            return data

    def deleteRear(self):
        if not self.isEmpty():
            data = self.rear.data
            self.rear = self.rear.prev

            if self.rear == None:
                self.front = None
            else:
                self.rear.next == None
            return data

 

작성일자: 2023-03-06