[자료구조] Single Linked List (단순 연결 리스트) 구현
2021. 1. 11. 13:36ㆍProblem 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가 아닌 다른 이름도 사용해도 되지만 암묵적으로 이렇게 표기한다.)
참고자료
반응형
'Problem Solving > 자료구조-알고리즘' 카테고리의 다른 글
[알고리즘] DFS, BFS 구현 (Python) (0) | 2021.01.27 |
---|---|
[자료구조] Circle Deque (원형 덱) 구현 (0) | 2021.01.19 |
[자료구조] Double Linked List (이중 연결 리스트) 구현 (0) | 2021.01.11 |