개발/Python
Linked List
Velody
2020. 7. 6. 19:23
# Node 클래스 정의
class Node:
def __init__(self, data):
self.data = data
self.next = None
# LinkedList 클래스 (자료구조) 정의
class LinkedList:
# 초기화 메소드
def __init__(self):
dummy = Node("dummy")
self.head = dummy
self.tail = dummy
self.current = None
self.before = None
self.num_of_data = 0
# Head Insert
def append_head(self, data):
new_node = Node(data)
new_node.next = self.head.next
self.head.next = new_node
self.num_of_data += 1
# Index노드 앞로 삽입
# Range 초과, 미만 확인결과 정상 작동
def append_index_before(self, data, index):
# if index is out of list range
if self.is_out_of_range(index):
return
# if index is 0, insert_head
if index <= 0:
self.append_head(data)
return
self.first()
new_node = Node(data)
# Pointer Jump
for i in range(0, index-1):
self.next()
# Actual insertion starts here
new_node.next = self.current.next
self.current.next = new_node
self.num_of_data += 1
# Index노드 뒤로 삽입
# Range 초과, 미만 확인결과 정상 작동
def append_index_next(self, data, index):
# if index is out of list range
if self.is_out_of_range(index):
return
self.first()
new_node = Node(data)
# Pointer Jump
for i in range(0, index):
self.next()
# Actual insertion starts here
new_node.next = self.current.next
self.current.next = new_node
self.num_of_data += 1
# Tail Insert
def append_tail(self, data):
new_node = Node(data)
self.tail.next = new_node
self.tail = new_node
self.num_of_data += 1
# 기본 Delete
def delete(self):
pop_data = self.current.data
if self.current is self.tail:
self.tail = self.before
self.before.next = self.current.next
self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
self.num_of_data -= 1
return pop_data
# 특정 문자 삭제
def delete_string(self, str):
self.first()
# Try to delete first node
if self.num_of_data != 0 and self.current.data == str:
self.delete()
# delete rest of the nodes
while True:
self.next()
if self.current.data == str:
self.delete()
elif not self.current.next:
break
# 특정 인덱스 삭제
def delete_index(self, index):
self.first()
# if index is greater than actual length of list
# end the process
if self.is_out_of_range(index):
return
for i in range(0, self.num_of_data):
if index == i:
self.delete()
return
self.next()
# 여러 인덱스 삭제
# 아직은 중복 인덱스에대해선 처리를 하지 못한다
def delete_multiple_index(self, index):
new_array = []
# check if any of indices are out of range
# leave only indices in correct range
for i in index:
if not self.is_out_of_range(i):
new_array.append(i)
new_array = sorted(new_array, reverse=True)
# perform deleting with indices from new_array
for i in new_array:
self.delete_index(i)
# 인덱스가 리스트보다 크거나 0보다 작은가
def is_out_of_range(self, input):
return (input+1 > self.num_of_data or input < 0)
# first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
def first(self):
if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
return None
self.before = self.head
self.current = self.head.next
return self.current.data
# next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
def next(self):
if self.current.next == None:
return None
self.before = self.current
self.current = self.current.next
return self.current.data
def size(self):
return self.num_of_data
# print method
def print_list(data):
if data:
print(data, end=' ')
while True:
data = l_list.next()
if data:
print(data, end= ' ')
else:
print()
break
if __name__ == "__main__":
l_list = LinkedList()
l_list.append_tail(5)
l_list.append_tail(2)
l_list.append_tail(1)
l_list.append_tail(2)
l_list.append_tail(7)
l_list.append_tail(5)
l_list.append_tail(2)
l_list.append_tail(11)
l_list.append_head(30)
l_list.append_head(20)
print_list(l_list.first())
# test string delete
print()
l_list.delete_string(5)
print_list(l_list.first())
# test index delete
print()
l_list.delete_index(9)
print_list(l_list.first())
# test multiple index delete
print()
l_list.delete_multiple_index([-1, 2, 3, 6, 7, 8, 9])
print_list(l_list.first())
# test insert next
print()
l_list.append_index_next(31, 3)
print_list(l_list.first())
# test insert next
print()
l_list.append_index_before(18, 3)
print_list(l_list.first())