8장 연결 리스트

리스트란?

순서가 있는 데이터를 늘어놓은 자료구조를 말한다.
종류로는 선형리스트와 연결리스트가 있다.

1. 단순 배열 연결리스트

단순 배열로 연결 리스트를 만들 경우 삽입, 삭제할 때마다 뒤에 데이터를 모두 옮겨야 하므로 효율적이지 않다.

2. 포인터를 이용한 연결 리스트

연결 리스트에서 각각의 원소를 노드라고 한다. 이 노드는 데이터와 다음 노드를 가르키는 포인터로 이뤄져 있다.
그래서 일반적인 경우 이러한 방법으로 연결 리스트를 구현한다.

class Node:  
    def __init__(self, val):  
        self.val = val  
        self.next = None  

def printNode(node):  
    while node is not None:  
        print(node.val, end = ' ')  
        node = node.next  
    print()  

class SLinkedList:  
    def __init__(self):  
        self.head = None  
        self.current = None  
        self.no = 0  

    def __len__(self):  
        return self.no  

    def addHead(self, val):  
        node = Node(val)  
        node.next = self.head  
        self.head = self.current = node  
        self.no += 1  

    def addTail(self, val):  
        if self.head is None:  
            self.addHead(val)  
        else:  
            new_node = Node(val)  
            node = self.head  
            while node.next is not None:  
                node = node.next  
            node.next = self.current = new_node  
        self.no += 1  

    def search(self, val) -> int:  
        node = self.head  
        cnt = 0  
        while node is not None:  
            if node.val == val:  
                return cnt  
            node = self.current = node.next  
            cnt += 1  
        return -1  

    def removeHead(self):  
        if self.head is not None:  
            self.head = self.current = self.head.next  
            self.no -= 1  

    def removeTail(self):  
        if self.head is not None:  
            if self.head.next is None:  
                self.removeHead()  
            else:  
                # singleLinkedList라서 2개의 포인터가 필요하다.  
                # self.current가 마지막에 위치하고 있다면 어차피 사용 못하니 self.head로 한 것 같다.  
                # self.current.next is not None인 경우 밑에와 같이 사용해도 무방하다.  
                ptr = pre = self.head  

                while ptr.next is not None:  
                    pre = ptr  
                    ptr = ptr.next  
                pre.next = None  
                self.current = pre  
                self.no -= 1  

    def removeValue(self, val):  
        if self.head is None:  
            return  
        ptr = self.head  
        if ptr.val == val:  
            self.removeHead()  
            return  
        while ptr is not None:  
            if ptr.val == val:  
                self.current.next = ptr.next  
                self.no -= 1  
                return  
            self.current = ptr  
            ptr = ptr.next  

    def remove(self, node):  
        if self.head is not None:  
            if node is self.head:  
                self.removeHead()  
            else:  
                ptr = self.head  
                while ptr.next is not node:  
                    ptr = ptr.next  
                    if ptr is None:  
                        return  
                ptr.next = node.next  
                self.current = ptr  
                self.no -= 1  

    def next(self) -> bool:  
        if self.current is None or self.current.next is None:  
            return False  
        self.current = self.current.next  
        return True  

    def removeCurrentNode(self):  
        if self.head == self.current:  
            self.removeHead()  
        else:  
            # remove함수를 사용한다. 이 함수는 노드를 삭제하는 함수이다.  
            self.remove(self.current)  


    def clear(self):  
        # self.head = None 왜 이것을 사용 안하는거지?  
        while self.head is not None:  
            self.removeHead()  
        self.current = None  
        self.no = 0  

    def printCurrentNode(self):  
        if self.current is None:  
            print("현재 위치 노드가 없습니다.")  
        else:  
            print(self.current.val)  

    def printNode(self):  
        node = self.head  
        while node is not None:  
            print(node.val, end = ' ')  
            node = node.next  
        print()

연결 리스트 구현 시 주의할 점

삽입, 삭제 시 오버플로우, 언더플로우를 조심한다.
연결 리스트에 원소가 없는 경우, 원소가 1개 있는 경우, 원소의 맨 앞 또는 맨 뒤를 삭제할 때 를 특히 주의해야 한다.

3. 커서를 이용한 연결 리스트

각 노드를 배열 안의 원소에 저장하고 원소를 잘 이용하여 연결 리스트로 구현하는 방법

커서를 이용한 연결 리스트는 데이터 자체의 순서를 나타내는 연결 리스트와 프리 리스트와 결합하므로 이러한 필드가 추가 되어 있다.
노드 클래스
- dnext : 프리 리스트의 뒤쪽 포인터

연결 리스트 클래스
- deleted : 프리 리스트의 머리 노드를 참고하는 커서
- max : 배열에서 맨 끝 쪽에 저장되는 노드의 레코드 번호

언제 사용하는가?

