[Datastructure] 한방향 연결리스트

업데이트: October 29, 2021

태그: computer science, data structure, python, singly linked list

연결리스트란

연결리스트는 파이썬의 리스트와는 다르게 key값과 link값으로 이루어져있다.

리스트는 각 인덱스가 메모리가 할당되어 각 원소의 주소값을 가지게된다. 그래서 상수시간 O(1) 내에 연산이 가능하다.

하지만 연결리스트는 각 메모리가 원소의 주소(key값) + 다음값이 저장된 주소(link값) 이 저장되어 있다.
key값과 link값이 함께 저장되어 있는 것을 Node라고 부른다.

class Node:
    def __init__(self, key = None): 
        self.key = key #노드의 키값
        self.next = None #노드의 링크값, 별도로 설정하지 않는다면 초기값은 none

    def __str__(self):
        return str(self.key) #키값 호출 시, print(self.key) 대신에 print(self) 로 바로 키값출력이 가능하도록 하는 메서드

특징

단점

연결리스트는 배열처럼 인덱스로 접근이 불가능하다.
따라서 우리가 만약에 연결리스트의 3번 인덱스 값을 찾고싶다면, head노드(노드의 맨 첫번째 값)의 링크부터 따라서 들어가야하므로 head->1->2->3으로 총 3번의 계산이 필요하다.
만약 100번 인덱스 값을 찾고 싶다면, 100번의 계산이 필요하므로 연결리스트의 시간복잡도는 O(N)이 된다.

장점

연결리스트의 장점도 있다.
일반적인 리스트가 insert를 하게되면 새로운 값을 맨 앞에 넣는다는 가정하에, 뒤의 모든 값을 밀어내야하므로 시간복잡도는 O(N)인데 반해,
연결리스트는 head node를 새로 만들어 link값을 이전 head node의 주소를 가리키면 되므로 시간 복잡도는 O(1)이다.

한방향 연결리스트

노드들이 self.next 링크를 따라 한방향으로 연결된 리스트이다.
맨 앞의 노드를 head.node라 하고, head node를 알면 그 뒤의 모든 노드들을 찾을 수 있기때문에 연결리스트를 대표하는 노드이다.
맨 마지막 노드는 self.next가 none을 저장한다.

class SinglyLinkedList:
    def __init__(self): #리스트 생성시 자동호출메서드
        self.head = None #초기 head값은 none
        self.size = 0 #리스트의 노드의 개수

    def __iter__(self): #이터레이터 호출시 자동호출함수()
        v = self.head #v에 head node 키값설정
        while v != None: #head node가 none이 아닐때(빈 리스트가 아닐때)
            yield v
            v = v.next

    def __str__(self): #str호출시 자동호출함수
        return "->".join(str(v) for v in self) #인스턴스 내의 

    def __len__(self):
        return self.size #인스턴스의 노드개수 리턴

지원연산

pushfront

현재 head node 앞에 새로운 node을 삽입해야하므로, 새로운 노드가 head node가 된다.
새로운 node의 next값은 이전의 head node가 된다.
연결리스트의 전체 사이즈가 1 커진다.

def pushfront(self, key):
    new_node = Node(key) #key값 가진 새로운 노드 생성
    new_node.next = self.head #새로운 노드의 next는 원래 head값인 self.head임
    self.head = new_node #self.head 는 새로운 노등니 new_node가 된다.
    self.size += 1

pushback

빈 리스트에 pushback은 새로운 노드는 head node가 된다.
.next가 none인 노드가 tail node가 된다. tail node 다음 값으로 주어진 node를 생성해 넣어야한다.
이를 찾기 위해서는 head node로 먼저 접근해 .next가 none인 노드를 찾는 과정이 필요하다.

def pushback(self, key):
    new_node = Node(key)
    if self.size == 0: #현재 연결리스트가 비어있는 경우
        self.head = new_node #연결리스트의 head node는 new_node가 된다.
    
    else:
        tail = self.head #tail node찾기 위해 tail에 self.head를 지정
        while tail.next != None: #tail.next 가 none이 아니라면
            tail = tail.next #tail에 tail.next(self.head.next)를 지정하고 다시 while문 반복
        tail.next = new_node #while문 끝나면 tail에 연결리스트의 마지막값이 들어와있으므로 다음값에 새로운 노드 new_node 연결
    self.size += 1

popfront

빈 리스트의 경우, popfront 불가능
popfront 이후 self.head는 self.head.next가 되어야한다.
popfront는 원래 self.head를 리턴해야한다.

def popfront(self):
        if self.size == 0:
            return None
        else:
            x = self.head #|node(4)를 x 변수에 복사
            key = x.key#|key 는 node(4)의 key인 4
            self.head = x.next #|node(4).next = node(5)이므로 self.head 는 node(5)가 된다.
            del x #|node(4) 객체 자체를 메모리에서 제거
            self.size -= 1
            return key

popback

