Linked List(연결된 구조)

연결된 구조란?

- 흩어진 데이터를 링크로 연결해서 관리하는 구조

- 메모리 낭비가 없고 용량이 고정되지 않음

- 중간에 자료를 삽입 / 삭제 시 용이

- n번째 항목 접근에 O(n)의 시간이 걸림

관련 용어

노드 (node)

- 데이터 필드 + 하나 이상의 링크 필드를 포함한 데이터 세트

- 데이터 필드에는 우리가 저장하고 싶은 자료가 들어감

- 링크 필드는 다른 노드의 주소를 저장하는 변수

시작/꼬리 노드, 헤드 포인터

- Header pointer(헤드 포인터)는 연결 리스트에서 첫 번째 노드의 주소를 저장하는 변수

- 꼬리(마지막) 노드는 link의 값을 None으로 설정하여 이 노드가 마지막임을 표시

Linked List의 종류

단순 연결 구조(singly linked structure)

한 방향으로만 연결된 구조

하나의 노드는 다음 노드의 주소를 기억

마지막 노드의 링크는 None

원형 연결 구조(circular linked structure)

단순 연결 구조와 같은 노드 사용, 맨 마지막 노드의 링크가 첫 번째 노드를 가리킴

따라서 어떤 노드에서 출발해도 다른 모든 노드를 방문할 수 있음

이중 연결 구조(doubly linked structure)

하나의 노드가 이전 노드와 다음 노드를 모두 알고 있도록 설계

단순 연결 구조에 비해 메모리 사용이 비효율적이다

구현 시 고려해야 할 점

- 각 구조마다 사용하는 노드 구현 -> data, link(next, prev) 등

- 자료구조 class의 생성자로 front, size 등 구현

- 구조가 비어있는지 / 차있는지 확인 isEmpty(), isFull()

- 특정 위치의 데이터 반환 getNode()

- 데이터 입력 및 반환+삭제 insert()/push(), delete/pop()

# 단일 노드

#단순 연결 노드 클래스
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# 이중 노드

class DNode:
    def __init__(self, data, prev = None, next = None):  # data:색깔, next:다음 구슬
        self.data = data
        self.prev = prev
        self.next = next

Linked Stack(연결된 스택) 구현

# Linked Stack 클래스

# 단일 노드 사용

#연결된 스택 클래스
class LinkedStack:

    #Linked Stack의 생성자
    def __init__(self):
        self.head = None    #처음 들어오는 Node는 head가 가리킴 (Stack의 최상위 데이터)
        self.size = 0        #node의 갯수

    # 비어있는지 확인
    def isEmpty(self): return self.top == None

    # 다 찼는지 확인 = Linked List는 절대 차지 않음
    def isFull(self): return False

    # 데이터 추가
    def push(self, data):
        node = ListNode(data, self.head)    #self.head를 가리키는 Node 생성
        self.head = Node(e, self.head)        #self.head는 node를 가리킴
        self.size += 1                        #size 1 추가

    # 데이터 삭제
    def pop(self):
        if not self.isEmpty():    # 데이터가 비어있지 않으면
            p = self.head        # 최상단 데이터를 p에 복사
            self.head = p.next    # 상단 다음 노드가 head를 가리키고
            self.size -= 1        # size 1 감소
            return n.data       # n의 data 반환

    # head의 데이터 반환
    def peek(self):
        if not self.isEmpty():
            return self.head.data

    # size값 계산
    def size(self):
        return self.size

    # 자료구조의 모든 데이터 출력
    def display(self):
        p = self.top                                # node 방문을 위한 포인터 역할

        while p != None:                            # p가 None이 될때까지 출력
            print("[%s] -> " % (p.data), end="")
            p = p.next

Linked List 구현

# Linked List 클래스

