한방향 연결리스트 및 연산(삽입, 삭제, 탐색)

class Node: #기본 노드 클래스
    def __init__(self, key=None):
        self.key = key
        self.next = None
    def __str__(self): #객체를 호출하면 이 함수가 호출된다.
        return str(self.key)

 

 

 

한방향 연결리스트 (SinglyLinkedList)

=> 노드들이 한 방향으로 연결된 리스트

한방향 연결리스트

head node와 tail 노드가 있고, 특정 key값을 찾는데 걸리는 시간은 가장 앞인 head노드로부터,

 

떨어진 거리의 시간과 같다. 삽입연산(pushFront(), pushBack()) / 삭제연산(popFront(),

 

popBack()) / 탐색연산 / 제거연산 이 있다. 그렇다면, 이 한방향 연결리스트를 구현해보자

 

class SinglyLinkedList:
    def __init__(self): #연결 리스트 생성
        self.head = None
        self.size = 0

한방향 연결리스트의 정의이다. 

 

 

 

2가지 삽입연산(pushFront, pushBack)

def pushFront(self, key):
    new_node = Node(key) #새 노드 생성
    new_node.next = self.head #이 노드는 현재 노드의 이전 노트
    self.head = new_node #이제 self가 가르키는 노드를 삽입된 노드로 변경
    self.size += 1 #추가되었으므로 길이가 증가
def pushBack(self, key):
    new_node = Node(key)#새 노드 생성
    if len(self) == 0: #노드가 없으면
        self.head = new_node #이 생성된 노드가 헤드노드로 삽입된다.
    else:
        tail = self.head
        while tail.next != None: #꼬리를 타고 물고간다 #O(n)
            tail = tail.next
        tail.next = new_node #마지막 노드에 삽입
        self.size += 1

 

 

 

2가지 삭제연산(popFront, 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:
        pre, tail = None, self.head
        while tail.next != None: #꼬리를 물면서 뒤로 이동
            prev = tail
            tail = tail.next
        if prev == None: #기존 노드가 하나만 존재하면
            self.head = None
        else:
            prev.head = None
        key = tail.key
        del tail
        self.size -= 1
        return key

삽입연산과 삭제연산 중에서 앞에서 연산이 일어나는 pushFront와 popFront는 O(1)의

 

시간복잡도로 해결되지만, 테일에서 일어나는 pushBack, popBack 반복문을 돌기때문에

 

O(n)의 시간복잡도를 가진다.

 

탐색연산은 어떨까

 

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

 

탐색연산(search) 또한 head 부터 tail로 반복문을 통해 탐색해나가기 때문에 O(n)

 

의 시간복잡도를 가진다. 이외에도 제거, 제너레이터 등의 연산이 존재한다.