Python 자료구조 6.1. 연결된 구조

연결된 구조란?

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

• 용량이 고정되지 않음
• 중간에 자료를 삽입하거나 삭제하는 것이 용이
• n번째 항목에 접근하는데 O(n)의 시간이 걸림

연결리스트의 구조

1. 노드(node)

• 데이터 필드(data field)
• 하나 이상의 링크 필드(link field)

2. 헤드 포인터(head pointer)

• 링크만 가지고 있는 노드, 연결리스트의 첫 번째 노드를 가리킨다.
  

연결리스트의 종류

1. 단순 연결리스트
   

2. 원형 연결리스트
   

3. 이중 연결리스트
   

단순 연결리스트 응용: 연결된 스택

연결 리스트 스택을 사용한다면 스택을 연결리스트로 구성하고 연결 리스트의 어느 쪽을 스택 탑으로 삼을 것인지 결정해주면 된다.

• 삽입 연산
• 삭제 연산
• 모든 노드의 접근

<삽입 연산>

<삭제 연산>

- 메모리 해제를 신경 쓸 필요가 없다!

<전체 노드의 방문>

연결된 스택 구현

# 연결된 스택

class Node:
    def __init__(self):
        self.data = elem
        self.link = link

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)
        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

단순연결리스트 응용: 연결 리스트

• 연결된 리스트 구조

• 노드 클래스 : 연결된 스택에서와 동일

연결 리스트 클래스 구현

# Linked List.
class Node:
    def __init__ (self, elem, next=None):
        self.data = elem 
        self.link = next

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

    def isEmpty( self ): return self.head == None
    def clear( self ) : self.head = None
    def size( self ) :
        node = self.head;
        count = 0;
        while node is not None :
            node = node.link
            count += 1
        return count
    def display(self, msg='LinkedList:' ):
        print(msg, end='')
        node = self.head
        while node is not None :
            print(node.data, end='->')
            node = node.link
        print('None')

    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 replace(self, pos, elem) :
        node = self.getNode(pos)
        if node != None : node.data = elem

    def find(self, val) :
        node = self.head;
        while node is not None:
            if node.data == val : return node
            node = node.link
        return node

    def insertNext(before, node) :
        node.link = before.link;
        before.link = node;
    def deleteNext(before) :
        if before.link != None :
            before.link = before.link.link

    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

#P6.2 ----------
    def merge(self, B) :
        before = self.getNode(self.size()-1)
        if before == None :
            self.head = B.head
        else:
            before.link = B.head
        B.head = None
#---------------

    def printByLine(self):
        print('Line Editor')
        node = self.head
        line = 0
        while node is not None :
            print('[%2d] '%line, end='')
            print(node.data)
            node = node.link
            line += 1
        print()


#======================================================================
s = LinkedList()
s.display('단순연결리스트로 구현한 리스트(초기상태):')
s.insert(0, 10);		s.insert(0, 20);     s.insert(1, 30)
s.insert(s.size(), 40);	s.insert(2, 50)
s.display("단순연결리스트로 구현한 리스트(삽입x5): ")
#s.sort()
#s.display("단순연결리스트로 구현한 List(정렬후): ")
s.replace(2, 90)
s.display("단순연결리스트로 구현한 리스트(교체x1): ")
s.delete(2);	s.delete(s.size() - 1);	s.delete(0)
s.display("단순연결리스트로 구현한 리스트(삭제x3): ")

s2 = LinkedList()
s2.insert(0, 15);       s2.insert(1, 25);       s2.insert(2, 35);

s.merge(s2)
s.display("s 병합후: ")
s2.display("s2병합후: ")

s.clear()
s.display("s  정리후: ")