popback은 맨 뒤 tail의 key값을 리턴해야한다.
tail의 이전값을 prev값으로 설정하는데, prev.next는 None이된다(.next가 none이라는건 리스트의 마지막 노드라는 의미)
리스트의 노드가 없을때, 1개일때, 2개 이상일때로 나뉜다.
노드가 없을때는 연산을 실행하지 않는다.
노드가 1개일때, self.head이자 tail의 key값을 리턴하면된다, 그리고 리스트가 비워질 것이므로 self.head를 none으로 설정한다.
노드가 2개 이상이라면, tail은 삭제될 것이므로 prev.next = none이 되어야한다.

def popback(self):
    if self.size == 0: #노드가 0개인 경우
        return None

    else:
        prev, tail = None, self.head #prev에 tail을 지정해나가면서 tail.next가 none인걸 찾는다.
        while tail.next != None: #노드가 1개인 경우
            prev = tail
            tail = tail.next

        if prev == None:  #while 연산이 끝났는데, prev가 none인건 노드가 1개일때밖에 없다.
            self.head == None #pop하면 리스트가 비워지므로 self.head를 None으로 만들어 
        else:
            prev.next = None #노드가 2개이상인 경우, prev 노드가 마지막노드가 되므로 prev의 next(링크)를 지운다.

        key = tail.key
        del tail
        self.size -= 1
        return key

search

찾고자하는 key값을 가진 node를 리턴해야한다. 없으면 none을 리턴한다.
1가지 방법은 while루프를 부르는 방법이있고,
다른 방법은 for 루프를 돌리는거다.

def search(self, key):
    x = self.head #연결리스트의 헤드노드를 x에 할당
    while x != None: #x가 none 아닌동안, 즉 연결리스트의 헤드부터 끝까지 
        if x.key = key: #만약 x의 키값이 찾고자하는 키값이라면
            return x #x 노드를 리턴한다.
        x = x.next #찾고자하는 키값이 아니라면 x에 다음 노드를 할당한다.
    return x (or None)#x가 none이되면 즉, 연결리스트의 끝값 +1이되면 x는 none이되는데, (x.next가 none이므로) none을 리턴하게된다.

remove

delete의 경우 3가지로 나뉜다

연결리스트의 길이가 0인 경우
지우고자하는 값이 headnode인 경우->popfront
연결리스트의 길이가 0이 아니면서 지우고자하는 값이 headnode가 아니라면 연결리스트에서 중간, 뒤에 있는 값을 의미한다.
3의 경우, popback처럼 prev찾아야하며, prev.next를 tail.next에 연결하면 지우고자하는 키값을 가진 노드는 연결리스트에서 배제된다.
배제된 노드는 삭제하고(tail), popfront와 달리 리스트의 사이즈를 줄이는 명령이 없으므로 별도로 self..size -= 1을 실행해줘야한다.

def remove(self, key):
        if self.size == 0: #연결리스트 길이 0인 경우
            return None

        elif self.head.key == key: #리스트의 헤드노드와 찾고자하는 노드의 키가 같은경우
            self.popfront() #popfront로 다음 노드를 헤드노드로 변경, 본래 헤드노드삭제

        else:
            prev, tail = None, self.head #초기값설정
            while tail.next != None: #tail.next가 none이 아닌동안
                prev = tail #prev와 tail을 한칸씩 옮겨가기
                tail = tail.next
                if tail.key == key: #만약 tail.key와 찾고자하는 키가 같다면
                    prev.next = tail.next #remove할 node의 링크를 지워버리면된다.
                    del tail #tail node를 리스트 상에서 삭제
                    self.size -= 1 #한개 삭제되었으므로 리스트 길이 1개 줄인다.
                    break

reverse

각 노드의 .next를 이전노드로 설정해야한다.
prev, tail로 작서앟자.
while문 탈출하고나선 리스트의 head노드를 변경해주자.

def reverse(self):
    a, b = None, self.head

    while b:
        if b:
            c = b.next #c에 b의 다음노드를 복사
            b.next = a #b의 링크를 반대로 설정
        a = b
        b = c

iter에 대해서

def __iter__(self): #
        v = self.head #
        while v != None: #
            yield v
            v = v.next

위 함수를 genarator라고 하는데, 연결리스트의 인스턴스에게 for문을 사용할 수 있게 해준다.
원래 연결리스트클래스의 인스턴스는 iterator가 없다면

for i in linkedlist:
    print(i)

를 할 경우, 에러가 나게 된다. 연결리스트에서는 일반적인 배열처럼 iter를 할 원소가 없기 때문이다.
이를 가능하게 해주는게 스페셜메서드로 __iter__(self)이다.
그리고 이 메서드처럼 yield가 있는 함수를 generator라고 부른다.

파이썬에서 인스턴스에 for문을 돌린다고 인지를 하게되면
인스턴스에 선언된 클래스에서 __iter__(self)를 자동으로 호출한다.
__iter__는 yeild로 v를 리턴한다.
while 문에서 v는 자동으로 다음 값이 할당된다.
yeild된 값은 for문의 원소로 리턴이 가능하게된다.
다시 for문이 호출되고, 다음 v가 리턴되게된다.
만약 while문이 종료되고 __iter__(self)에서 yeild가 명령되지 않으면 자동으로 StopIterator Errormessage가 출력되면서 for문이 종료된다.

엘비