자료구조 연결리스트, 한방향 연결리스트 Singly Linked List

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

자료구조 연결리스트 소개 - YouTube

자료구조 한방향연결리스트 - 삽입, 삭제 연산 - YouTube

자료구조 한방향연결리스트 - 탐색 연산 - YouTube

 

배열과는 달리 메모리상에서 흩어져 있음.

실제 데이터값(key)과 값이 저장된 곳의 주소(link)로 구성된 쌍(key, link), 즉 하나의 노드 node를 갖고 있어야 함. 

가장 앞에 있는 노드는 헤드노드 head node

 

배열은 인덱스가 주어지면 상수시간 O(1) 내에 인덱스에 있는 값을 바로 알 수 있다는 것이 장점

연결리스트는 그렇지 않음.

 

하지만 배열은 값을 삽입하거나 삭제할 때 나머지 값에서 인덱스의 이동이 발생함. 최악의 경우에는 O(n)이 듦.

연결리스트에서는 link만 바꿔주면 되니 상수시간 O(1)이 걸림. (그 전 노드와 다음 노드를 알고 있다는 가정 하에)

 

한방향 연결리스트

말 그대로 한방향으로만 연결된 연결리스트. 

 

<노드 클래스 구현>

class Node:
    def __init__(self, key=None):
        self.key = key
        self.next = None
    def __str__(self):
        return str(self.key)

__str__(self) 함수는 print(node)일 경우를 위한 함수이다.

이게 무슨 소리냐면, 우선 노드 v에 3이라는 값이 저장되어 있다고 가정하겠다.

__str__()은 print(v)를 실행했을 때 print(v.key)가 아니더라도 v의 key값이 출력되도록 하는 것이다.

클래스에 __str__() 함수가 정의된 상태에서 print(v)를 실행하면 내부적으로는 print(v.__str__())으로 동작하여 노드 v의 key값이 출력된다.

 

<삽입 연산>

1. pushFront(self, key)

연결리스트의 맨 앞에 값을 삽입

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 빈 리스트는 head가 None을 가리킴
        self.size = 0
    # 삽입 연산
    def pushFront(self, key):
        new_node = Node(key)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

새 노드를 만든 후 그 노드가 기존에 있던 self.head를 가리키도록 함. 

그리고 헤드 노드를 새롭게 삽입된 노드로 업데이트한 후, size를 1 늘린다.

 

2. pushBack(self, key)

연결리스트의 맨 뒤에 값을 삽입

    def pushBack(self, key):
        v = Node(key)
        if self.size == 0:
            self.head = v
        else:
            tail = self.head
            while tail.next != None:
                tail = tail.next
            tail.next = v
        self.size += 1

마찬가지로 새 노드 v를 만든다.

리스트에 아무것도 없을 경우를 고려해야 한다. 이럴 때는 헤드가 새 노드가 된다.

이미 리스트에 어떤 값이 들어있을 경우에는 테일을 헤드로 설정한 후 테일이 가리키는 값이 None이 될 때까지 반복문을 돌며 테일을 찾는다.

테일 노드를 찾았다면 그 테일의 다음 값을 새롭게 삽입한 v로 지정한 후 size를 1 늘린다.

 

<삭제 연산>

1. popFront()

연결리스트의 맨 앞의 값을 삭제 후 리턴

    def popFront(self):
        if self.size == 0:
            return None
        else:
            x = self.head
            key = x.key
            self.head = x.next
            self.size -= 1
            del x
            return key

리스트에 아무것도 들어있지 않다면 None 리턴

x라는 변수를 헤드 노드로 설정하고 key 변수에는 x의 key값을 저장한다.

헤드 노드를 x의 다음 값으로 설정하고 size를 하나 줄인다.

 

대충 그림으로 그려보면 이런 형태

 

2. popBack()

연결리스트의 맨 뒤의 값을 삭제 후 리턴

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

리스트에 아무것도 들어있지 않다면 None 리턴

