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

Preface

 

이번 장에선 리스트의 종류들 중 포인터를 통해 효율성을 향상시킨 연결 리스트에 대해 공부했다.

 

만들어야 할 함수가 많아 코드가 생각보다 길어졌지만, 클래스를 통해 선언하는 단순한 함수들을 나열한 것이므로 크게 어려운 부분은 없었다.

 

며칠 간 책에 있는 내용들을 이해하기 어려워 스트레스를 많이 받았었는데, 이번 장은 쉽게 이해할 수 있었던 탓인지 숨통이 조금 트인 것 같다.

---

 

1. 연결 리스트

 

 

- 리스트 : 순서가 있는 데이터를 늘어놓은 자료구조

1) 선형 리스트 : 데이터의 논리적인 순서와 기억 장소에 저장되는 물리적인 순서가 일치하는 구조

2) 연결 리스트 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 구조

 

 

- 연결 리스트 용어

1) 노드 : 각각의 원소

2) 머리 노드 : 맨 앞에 있는 노드

3) 꼬리 노드 : 맨 끝에 있는 노드

 

---

 

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

 

 

- 자기 참조형 : 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조

 

 

- 연결 리스트 코드

# 포인터로 연결 리스트 구현하기

from __future__ import annotations
from typing import Any, Type


class Node:  # 연결 리스트용 노드 클래스
    def __init__(self, data: Any = None, next: Node = None):
        self.data = data
        self.next = next


class LinkedList:  # 연결 리스트 클래스
    def __init__(self) -> None:
        self.no = 0          # 노드의 개수
        self.head = None     # 머리 노드
        self.current = None  # 주목 노드

    def __len__(self) -> int:
        return self.no

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

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

    def add_first(self, data: Any) -> None:  # 머리에 노드를 삽입
        ptr = self.head
        self.head = self.current = Node(data, ptr)
        self.no += 1

    def add_last(self, data: Any) -> None:  # 꼬리에 노드를 삽입
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = self.current = Node(data, None)
            self.no += 1

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

    def remove_last(self) -> None:
        if self.head is not None:
            if self.head.next is None:
                self.remove_first()
            else:
                ptr = self.head
                pre = self.head

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

    def remove(self, p: Node) -> None:  # 임의의 노드를 삭제
        if self.head is not None:
            if p in self.head:
                self.remove_first()
            else:
                ptr = self.head

                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return
                ptr.next = p.next
                self.current = ptr
                self.no -= 1

    def remove_current_node(self) -> None:
        self.remove(self.current)

    def clear(self) -> None:
        while self.head is not None:
            self.remove_first()
        self.current = None
        self.no = 0

    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 print_current_node(self) -> None:
        if self.current is None:
            print('주목 노드가 존재하지 않습니다.')
        else:
            print(self.current.data)

    def print(self) -> None:
        ptr = self.head

        while ptr is not None:
            print(ptr.data)
            ptr = ptr.next

    def __iter__(self) -> LinkedListIterator:
        return LinkedListIterator(self.head)


class LinkedListIterator:
    def __init__(self, head: Node):
        self.current = head

    def __iter__(self) -> LinkedListIterator:
        return self

    def __next__(self) -> Any:
        if self.current is None:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.next
            return data

 

 

- 이터러블 객체 : 반복 가능한 원소를 1개씩 꺼내는 구조의 객체

 

 

- 이터레이터(반복자) : 데이터가 줄지어 늘어선 것을 표현하는 객체

 

 

- 연결리스트 프로그램 코드

from enum import Enum
from linked_list import LinkedList

Menu = Enum('Menu', ['머리에노드삽입', '꼬리에노드삽입', '머리노드삭제',
                     '꼬리노드삭제', '주목노드출력', '주목노드이동',
                     '주목노드삭제', '모든노드삭제', '검색', '멤버십판단',
                     '모든노드출력', '스캔', '종료'])


def select_menu() -> Menu:
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)


lst = LinkedList()

while True:
    menu = select_menu()

    if menu == Menu.머리에노드삽입:
        lst.add_first(int(input('머리 노드에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.꼬리에노드삽입:
        lst.add_last(int(input('꼬리에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.머리노드삭제:
        lst.remove_first()

    elif menu == Menu.꼬리노드삭제:
        lst.remove_last()

    elif menu == Menu.주목노드출력:
        lst.print_current_node()

    elif menu == Menu.주목노드이동:
        lst.next()

    elif menu == Menu.주목노드삭제:
        lst.remove_current_node()

    elif menu == Menu.모든노드삭제:
        lst.clear()

    elif menu == Menu.검색:
        pos = lst.search(int(input('검색할 값을 입력하세요.: ')))
        if pos >= 0:
            print(f'그 값의 데이터는 {pos + 1}번째에 있습니다.')
        else:
            print('해당하는 데이터가 없습니다.')

    elif menu == Menu.멤버십판단:
        print('그 값의 데잉터는 포함되어'
              + (' 있습니다.' if int(input('판단할 값을 입력하세요.: ')) in lst
                 else '있지 않습니다.'))

    elif menu == Menu.모든노드출력:
        lst.print()

    elif menu == Menu.스캔:
        for e in lst:
            print(e)

    else:
        break