[Python 자료구조 #연결리스트1] 단순연결리스트 : 연결된 스택

* 연결 리스트

• 용량이 고정되어 있지 않다.
• 삽입과 삭제가 용이하다.
• n번째 항목에 접근하는데 O(n)의 시간이 걸린다.

 

* 연결 리스트 구조

• 노드(node) : 연결된 구조에서 하나의 데이터 상자
• 노드는 데이터 필드(data field)와 하나 이상의 링크 필드(link field)를 갖는다.
• 데이터 필드에는 저장할 데이터가, 링크 필드에는 다른 노드의 주소를 저장하는 변수이다.

 

*헤드 포인터(head pointer)

• 연결 리스트는 첫 번째 노드만 알면 링크로 매달려 있는 모든 노드에 순차적으로 접근할 수 있다. 따라서 시작 노드의 주소를 반드시 저장해야 한다. 연결리스트에서 첫 번째 노드의 주소를 저장하는 변수를 헤드 포인터라고 한다.
• 마지막 노드는 더 이상 연결할 노드가 없으므로 링크의 값을 None으로 설정한다.

 

* 연결리스트 종류

1. 단순 연결리스트(singly linked list)

• 하나의 방향으로만 연결되어 있는 구조를 갖는다.

 

2. 원형연결리스트(circular linked list)

• 단순연결리스트와 동일한 노드 구조이나, 마지막 노드의 링크 값이 None이 아니라 다시 첫 번째 노드를 가리킨다.
• 종료조건에 유의해야 한다.

 

3. 이중연결리스트(doubly linked list)

• 하나의 노드가 이전 노드와 다음 노드를 모두 알고 있도록 설계되었다.
• 두개의 링크를 갖는데, 선행 노드(previous node)를 다른 하나는 후속 노드(next node)를 가리킨다.

 

* 단순연결리스트 응용 : 연결된 스택(linked stack) ADT(추상데이터 타입)

 

출처: 파이썬으로 쉽게 풀어쓴 자료구조

 

출처: 파이썬으로 쉽게 풀어쓴 자료구조

※ 객체를 참조하는 변수가 하나도 없으면 그 객체는 자동으로 삭제된다.

class Node:  # 노드 클래스 생성
    def __init__(self, elem, link=None):	# 링크는 디폴트 인수 기능을 이용해 인수가 전달되지 않으면 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):
        self.top = None

    def push(self, item):  # 삽입
        n = Node(item, self.top)  # 기존 가리키던 top을 새로운 노드가 가리키는 link에 넣음.
        self.top = n  # 헤드포인터에 새로운 노드의 주소를 넣음

    def pop(self):
        if not self.isEmpty():
            n = self.top  # 임시로 top을 새로운 변수(n)에 저장
            self.top = n.link  # 새롭게 top이 될 다음 노드의 주소를 헤드포인터에 저장
            return n.data  # pop된 데이터를 반환

    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, msg="LinkedStack:"):
        print(msg, end="")
        node = self.top
        while not node == None:
            print(node.data, end=" ")
            node = node.link
        print()

 

연결된 스택(linked stack) 적용 예시

odd = LinkedStack()
even = LinkedStack()
for i in range(10):
    if i % 2 == 0:
        even.push(i)
    else:
        odd.push(i)

even.display(" 스택 even push 5회: ")
odd.display(" 스택 odd  push 5회: ")
print(" 스택 even     peek: ", even.peek())
print(" 스택 odd      peek: ", odd.peek())
for _ in range(2):
    even.pop()
for _ in range(3):
    odd.pop()
even.display(" 스택 even  pop 2회: ")
odd.display(" 스택 odd   pop 3회: ")
----------------------------------------------------
 스택 even push 5회: 8 6 4 2 0 
 스택 odd  push 5회: 9 7 5 3 1 
 스택 even     peek:  8        
 스택 odd      peek:  9        
 스택 even  pop 2회: 4 2 0     
 스택 odd   pop 3회: 3 1

 

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

스택과는 달리 리스트는 항목의 삽입이나 삭제가 시작노드뿐만 아니라 임의의 위치에서도 가능하다.

출처: 파이썬으로 쉽게 풀어쓴 자료구조

출처: 파이썬으로 쉽게 풀어쓴 자료구조

 

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


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

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

    def clear(self):
        self.head = None

    def size(self):	# 인덱스가 아닌 크기(1이상의 수)를 반환
        node = self.head
        count = 0
        while not node == None:
            node = node.link
            count += 1
        return count

    def display(self, msg="LinkedList:"):
        print(msg, end="")
        node = self.head
        while not node == None:
            print(node.data, end=" ")
            node = node.link
        print()

    def getNode(self, pos): # 리스트 ADT에 없는 추가된 연산. pos번째 노드를 반환.
        if pos < 0:
            return None
        node = self.head
        while pos > 0 and node != None:
            node = node.link	# 리스트 크기 이상의 pos를 대입해도 마지막 pos까지 감소하고 마지막 노드는 None을 가리키게 된다.
            pos -= 1    # 남은 반복 횟수 줄임
        return node

    def getEntry(self, pos):    # getNode를 이용해서 데이터만 반환하는 getEntry 구현
        node = self.getNode(pos)    # pos번째 노드
        if node == None:    # 찾는 노드가 없는 경우
            return None
        else:
            return node.data    # 그 노드의 데이터 필드 반환

    def replace(self, pos, elem):   # getNode를 이용해서 간단히 구현
        node = self.getNode(pos)    # pos번째 노드를 찾아
        if node != None:    # 데이터 필드에 elem 복사
            node.data = elem

    def find(self, data):   # 원하는 데이터를 가진 노드 찾는 함수.
        node = self.head
        while node is not None:
            if node.data == data:
                return node
            node = node.link
        return node # 못 찾으면 node는 마지막 노드의 None을 갖게 됨.

    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

연결된 리스트 예시

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