연결리스트 종류
- 단일 연결리스트(Single linked list)
- 이중 연결리스트 (Doubly linked list)
- 원형 연결리스트 (Circular linked list)
- 원형 이중 연결리스트 (Doubly Circular linked list)
단일 연결리스트(Single linked list)
연결리스트의 개념이 궁금하시면 연결리스트가 뭔지 보고 오시면 좋을거 같습니다.
이중(양방향) 연결리스트 (Doubly linked list)
이중 연결리스트는 각 노드가 두 개의 참조를 가지며, 하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킵니다.
이로 인해 리스트를 양방향으로 탐색할 수 있습니다. 이를 파이썬으로 구현하는 경우 Doubly_linked_list 클래스를 사용하여 이를 수행합니다. Node 하위 클래스는 노드를 나타내며, data, pre, next 세 개의 속성을 가집니다.
단일 연결리스트는 단방향 탐색만 가능한 반면 이중 연결리스트는 지나간 노드를 다시 탐색할 수 있다는 장점이 있습니다.
원형 연결리스트 (Circular linked list)
원형 연결리스트는 마지막 노드가 첫 번째 노드를 가리키는 단일 연결 리스트입니다.
이는 리스트를 계속 순환할 수 있게 해줍니다. `
Circular_linked_list클래스를 통해 이를 구현할 수 있습니다. 마찬가지로Node` 하위 클래스를 사용하여 노드를 나타냅니다.
단방향 연결리스트는 삭제와 삽입 연산이 빠르지만 탐색 연산이 느리다는 단점이 있습니다. 특히 head 와 제일 떨어져있는 꼬리 (tail) 노드의 삭제 연산이 최악의 연산입니다.
하지만 원형 연결리스트는 tail의 노드가 head 의 노드를 가리킵니다.
일반적으로 head 로 원형 연결리스트를 나타내기 보다는 tail을 가리키는 노드로 원형 연결리스트를 나타냅니다
원형 연결리스트는 tail을 가리키게 되면 tail에서의 삽입 삭제 연산도 단방향 연결리스트 보다. 효율적입니다.
단방향 연결리스트의 tail 삽입 삭제는 O(n)이지만
원형 연결리스트의 tail 삽입 삭제는 O(1)입니다.
원형 이중 연결리스트 (Doubly Circular linked list)
원형 이중 연결리스트는 이중 연결리스트의 변형입니다.
여기서 첫 번째 노드는 마지막 노드를 가리키고, 마지막 노드는 첫 번째 노드를 가리킵니다. 이는 리스트를 양방향으로 계속 순환할 수 있게 해줍니다.
Doubly_Circular_linked_list 클래스를 통해 이를 구현할 수 있으며, Node 하위 클래스는 노드를 나타냅니다.
원형 연결리스가 단방향보다 효율적이지만 단방향이라는 점 때문에 역 순환이 불가능합니다.
이점을 보완하기 위해 원형 연결리스트와 이중 연결리스트의 개념을 합친 원형 이중 연결리스트라는 개념이 나왔습니다.
하지만 구현이 매우 어렵다는 단점이 있습니다.
코드 구현
각 연결리스트의 삽입 삭제 출력을 클래스화 시켜서 구현해봤습니다.
각 연결리스트 안에 Node 클래스는 각 Node의 구조를 정의한 것입니다.
노드들의 data와 다음 노드를 가리키는 link나 양방향 연결리스트 같은 경우는 next와 pre(previous)로 양방향 노드들을 가리킵니다.
import random
class linked_list:
class Node:
def __init__(self,value):
self.data = value
self.link = None
def __init__(self):
self.head = None
def insert(self,value): # 맨처음에만 삽입
newnode = linked_list.Node(value)
newnode.link = self.head
self.head = newnode
def delete(self,value): ## value값 탐색 후 삭제
if self.head == None:
print("no delete None")
return
previous = None
current = self.head
while(current != None):
if(current.data == value):
break
else:
previous = current
current = current.link
if(previous == None):
# 첫 노드일때
self.head = current.link
elif (current == None):
# 값을 못찾을 때
print("no find")
return
else:
previous.link = current.link
current = None
# 로컬 변수 current 는 어차피 소멸되지만
# 그래도 명시적으로 가비지 컬렉션에 넣는 모습
def display(self):
cur = self.head
if cur == None:
return
while cur != None:
print(cur.data,end = '->')
cur = cur.link
print()
return
class Doubly_linked_list:
class Node:
def __init__(self,value):
self.data = value
self.pre = None
self.next = None
def __init__(self):
self.head = None
def insert(self, value):
newnode = Doubly_linked_list.Node(value)
if self.head is None:
self.head = newnode
else:
self.head.pre = newnode
newnode.next = self.head
self.head = newnode
return
def delete(self,value):
if self.head is None: return
else:
cur = self.head
while(cur != None):
if(cur.data == value):
break
else:
cur = cur.next
if cur == None: return #값이 리스트에 없을때
elif cur == self.head:
if cur.next is None:
# 마지막 노드일때
self.head = None
else:
# 첫번째 노드를 삭제할때
cur.next.pre = None
self.head = cur.next
cur = None
elif cur.next == None:
# 마지막 노드를 삭제할때
cur.pre.next = None
cur = None
else:
#일반적인 경우
cur.pre.next = cur.next
cur.next.pre = cur.pre
return
def display(self):
cur = self.head
while(cur!= None):
print(cur.data,end='->')
cur = cur.next
print()
class Circular_linked_list:
class Node:
def __init__(self,value):
self.data = value
self.link = None
def __init__(self):
self.tail = None
def insert(self,value):
newnode = Circular_linked_list.Node(value)
if self.tail == None:
self.tail = newnode
self.tail.link = self.tail
else:
newnode.link = self.tail.link
self.tail.link = newnode
def delete(self,*value):
if self.tail is None: return
# 매개인자가 없으면 첫번째 원소값 삭제
# 매개인자가 1개 면 그 값을 삭제
if len(value) == 0:
if self.tail == self.tail.link:
self.tail = None
return
else:
current = self.tail.link
self.tail.link = current.link
current = None
return
elif len(value) ==1:
pre = None
cur = self.tail.link
while(pre != self.tail):
if cur.data == value[0]:
break
else:
pre = cur
cur = cur.link
if pre == None:
if cur.data != value[0]:
# 찾는 값이 없을때
return
else:
# 찾는 값이 첫번째 노드 일때
self.delete() # 값이 1개일때도 포함
elif cur == self.tail:
pre.link = cur.link
self.tail = pre
cur = None
return
else:
pre.link = cur.link
cur = None
return
def display(self):
if self.tail == None: return
pre = None
cur = self.tail.link
while(pre != self.tail):
print(cur.data,end= '->')
pre = cur
cur = cur.link
print()
class Doubly_Circular_linked_list:
class Node:
def __init__(self,value):
self.data = value
self.pre = None
self.next = None
def __init__(self):
self.head = None
self.tail = None
def insert(self, value):
newnode = Doubly_linked_list.Node(value)
if self.tail is None:
# 0개의 노드를 가질때
self.head = newnode
self.tail = newnode
self.tail.next = self.head
self.head.pre = self.tail
else:
# 일반적인 경우일때
self.head.pre = newnode
newnode.next = self.head
self.head = newnode
self.tail.next = self.head
self.head.pre = self.tail
return
def delete(self,value):
if self.head is None: return
else:
cur = self.head
while(cur != self.tail):
if(cur.data == value):
break
else:
cur = cur.next
if cur == self.tail:
if cur.data is value:
# tail is value
if self.tail == self.head:
# node 수 1개
self.tail = None
self.head = None
else:
#2개 이상
cur.next.pre = cur.pre
cur.pre.next = cur.next
self.tail = cur.pre
cur = None
else: return # 값을 못찾음
else:
cur.next.pre = cur.pre
cur.pre.next = cur.next
if cur == self.head:
self.head = cur.next
cur = None
def display(self):
if self.head is None: return
cur = self.head
print(cur.data,end='->')
cur = cur.next
while(cur!= self.head):
print(cur.data,end='->')
cur = cur.next
print()
이미지 참고
