Programming 기초/Python
[Python 자료구조 #연결리스트1] 단순연결리스트 : 연결된 스택
코딩상륙작전
2023. 5. 22. 21:29
* 연결 리스트
- 용량이 고정되어 있지 않다.
- 삽입과 삭제가 용이하다.
- 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
단순연결리스트로 구현한 리스트(정리후):