[Data Structure] Linked List
Singly Linked List 단일 연결 리스트
- 순차적으로 연결된 공간에 데이터를 나열하는 배열과 달리 링크드 리스트는 떨어진 곳에 존재하는 데이터를 연결해서 관리하는 데이터 구조
- 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원해 줌
- Node = data + link
노드(Node)
- 데이터 저장 단위 (데이터값, 포인터) 로 구성
포인터(pointer)
- 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self, data):
self.head = Node(data)
def add(self, data):
if self.head == '':
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
def delete(self, data):
if self.head == '':
print ('해당 값을 가진 노드 없음')
return
# 경우의 수1: self.head를 삭제해야할 경우 -> self.head를 바꾼 뒤 삭제
if self.head.data == data:
temp = self.head
self.head = self.head.next
del temp
else:
node = self.head
# 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
while node.next:
if node.next.data == data:
temp = node.next
node.next = node.next.next
del temp
pass
else:
node = node.next
def search_node(self, data):
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
장점
- 미리 데이터 공간을 할당 해야 하는 배열과 달리 데이터 공간을 미리 할당하지 않아도 됨
단점
- 연결을 위한 별도 데이터 공간이 필요하므로 저장 공간 효율이 높지 않음
- 데이터를 찾는 시간이 필요하므로 접근 속도가 느림
- 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
Doubly Linked List 이중 연결 리스트
- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
- 단순연결리스트와는 다르게 상수시간 내 역방향 연산이 가능
- Node = data + next_link + prev_link
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class DoublyLinkedList:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert_before(self, data, before_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node == None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.next = node
return True
def insert_after(self, data, after_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.head
while node.data != after_data:
node = node.next
if node == None:
return False
new = Node(data)
after_new = node.next
new.next = after_new
new.prev = node
node.next = new
if new.next == None:
self.tail = new
return True
def insert(self, data):
if self.head == None:
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
Circular Linked List 원형 연결 리스트
- 마지막 노드를 참조하는 last가 단순연결리스트의 head 역할을 함
- 마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있음
- 빈 리스트가 아니면 어떤 노드도 None을 가지고 있지 않아서 프로그램에서 None 조건을 검사하지 않아도 됨
- 비슷한 원리로 Circularly Doubly Linked List도 구현 가능