running technique 활용

prev 노드와 tail 노드 설정 후 반복문을 돌며 None을 가리키고 있는 진짜 tail 노드 찾기

prev 노드는 tail 노드를 쫓아간다. 

 

리스트에 값이 하나 들어있는 경우도 고려해야 함. 

이 때에는 head 노드가 곧 tail 노드임. 

head 노드를 비움. 

그렇지 않은 경우에는 prev 노드의 다음을 None으로 지정함. prev 노드가 tail이 됨. (None을 가리키니까)

 

앞에서 이루어지는 연산, pushFront와 popFront는 O(1)

뒤에서 이루어지는 연산, pushBack과 popBack은 O(n)만큼의 시간이 걸림

--> 연결리스트의 특성상 인덱싱을 바로바로 할 수 없기 때문에 하나하나 돌면서 맨 끝값을 찾아야 하기 때문. 

 

3. remove(x)

구름 실습에서 주어진 연습문제 

입력된 노드를 제거한 후 제거에 성공했으면 True, 실패했으면 False를 리턴함.

    def remove(self, x):
        # 노드 x를 제거한 후 True리턴. 제거 실패면 False 리턴
        if self.size == 0 or x == None:
            # do nothing
            return False
        elif x == self.head:
            L.popFront()
            return True
        else:
            w, v = None, self.head
            while v != None:
                if v == x:
                    w.next = v.next
                    del v
                    self.size -= 1
                    return True
                w = v
                v = v.next
            return False

세 가지 경우로 나뉜다.

1. 리스트가 비어있거나 x가 None인 경우 -> False 리턴

2. x가 첫 번째 노드인 경우 -> popFront를 호출하여 실행 후 True 리턴

3. 그 외의 경우 -> x의 전 노드에 x의 다음 노드를 연결한 후 x를 지우고 size도 줄인 후 True 리턴

 

<탐색 연산>

1. search(self, key)

값을 찾음

    def search(self, key):
        v = self.head
        while v != None:
            if v.key == key:
                return v
            v = v.next
        return None

연결리스트 L이 있다고 가정.

L.search(3)

처음부터 돌면서 key의 값이 3일 경우 노드를 출력

아니라면 다음 노드로 넘어가고 전부 돌았는데도 없다면 None 출력

 

2. __iter__()

iterator, iterable 설명 참고:

Python Iterators (w3schools.com)

38. Iterable 과 Iterator - 파이썬 - 기본을 갈고 닦자! (wikidocs.net)

 

generator 설명 참고:

39. Generator(제네레이터) - 파이썬 - 기본을 갈고 닦자! (wikidocs.net)

 

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

generator를 생성하면 연결리스트에서도 for i in x와 같은 문법이 가능해짐. 

 

 

<한방향 연결리스트 구현 코드>

class Node:
    def __init__(self, key=None):
        self.key = key
        self.next = None
    def __str__(self):
        return str(self.key)


class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 빈 리스트는 head가 None을 가리킴
        self.size = 0
    # 삽입 연산
    def pushFront(self, key):
        new_node = Node(key)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    def pushBack(self, key):
        v = Node(key)
        if self.size == 0:
            self.head = v
        else:
            tail = self.head
            while tail.next != None:
                tail = tail.next
            tail.next = v
        self.size += 1
    # 삭제 연산
    def popFront(self):
        if self.size == 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 self.size == 0:
            return None
        else:
            #running technique
            prev, tail = None, self.head
            while tail.next != None:
                prev = tail
                tail = tail.next
            if self.size == 1:
                self.head = None
            else:
                prev.next = None
            key = tail.key
            del tail
            self.size -= 1
            return key
    def search(self, key):
        v = self.head
        while v != None:
            if v.key == key:
                return v
            v = v.next
        return None
    # for x in L <- 이 문법을 쓸 수 있도록 generator
    def __iter__(self):
        v = self.head
        while v != None:
            yield v
            v = v.next