커서를 이용한 연결 리스트

Preface

 

이번 장에선 커서를 이용한 연결 리스트를 공부했다.

 

이는 연결 리스트를 사용하는 방법 중 하나이므로 지난 장에서 공부했던 포인터를 이용한 연결 리스트와 크게 다른 부분이 없었다.

 

한 가지 다른 점이라면 프리 리스트를 사용한다는 것인데, 이 또한 배열의 빈 공간 인덱스를 특정 변수에 저장한다는 개념일 뿐 특별한 점은 없어 어렵지 않게 이해할 수 있었다.

---

 

- 커서(cursor) : 인덱스로 나타낸 뒤쪽 포인터

 

 

- 커서를 이용한 연결 리스트 : 데이터 개수가 크게 변하지 않거나 데이터 최대 개수를 예측할 수 있는 경우 프리 리스트를 사용하여 메모리를 확보하는 구조

 

 

- 커서를 이용한 연결 리스트 코드

# 커서로 연결 리스트 구현하기

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: int):
        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) -> int:
        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: int) -> None:  # 레코드 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: Any) -> int:
        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: Any) -> bool:
        return self.search(data) >= 0

    def add_first(self, data: Any) -> None:
        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: Any) -> None:
        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) -> None:
        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) -> None:
        if self.head != Null:
            if self.n[self.head].next == Null:
                self.remove_first()
            else:
                ptr = self.head
                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 remove(self, p: int) -> None:
        if self.head != Null:
            if p == self.head:
                self.remove_first()
            else:
                ptr = self.head

                while self.n[ptr].next != p:
                    ptr = self.n[ptr].next
                    if ptr == Null:
                        return
                self.n[ptr].next = Null
                self.delete_index(p)
                self.n[ptr].next = self.n[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 != Null:
            self.remove_first()
        self.current = Null

    def next(self) -> bool:
        if self.current == Null or self.n[self.current].next == Null:
            return False
        self.current = self.n[self.current].next
        return True

    def print_current_node(self) -> None:
        if self.current == Null:
            print('주목 노드가 없습니다.')
        else:
            print(self.n[self.current].data)

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

        while ptr != Null:
            print(self.n[ptr].data)
            ptr = self.n[ptr].next

    def dump(self) -> None:
        for i in self.n:
            print(f'[{i}]  {i.data} {i.next} {i.dnext}')

    def __iter__(self) -> ArrayLinkedListIterator:
        return ArrayLinkedListIterator(self.n, self.head)


class ArrayLinkedListIterator:
    def __init__(self, n: int, head: int):
        self.n = n
        self.current = head

    def __iter__(self) -> ArrayLinkedListIterator:
        return self

    def __next__(self) -> Any:
        if self.current == Null:
            raise StopIteration
        else:
            data = self.n[self.current].data
            self.current = self.n[self.current].next
            return data

 

※ 삽입된 노드의 저장 장소는 연결 리스트의 맨 끝이 아닌 배열 안에서 가장 끝 쪽에 있는 인덱스의 위치이다.

 

 

- 프리 리스트 : 삭제된 레코드 그룹을 관리할 때 사용하는 자료구조

 

 

- 커서를 이용한 연결 리스트 프로그램 코드

from enum import Enum
from array_list import ArrayLinkedList

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 = ArrayLinkedList(100)

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

 

 

- 파이썬의 논리 연산자

1) x and y : x를 평가하여 거짓이면 그 값을 생성하고, 그렇지 않으면 y를 평가하여 그 값을 생성한다.

2) x or y : x를 평가하여 참이면 그 값을 생성하고, 그렇지 않으면 y를 평가하여 그 값을 생성한다.

3) not x : x가 참이면 False, 그렇지 않으면 True를 생성한다.

 

 

- 단축 평가 : and 연산자와 or 연산자의 평가 결과가 왼쪽 피연산자의 평가 결과만으로 명확해질 경우 오른쪽 피연산자의 평가를 생략하는 것