커서를 이용한 연결 리스트는 두가지가 충족될 때 사용한다면 메모리를 많이 아끼며 연결 리스트를 만들 수 있다.

1. 데이터 개수가 크게 변하지 않음
2. 데이터 최대 개수를 예측할 수 있음

프리 리스트란?

삭제된 레코드 그룹을 관리할 때 사용하는 자료구조이다.
앞에서 삭제를 할 경우 배열이 비어있는 문제를 해결할 수 있다.
노드 클래스와 연결 리스트 클래스에는 이와 같은 필드가 추가되어 있다.

구현

from __future__ import annotations  
from typing import Any, Type  
NULL = -1  
class Node:  
    def __init__(self, data = NULL, next = NULL, dnext = NULL):  
        self.data = data  
        self.next = next  
        self.dnext = dnext  

class ArrayLinkedList:  
    def __init__(self, capacity):  
        self.head = NULL  # 헤더 노드  
        self.current = NULL  # 주목 노드  
        self.max = NULL  # 사용 중인 꼬리 레코드 탐색할 때 사용  
        self.deleted = NULL  # 프리 리스트의 머리 노드  
        self.capacity = capacity  # 리스트의 크기  
        self.n = [Node()] * self.capacity  
        self.no = 0  

    def __len__(self):  
        return self.no  

    def get_insert_index(self):  
        if self.deleted == NULL:  
            if self.max + 1 < self.capacity:  
                self.max += 1  
                return self.max  
            else:  
                return NULL  
        else:  
            rec = self.deleted  
            self.deleted = self.n[rec].dnext  
            return rec  

    def delete_index(self, idx):  
        if self.deleted == NULL:  
            self.deleted = idx  
            self.n[idx].dnext = NULL  
        else:  
            rec = self.deleted  
            self.deleted = idx  
            self.n[idx].dnext = rec  

    def search(self, data):  
        cnt = 0  
        ptr = self.head  
        while ptr != NULL:  
            if self.n[ptr].data == data:  
                self.current = ptr  
                return cnt  
            cnt += 1  
            ptr = self.n[ptr].next  
        return NULL  

    def __contains__(self, data) -> bool:  
        return self.search(data) >= 0  

    def add_first(self, data):  
        ptr = self.head  
        rec = self.get_insert_index()  
        if rec != NULL:  
            self.head = self.current = rec  
            self.n[self.head] = Node(data, ptr)  
            self.no += 1  

    def add_last(self, data):  
        if self.head == NULL:  
            self.add_first(data)  
        else:  
            ptr = self.head  
            while self.n[ptr].next != NULL:  
                ptr = self.n[ptr].next  
            rec = self.get_insert_index()  

            if rec != NULL:  
                self.n[ptr].next = self.current = rec  
                self.n[rec] = Node(data)  
                self.no += 1  

    def remove_first(self):  
        if self.head != NULL:  
            ptr = self.n[self.head].next  
            self.delete_index(self.head)  
            self.head = self.current = ptr  
            self.no -= 1  

    def remove_last(self):  
        if self.head != NULL:  
            if self.n[self.head].next == NULL:  
                self.remove_first()  
            else:  
                ptr = pre = self.head  

                while self.n[ptr].next != NULL:  
                    pre = ptr  
                    ptr = self.n[ptr].next  
                self.n[pre].next = NULL  
                self.delete_index(ptr)  
                self.current = pre  
                self.no -= 1  

    def print(self):  
        ptr = self.head  
        while ptr != NULL:  
            print(self.n[ptr].data, end = ' ')  
            ptr = self.n[ptr].next  
        print()

4. 원형 이중 연결 리스트

원형 이중 연결 리스트는 앞과 뒤를 함께 볼 수 있음

책 참고 코드

접기/펼치기 버튼

from __future__ import annotations  
from typing import Any, Type  

class Node:  
    def __init__(self, val: Any = None, prev: Node = None, next: Node = None):  
        self.val = val  
        self.prev = prev or self  
        self.next = next or self  

