연결된 구조란?
- 흩어진 데이터를 링크로 연결해서 관리하는 구조
- 메모리 낭비가 없고 용량이 고정되지 않음
- 중간에 자료를 삽입 / 삭제 시 용이
- n번째 항목 접근에 O(n)의 시간이 걸림
관련 용어
노드 (node)
- 데이터 필드 + 하나 이상의 링크 필드를 포함한 데이터 세트
- 데이터 필드에는 우리가 저장하고 싶은 자료가 들어감
- 링크 필드는 다른 노드의 주소를 저장하는 변수
시작/꼬리 노드, 헤드 포인터
- Header pointer(헤드 포인터)는 연결 리스트에서 첫 번째 노드의 주소를 저장하는 변수
- 꼬리(마지막) 노드는 link의 값을 None으로 설정하여 이 노드가 마지막임을 표시
Linked List의 종류
단순 연결 구조(singly linked structure)
한 방향으로만 연결된 구조
하나의 노드는 다음 노드의 주소를 기억
마지막 노드의 링크는 None
원형 연결 구조(circular linked structure)
단순 연결 구조와 같은 노드 사용, 맨 마지막 노드의 링크가 첫 번째 노드를 가리킴
따라서 어떤 노드에서 출발해도 다른 모든 노드를 방문할 수 있음
이중 연결 구조(doubly linked structure)
하나의 노드가 이전 노드와 다음 노드를 모두 알고 있도록 설계
단순 연결 구조에 비해 메모리 사용이 비효율적이다
구현 시 고려해야 할 점
- 각 구조마다 사용하는 노드 구현 -> data, link(next, prev) 등
- 자료구조 class의 생성자로 front, size 등 구현
- 구조가 비어있는지 / 차있는지 확인 isEmpty(), isFull()
- 특정 위치의 데이터 반환 getNode()
- 데이터 입력 및 반환+삭제 insert()/push(), delete/pop()
# 단일 노드
#단순 연결 노드 클래스
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next# 이중 노드
class DNode:
def __init__(self, data, prev = None, next = None): # data:색깔, next:다음 구슬
self.data = data
self.prev = prev
self.next = nextLinked Stack(연결된 스택) 구현
# Linked Stack 클래스
# 단일 노드 사용
#연결된 스택 클래스
class LinkedStack:
#Linked Stack의 생성자
def __init__(self):
self.head = None #처음 들어오는 Node는 head가 가리킴 (Stack의 최상위 데이터)
self.size = 0 #node의 갯수
# 비어있는지 확인
def isEmpty(self): return self.top == None
# 다 찼는지 확인 = Linked List는 절대 차지 않음
def isFull(self): return False
# 데이터 추가
def push(self, data):
node = ListNode(data, self.head) #self.head를 가리키는 Node 생성
self.head = Node(e, self.head) #self.head는 node를 가리킴
self.size += 1 #size 1 추가
# 데이터 삭제
def pop(self):
if not self.isEmpty(): # 데이터가 비어있지 않으면
p = self.head # 최상단 데이터를 p에 복사
self.head = p.next # 상단 다음 노드가 head를 가리키고
self.size -= 1 # size 1 감소
return n.data # n의 data 반환
# head의 데이터 반환
def peek(self):
if not self.isEmpty():
return self.head.data
# size값 계산
def size(self):
return self.size
# 자료구조의 모든 데이터 출력
def display(self):
p = self.top # node 방문을 위한 포인터 역할
while p != None: # p가 None이 될때까지 출력
print("[%s] -> " % (p.data), end="")
p = p.nextLinked List 구현
# Linked List 클래스
# 단일 노드 사용
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
# 리스트가 비어있는지 / 차있는지 확인
def isEmpty(self): return self.head == None
def isFull(self): return False
# 원하는 위치의 노드 확인
def getNode(self, pos):
if pos <= self.size: # 원하는 위치 찾기
p = self.head
for i in range(1, pos):
p = p.next
return p #데이터 변환
else:
print("Invalid Pos at getNode()")
# 원하는 위치에 노드 추가
def insert(self, pos, data):
before = self.getNode(pos-1)
n = Node(data)
if before == None:
self.head = Node(data, self.head)
else:
node = Node(data, before.link)
before.link = node
# 원하는 위치의 노드 삭제
def delete(self, pos):
# 지울 값이 있나 확인
# pos - 1 위치의 node 불러오기
# 불러온 node의 link = 지울 값의 link
before = self.getNode(pos - 1)
if before == None: # 시작 노드를 삭제하는 상황
if self.head is not None:
deleteNode = self.head
self.head = self.head.next
self.size -= 1
return deleteNode
else:
print("Error: List doesn't have Node")
elif before.next != None: # 시작 노드 제외 노드를 삭제하는 상황
p = before.next
before.next = p.next
self.size -= 1
return p
else:
print("Invalid Pos")Linked Queue (연결된 큐) 구현
#Linked Queue 클래스
# 단일 노드 사용
class LinkedQueue:
def __init__(self):
self.size = 0
# 마지막 노드(꼬리 노드)
self.tail = None
# 다 찼는지 / 비어있는지 확인
def isEmpty(self): return self.size == 0
def isFull(self): return False
# 특정 위치의 노드 반환
def getNode(self, pos):
if pos <= self.size:
p = self.tail
for i in range(0, pos):
p = p.next
return p
else:
print("Invalid pos!")
# 노드 추가
def enqueue(self, data):
n = Node(data)
# 자료구조가 비어있을 때
if self.isEmpty():
# 자료구조의 맨 마지막 = n
self.tail = n
# 자료구조의 맨 마지막 + 1의 위치 = 자기자신
n.next = n
else:
# 자기자신 다음에 첫 노드로 연결
n.next = self.tail.next
# 기존 마지막 노드 다음에 자신으로 연결
self.tail.next = n
# 자신을 자료구조의 마지막 노드로 설정
self.tail = n
self.size += 1
def dequeue(self):
if not self.isEmpty():
#반환할 데이터 저장
data = self.tail.next.data
if self.tail.next == self.tail:
#데이터가 하나밖에 없을 시 -> 데이터 초기화
self.tail = None
else:
#데이터가 여러개일 시
self.tail.next = self.tail.next.next
self.size -= 1
return data
def display(self):
p = self.tail
for i in range(self.size):
p = p.next
print("[%s] -> " % (p.data), end="")
print("\b\b\b")# 실행 예시
if __name__ == "__main__":
L = LinkedQueue()
L.enqueue("A")
L.enqueue("B")
L.enqueue("C")
L.enqueue("D")
L.display()
L.dequeue()
L.display()Linked Deque 구현
# Linked Deque 클래스
# 이중 노드 사용
class DoublyLinkedDeque:
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def isEmpty(self):
return self.size == 0
def isFull(self):
return False
# 특정 위치의 노드 반환
def getNode(self, pos):
if pos <= self.size:
p = self.front
for i in range(0, pos):
p = p.next
return p
else:
print("Invalid pos!")
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
self.size += 1
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
self.size += 1
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
self.size -= 1
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
self.size -= 1
return data
def display(self):
p = self.front
while p is not None:
print("[%s] -> " % (p.data), end="")
p = p.next
print("\b\b\b")
# 실행 예시
if __name__ == "__main__":
L = DoublyLinkedDeque()
L.addFront("A")
L.addFront("B")
L.addRear("C")
L.addRear("D")
L.display()
L.deleteRear()
L.deleteFront()
L.display()728x90
'학교생활' 카테고리의 다른 글
| 6. Linked List(연결된 구조) 문제풀이 (0) | 2024.05.31 |
|---|