[자료 및 알고리즘] 6. 연결된 구조 (파이썬)

연결된 구조란?

 

배열 구조 vs 연결된 구조

 

배열 구조

- 모든 데이터를 연속된 메모리 공간에 저장

- n번째 자료의 위치를 금방 찾을 수 있다. O(1)

 

연결된 구조

- 흩어진 데이터를 링크(포인터)로 연결해서 관리

- n번째 자료의 위치를 찾으려면? O(n)

 

연결된 구조의 특징

장점 :

메모리 낭비가 없고 용량이 고정되지 않는다.

중간에 자료를 삽입하거나 삭제하는 것이 용이하다.

 

단점 :

n번째 항목 접근에 O(n)의 시간이 걸린다.

 

노드란?

 

노드(Node)는 데이터와 링크 필드로 나뉘어져 있다.

맨 앞에 있는 노드를 시작 노드(머리 노드)라고 한다.

맨 뒤에 있는 노드를 마지막 노드(꼬리 노드)라고 한다.

 

연결 리스트의 종류

 

- 단순 연결 리스트 : 일자로 연결되어 있음

- 원형 연결 리스트 : 마지막 노드의 링크가 시작 노드를 가리킨다.

- 이중 연결 리스트 : 단순 연결 리스트에서 각 노드가 앞뒤로 연결 되어있음

 

연결된 스택

 

class LinkedStack :
    def __init__(self) :
        self.top = None
        
    def isEmpty(self) : return self.top == None
    
    def isFull(self) : return False
    
    def push(self, e) : self.top = Node(e, self.top)
    
    def pop(self) :
        if not self.isEmpty():
            n = self.top
            self.top = n.link()
            return n.data
            
    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 __str__(self):
        arr = []
        node = self.top
        while not node == None:
            arr.append(node.data)
            node = node.link
        return str(arr)

 

연결 리스트

 

class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self): return self.head == None
    def isFull(self): return False
    
    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
    
    def getEntry(self, pos):
        node = self.getNode(pos)
        if node == None : return None
        else : return node.data
        
    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 is not None: 
                self.head = self.head.link
        elif before.link != None:
            before.link = before.link.link

 

연결된 큐 클래스

 

class LinkedQueue:
    def __init__(self):
        self.tail = None
        
    def isEmpty(self): return self.tail == None
    def isFull(self): return False
    
    def enqueue(self, item):
        node = Node(item. None)
        if self.isEmpty():
            self.tail = node
            node.link = node
        else:
            node.link = self.tail.link
            self.tail.link = node
            self.tail = node
            
    def dequeue(self):
        if not self.isEmpty():
            data = self.tail.link.data
            if self.tail.link == self.tail:
                self.tail = None
            else:
                self.tail.link = self.tail.link.link
            return data

 

연결된 덱 (이중 연결 구조)

 

//이중 연결 구조 노드 클래스
class DNode:
    def __init__ (self, elem, prev = None, next = None)
        self.data = elem
        self.prev = prev
        self.next = next

 

class DoublyLinkedDeque:
    def __init__(self):
        self.front = None
        self.rear = None
        
    /...
    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
            
    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
            
    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
            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