연결된 구조란?
- 연결된 구조는 흩어진 데이터를 링크로 연결해서 관리
- 노드 = 데이터(값을 저장) + 링크(다음 노드를 가리킴)
연결된 구조의 특징
- 용량이 고정되지 않음
- 중간에 자료를 삽입하거나 삭제하는 것이 용이 → 시간복잡도: O(1)
- n번째 항목에 접근은 시간이 걸림 → 시간복잡도: O(n)
연결 리스트의 구조
- 노드
- 데이터: 값을 저장
- 링크: 다음 노드를 가리킴
- 헤드 포인터
연결 리스트의 종류
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
단순 연결 리스트 응용: 연결된 스택
class Node: # 노드
def __init__(self, elem, link=None): # 생성자
self.data = elem # 데이터 초기화
self.link = link # 링크 초기화
class LinkedStack:
def __init__(self): # 생성자
self.top = None # top 초기화
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 = n.link
return n.data
def size(self): # 스택의 크기 반환
node = self.top # 시작 노드
count = 0
while not node == None: # node가 None이 아닐 때까지
node = node.link # 다음 노드로 이동
count += 1 # count 증가
return count # count 반환
def peek(self): # 스택의 상단 요소(데이터) 반환
if not self.isEmpty():
return self.top.data
def display(self, msg="LinkedStack: "): # 스택의 상단 요소부터 출력
print(msg, end='')
node = self.top
while not node == None:
print(node.data, end=' ')
node = node.link
print()
단순 연결 리스트 응용: 연결된 리스트
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): # 리스트의 크기 반환
node = self.head
count = 0
while not node == None:
node = node.link
count += 1
return count
def display(self, msg): # 리스트의 맨 앞부터 출력
print(msg, end='')
node = self.head
while not node == None:
print(node.data, end='->')
node = node.link
print("None")
def getNode(self, pos): # 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): # pos번째 노드의 데이터 반환
node = self.getNode(pos)
if node == None:
return None
else:
return node.data
def replace(self, pos, elem): # pos번째 노드의 데이터를 변경
node = self.getNode(pos)
if node != None:
node.data = elem
def find(self, data): # 원하는 데이터를 가진 노드를 반환
node = self.head
while not node == None:
if node.data == data:
return node
node = node.link
return 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 not self.head == None:
self.head = self.head.link
elif before.link != None: # 중간에 있는 노드를 삭제
before.link = before.link.link
원형 연결 리스트 응용: 연결된 큐
class Node: # 노드
def __init__(self, elem, link=None): # 생성자
self.data = elem # 데이터 초기화
self.link = link # 링크 초기화
class CircularLinkedQueue:
def __init__(self): # 생성자
self.tail = None
def isEmpty(self): # 공백상태 검사
return self.tail == None
def clear(self): # 큐를 공백상태로 초기화
self.tail = None
def peek(self): # 큐의 전단 노드의 데이터를 반환
if not self.isEmpty():
return self.tail.link.data
def enqueue(self, item): # 삽입연산
node = Node(item, None)
if self.isEmpty(): # 큐가 공백상태인 경우
node.link = node
self.tail = 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
def size(self): # 큐의 크기 반환
if self.isEmpty():
return 0
else:
count = 1
node = self.tail.link
while not node == self.tail:
node = node.link
count += 1
return count
def display(self, msg="CircularLinkedQueue: "): # 큐의 맨 앞부터 출력
print(msg, end='')
if not self.isEmpty():
node = self.tail.link
while not node == self.tail:
print(node.data, end=' ')
node = node.link
print(node.data, end=' ')
print()
이중 연결 리스트 응용: 연결된 덱
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 isEmpty(self): # 공백상태 검사
return self.front == None
def clear(self): # 덱을 공백상태로 초기화
self.front = self.rear = None
def size(self): # 덱의 크기 반환
node = self.front
count = 0
while not node == None:
node = node.next
count += 1
return count
def display(self, msg="DoublyLinkedDeque: "): # 덱을 맨 앞부터 출력
print(msg, end='')
node = self.front
while not node == None:
print(node.data, end=' ')
node = node.next
print()
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