class DLinkedList:  
    def __init__(self):  
        self.head = self.current = Node() # 처음에 더미 노드 생성  
        self.no = 0  

    def __len__(self):  
        return self.no  

    def search(self, val):  
        cnt = 0  
        ptr = self.head.next  
        while ptr is not self.head:  
            if ptr.val == val:  
                return cnt  
            ptr = ptr.next  
        return -1  

    def __contains__(self, val):  
        return self.search(val) >= 0  

    def print_current_node(self):  
        if self.isEmpty():  
            print("주목 노드는 없습니다.")  
        else:  
            print(self.current.val)  

    def print(self):  
        ptr = self.head.next  
        while ptr is not self.head:  
            print(ptr.val, end = ' ')  
            ptr = ptr.next  
        print()  

    def reverse_print(self):  
        ptr = self.head.prev  
        while ptr is not self.head:  
            print(ptr.val, end = ' ')  
            ptr = ptr.prev  
        print()  

    def next(self):  
        if self.isEmpty() or self.current.next is self.head:  
            return False  
        self.current = self.current.next  
        return True  

    def prev(self):  
        if self.isEmpty() or self.current.prev is self.head:  
            return False  
        self.current = self.current.prev  
        return True  

    def add(self, val):  
        # 주목노드 뒤에 val 삽입  
        node = Node(val, self.current, self.current.next)  
        self.current.next.prev = node  
        self.current.next = node  
        self.current = node  
        self.no += 1  

    def add_first(self, val):  
        # 더미노드인 head 바로 뒤에 삽입  
        self.current = self.head  
        self.add(val)  

    def add_last(self, val):  
        self.current = self.head.prev  
        self.add(val)  

    def remove_current_node(self):  
        if not self.isEmpty():  
            self.current.prev.next = self.current.next  
            self.current.next.prev = self.current.prev  
            self.current = self.current.prev  
            self.no -= 1  
            if self.current is self.head:  
                self.current = self.head.next  

    def remove(self, p: Node):  
        ptr = self.head.next  

        while ptr is not self.head:  
            if ptr is p:  
                self.current = p  
                self.remove_current_node()  
                break  
            ptr = ptr.next  

    def remove_first(self):  
        self.current = self.head.next  
        self.remove_current_node()  

    def remove_last(self):  
        self.current = self.head.prev  
        self.remove_current_node()  

    def clear(self):  
        while not self.isEmpty():  
            self.remove_first()  
        self.no = 0  


    def printNode(self):  
        if self.isEmpty():  
            print("비었습니다.")  
            return  
        node = self.head  
        for i in range(self.no + 1):  
            print(node.val, end = ' ')  
            node = node.next  
        print()  

    def isEmpty(self):  
        return self.head.next is self.head

혼자 만든 코드

접기/펼치기 버튼

class Node:  
    def __init__(self, val):  
        self.val = val  
        self.next = None  
        self.prev = None  

class DLinkedList:  
    def __init__(self):  
        self.head = self.tail = None  
        self.no = 0  

    def __len__(self):  
        return self.no  

    def addHead(self, val):  
        node = Node(val)  
        if self.isEmpty():  
            self.head = self.tail = node  
            node.next = self.tail  
            node.prev = self.tail  
            self.no += 1  
        else:  
            self.head.prev = node  
            self.tail.next = node  
            node.prev = self.head.prev  
            node.next = self.head  
            self.head = node  
            self.no += 1  

    def addTail(self, val):  
        if self.isEmpty():  
            self.addHead(val)  
        else:  
            node = Node(val)  
            self.tail.next = node  
            self.head.prev = node  
            node.prev = self.tail  
            node.next = self.head  
            self.tail = node  
            self.no += 1  

    def search(self, val):  
        if self.isEmpty():  
            return -1  
        node = self.head  
        for i in range(self.no):  
            if node.val == val:  
                return i  
            node = node.next  
        return -1  
    def __contains__(self, val):  
        return self.search(val) >= 0  
    def removeHead(self):  
        if self.isEmpty():  
            return  
        if self.no == 1:  
            self.head = self.tail = None  
        else:  
            self.head.next.prev = self.head.prev  
            self.head = self.head.next  
            self.tail.next = self.head  
        self.no -= 1  

    def removeTail(self):  
        if self.isEmpty():  
            return  
        if self.head == self.tail:  
            self.removeHead()  
        else:  
            self.tail.prev.next = self.tail.next  
            self.tail = self.tail.prev  
            self.head.prev = self.tail  
            self.no -= 1  

    def removeValue(self, val):  
        if self.isEmpty():  
            return  
        node = self.head  
        for i in range(self.no):  
            if node.val == val:  
                if i == 0:  
                    self.removeHead()  
                elif i == self.no - 1:  
                    self.removeTail()  
                else:  
                    node.prev.next = node.next  
                    node.next.prev = node.prev  
                    self.no -= 1  
                return  
            node = node.next  


    def remove(self, node):  
        if self.isEmpty():  
            return  
        ptr = self.head  
        for i in range(self.no):  
            if ptr == node:  
                if i == 0:  
                    self.removeHead()  
                elif i == self.no - 1:  
                    self.removeTail()  
                else:  
                    ptr.prev.next = ptr.next  
                    ptr.next.prev = ptr.prev  
                    self.no -= 1  
                return  
            ptr = ptr.next  

    def clear(self):  
        while self.head != self.tail:  
            self.removeHead()  
        self.removeHead()  

    def printNode(self):  
        if self.isEmpty():  
            print("비었습니다.")  
            return  
        node = self.head  
        for i in range(self.no + 1):  
            print(node.val, end = ' ')  
            node = node.next  
        print()  



    def isEmpty(self):  
        if self.no == 0:  
            return True  
        return False

참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편