# 단일 노드 사용

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    # 리스트가 비어있는지 / 차있는지 확인
    def isEmpty(self): return self.head == None
    def isFull(self): return False

    # 원하는 위치의 노드 확인
    def getNode(self, pos):
        if pos <= self.size:        # 원하는 위치 찾기
            p = self.head
            for i in range(1, pos):
                p = p.next
            return p                #데이터 변환
        else:
            print("Invalid Pos at getNode()")
    # 원하는 위치에 노드 추가
    def insert(self, pos, data):
        before = self.getNode(pos-1)
        n = Node(data)
        if before == None:
            self.head = Node(data, self.head)
        else:
            node = Node(data, before.link)
            before.link = node
    # 원하는 위치의 노드 삭제
    def delete(self, pos):
        # 지울 값이 있나 확인
        # pos - 1 위치의 node 불러오기
        # 불러온 node의 link = 지울 값의 link
        before = self.getNode(pos - 1)
        if before == None:                    # 시작 노드를 삭제하는 상황
            if self.head is not None:
                deleteNode = self.head
                self.head = self.head.next
                self.size -= 1
                return deleteNode
            else:
                print("Error: List doesn't have Node")
        elif before.next != None:            # 시작 노드 제외 노드를 삭제하는 상황
            p = before.next
            before.next = p.next
            self.size -= 1
            return p
        else:
            print("Invalid Pos")

Linked Queue (연결된 큐) 구현

#Linked Queue 클래스

# 단일 노드 사용

class LinkedQueue:
    def __init__(self):
        self.size = 0
        # 마지막 노드(꼬리 노드)
        self.tail = None

    # 다 찼는지 / 비어있는지 확인
    def isEmpty(self): return self.size == 0
    def isFull(self): return False

    # 특정 위치의 노드 반환
    def getNode(self, pos):
        if pos <= self.size:
            p = self.tail
            for i in range(0, pos):
                p = p.next
            return p
        else:
            print("Invalid pos!")

    # 노드 추가
    def enqueue(self, data):
        n = Node(data)
        # 자료구조가 비어있을 때
        if self.isEmpty():
        	# 자료구조의 맨 마지막 = n
            self.tail = n 
            # 자료구조의 맨 마지막 + 1의 위치 = 자기자신
            n.next = n
        else:
        	# 자기자신 다음에 첫 노드로 연결
            n.next = self.tail.next
            # 기존 마지막 노드 다음에 자신으로 연결
            self.tail.next = n
            # 자신을 자료구조의 마지막 노드로 설정
            self.tail = n
        self.size += 1

    def dequeue(self):
        if not self.isEmpty():
        	#반환할 데이터 저장
            data = self.tail.next.data
            if self.tail.next == self.tail:    
            	#데이터가 하나밖에 없을 시 -> 데이터 초기화
                self.tail = None
            else:
            	#데이터가 여러개일 시
                self.tail.next = self.tail.next.next
            self.size -= 1
            return data

    def display(self):
        p = self.tail
        
        for i in range(self.size):
            p = p.next
            print("[%s] -> " % (p.data), end="")
        print("\b\b\b")

# 실행 예시
if __name__ == "__main__":
    L = LinkedQueue()
    L.enqueue("A")
    L.enqueue("B")
    L.enqueue("C")
    L.enqueue("D")
    L.display()

    L.dequeue()
    L.display()

Linked Deque 구현

# Linked Deque 클래스

# 이중 노드 사용

 

class DoublyLinkedDeque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0
	
    def isEmpty(self): 
        return self.size == 0

    def isFull(self): 
        return False
    
    # 특정 위치의 노드 반환
    def getNode(self, pos):
        if pos <= self.size:
            p = self.front
            for i in range(0, pos):
                p = p.next
            return p
        else:
            print("Invalid pos!")
        
    def addFront(self, item):
        node = DNode(item, None, self.front)
        if self.isEmpty():
            self.front = self.rear = node
        else:
            self.front.prev = node
            self.front = node
        self.size += 1
            
    def addRear(self, item):
        node = DNode(item, self.rear, None)
        if self.isEmpty():
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node
        self.size += 1
            
    def deleteFront(self):
        if not self.isEmpty():
            data = self.front.data
            self.front = self.front.next
            if self.front == None:
                self.rear = None
            else:
                self.front.prev = None
            self.size -= 1
            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
            self.size -= 1
            return data
            
    def display(self):
        p = self.front
        while p is not None:
            print("[%s] -> " % (p.data), end="")
            p = p.next
        print("\b\b\b")

 

# 실행 예시
if __name__ == "__main__":
    L = DoublyLinkedDeque()
    L.addFront("A")
    L.addFront("B")
    L.addRear("C")
    L.addRear("D")
    L.display()

    L.deleteRear()
    L.deleteFront()
    L.display()