[자료구조] Single Linked List (단순 연결 리스트) 구현

2021. 1. 11. 13:36Problem Solving/자료구조-알고리즘

Single Linked List (단순 연결 리스트)

파이썬으로 구현 해 보았다.

# Single Linked List
class Node:
def __init__(self, item, next=None):
self.item = item
self.next = next
class SingleLinkedList:
def __init__(self):
self.head = None
self.size = 0
def list_size(self):
return self.size
def is_empty(self):
if self.size != 0:
return False
else:
return True
def select_node(self, idx):
if idx >= self.size:
print("Index Error")
return None
if idx == 0:
return self.head
else:
target = self.head
for cur in range(idx):
target = target.next
return target
def insert_first(self, item):
if self.is_empty():
self.head = Node(item)
else:
self.head = Node(item, self.head)
self.size += 1
def insert(self, item, idx):
if self.is_empty():
self.head = Node(item)
self.size += 1
elif idx == 0:
self.insert_first(self, item)
else:
target = self.select_node(idx - 1)
if target == None:
return
new_node = Node(item)
tmp = target.next
target.next = new_node
new_node.next = tmp
self.size += 1
def delete(self, idx):
if self.is_empty():
print('Underflow: Empty Linked List Error')
return
elif idx >= self.size:
print('Overflow: Index Error')
return
elif idx == 0:
target = self.head
self.head = target.next
del(target)
self.size -= 1
else:
pretarget = self.select_node(idx - 1)
deltarget = pretarget.next
pretarget.next = deltarget.next
del(deltarget)
self.size -= 1
def print_list(self):
target = self.head
while target:
if target.next != None:
print(target.item, '-> ', end='')
target = target.next
else:
print(target.item)
target = target.next
single_linked_list = SingleLinkedList()
print('<insert>')
for i in range(5):
single_linked_list.insert_first(i)
single_linked_list.print_list()
print('size : ', single_linked_list.list_size())
print()
print('<delete>')
for i in range(5):
single_linked_list.delete(0)
single_linked_list.print_list()
print('size : ', single_linked_list.list_size())
"""
<결과>
<insert>
4 -> 3 -> 2 -> 1 -> 0
size : 5
<delete>
3 -> 2 -> 1 -> 0
2 -> 1 -> 0
1 -> 0
0
size : 0
"""

파이썬으로 자료구조 공부를 하진 않았으나, C, C++와 Java를 알고있어서 self와 같은 개념이 별로 어렵게 다가오진 않았다.

self는 Java의 this와 비슷하다고 보면 된다.
Java에선 메소드의 파라미터에 this를 표기하진 않지만 Python에선 메소드의 첫번째 파라미터에 명시하여 사용한다. (self가 아닌 다른 이름도 사용해도 되지만 암묵적으로 이렇게 표기한다.)

 

참고자료

반응형