한 방향 연결 리스트

class Node:
	def __init__(self, key=None):
    	self.key = key
        self.next = None
    def __str__(self):
    	return str(self.key) 
        # print(v.key) = 3를 print(v)만 하면 되게끔(실제로는 v.__str__() = "3"이 실행됨)

# linked list 만들기
a = Node(3)
b = Node(9)
c = Node(-1) # [3]->[9]->[-1]->None

a.next = b
b.next = c

이렇게 만들고 head와 size를 잘 적어주면 한 방향 연결리스트 객체를 만든 것이다!

clas SinglyLinkedList:
	def __init__(self):
    	self.head = None
        self.size = 0
    + 삽입 methods, 삭제 methods, 
    + def __len__(self): 
    	return self.size# 노드가 몇 개인지

삽입, 삭제 연산

• 삽입 연산 : push front, push back

push front, push back을 알아볼 것인데, push front는 말 그대로 head node 앞에 새로운 노드를 삽입하는 것이고, push back은 tail node 다음에 새로운 노드를 삽입하는 것이다.

class SinglyLinkedList:
	def __init__(self):
    	self.head = None
        self.size = 0
    def pushFront(self, key):
    	new_node = Node(key)
        new_node.next = L.head
        L.head = new_node
        L.size += 1
    def pushBack(self, key):
    	v = Node(key)
        if len(self)==0: # 빈 리스트이다. 즉 최초의 노드이다.
        	self.head = v
        else: # tail node의 링크를 v로 연결해야 한다. 앞에서 부터 쫓아가서 tail node 찾기
        	tail = self.head
            while tail.next != None:
            	tail = tail.next
            tail.next = v
        self.size += 1
        
        
L = SinglyLinkedList()
L.pushFront(-1) # [-1] -> None
L.pushFront(9) # [9] -> [-1] -> None
L.pushFront(3) # [3] -> [9] -> [-1] -> None
L.pushFront(5) # [5] -> [3] -> [9] -> [-1] -> None

• 삭제 연산 : pop front, popback

def popFront(self):
	if len(self)==0:
    	return None
    else:
    	x = self.head
        key = x.key
        self.head = x.next
        self.size -= 1
        del x
        return key
        
def popBack(self):
	if len(self)==0:
    	return None
    else:
    	# running technique
        prev, tail = None, self.head
        while tail.next != None:
        	prev = tail
            tail = tail.next
        if len(self) == 1:
        	self.head = None
        else:
        	prev.next = tail.next
        key = tail.key
        del tail
        self.size -= 1
		return key
            

정리하자면, pushFront와 popFront는 상수시간 O(1)만에 가능하고, pushBack과 popBack의 경우는 tail node와 prev node를 알아야 하기에 처음부터 n번 쫓아가야 하는 시간이 필요하다. 따라서 O(n)이기에 Front에 비해 Back이 시간이 많이 걸린다.

한 방향 연결 리스트 추가 연산 : 탐색 연산(search) + Generator

def search(self, key): # O(n) 걸린다.
	# key값의 노드를 리턴, 없으면 None 리턴
    v = self.head
    while v != None:
    	if v.key == key:
        	return v
        v = v.next
    return None(or return v)
    

이번에는 Genenrator를 알아보자.

만약 list A = [3,5,-1,9]가 있을 때, 이것들을 모두 출력하려면

for x in A:
	print(x)

로 for+in+리스트 반복하는 액션을 취한다.

그렇다면 순차적 연결 리스트에서는 어떻게 할까?

for x in L:
	print(x)

이와 같이 하면 좋을 것이다. 이것이 자동으로 수행되게 하는 것은 Linked List의 내부 메소드인 iterator가 이 작업을 수행하게 해 준다.

# Generator
def __iterator__(self):
	v = self.head
    while v!= None:
    	yield v # return과 똑같다.
    	v = v.next