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

연결 리스트는 해시법을 공부하며 한번 공부했던 경험이 있어서 그런지 쉽게 느껴졌다, 나름 긴 코드도 술술 읽히고 책이 잘 읽혀진다는 느낌을 되게 오랜만에 느껴본 것 같아 뿌듯했다.

 

처음에는 연결리스트가 해시법과 뭐가 다른지 많이 헷갈렸지만 해시법과 연결 리스트는 애초에 비교를 할 수가 없는 다른 종류인 것 같다.

 

해시법은 검색을 하기 위한 알고리즘의 종류일 뿐이고 연결 리스트는 해시법과 같은 알고리즘을 위한 과정? 그 정도인것 같다.

---

연결리스트

 

데이터에 순서를 매겨놓은 자료구조 각 노드에는 다음 노드로 가기 위한 주소와 데이터가 담겨있다. 이 때 주소가 담겨있는 것을 포인터라고 한다. 포인터는 바로 다음 노드만을 가르키기 때문에 바로 뒷주소가 아닌 다른 주소로는 갈 수 없다.

노드를 구현하기 위한 가장 쉬운 방법은 먼저 노드 클래스를 만드는 것 이다.

 

노드 클래스를 만들어 데이터가 담길 노드들을 찍어내어 (인스턴스) 그 노드마다 포인터와 데이터를 저장하면 쉽게 연결 리스트를 구현할 수 있다.

 

다음은 노드 클래스의 코드이다.

class Node:
    def __init__(self, data: Any = None, next: Node = Node):    # node 인스턴스를 생성했을 때 노드를 생성
        self.data = data
        self.next = next	# 포인터

이 때 데이터와 다음 주소를 확인하는 포인터가 있는것을 알 수 있다.

 

다음은 연결리스트 클래스의 코드이다. 

class LinkedList:
    def __init__(self):
        self.no = 0             # 노드의 개수
        self.head = None        # 헤드노드
        self.current = None     # 주목노드

노드의 특수한 경우는 3가지가 있다. 가장 먼저 노드가 존재하지 않을 때, 노드가 1개일 경우 (헤드노드가 꼬리노드일 경우), 2개일 경우 (헤드노드 다음이 꼬리노드일경우) 로 나뉜다.

 

먼저 노드가 존재하지 않을 때 구별하는 법은 코드에서 self.head를 None으로 설정했다. 따라서 노드가 없다면 head는 None인 상태 그대로이다.

 

두번째는 next가 None 인지를 확인하는 것이다. 만약 헤드노드 다음이 아무것도 없다면 연결리스트에는 노드가 1개만 존재하는 것이다. (세번째도 이와 같은 방법으로 구분한다.)

 

마지막으로 연결리스트의 총 코드와 실행 코드이다.

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):
        self.no = 0             # 노드의 개수
        self.head = None        # 헤드노드
        self.current = None     # 주목노드

    def __len__(self) -> int:   # 노드의 개수
        return self.no

    def search(self, data):

        '''찾기'''

        cnt = 0                 # 몇번째 노드인지 반환하기 위한 변수
        ptr = self.head         # 커서
        while ptr is not None:  # 노드가 리스트 안에 있다면
            if ptr.data == data:  # 데이터가 맞다면
                return cnt        # 노드의 위치 반환
            cnt += 1              # 데이터가 맞지않다면 다음 노드로 커서 이동
            ptr = ptr.next        # 포인터를 참조하여 다음 노드로
        return -1                 # 아무것도 찾지 못했을 때 -1 반환

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

    def add_first(self, data):

        '''첫번째 자리에 노드 추가'''

        ptr = self.head           # 커서를 헤드노드로 이동
        self.head = self.current = Node(data, ptr)  # 헤드에 노드를 생성 (이 때 포인터는 ptr을 참조한다)
        self.no += 1                                # 노드의 개수 +1

    def add_last(self, data):

        '''마지막 자리에 노드 추가'''

        if self.head is None:                       # 만약 노드가 비어있다면 첫번째에 삽입
            self.add_first(data)

        else:
            ptr = self.head
            while ptr.next is not None:                 # 커서의 다음이 None이 아니라면 (커서가 마지막 노드가 아니라면)
                ptr = ptr.next                      # 다음으로 넘긴다
            ptr.next = self.current = Node(data, None)
            self.no += 1

    def remove_first(self):

        '''첫번째 노드 삭제'''

        if self.head is not None:                       # 리스트가 비어있지 않다면
            self.head = self.current = self.head.next   # 헤드와 참조노드를 모두 기존 헤드의 다음 노드로 정의
        self.no -= 1                                    # 리스트의 개수 -1

    def remove_last(self):

        '''마지막 노드 삭제'''

        if self.head is not None:                       # 리스트가 비어있지 않다면
            if self.head.next is None:                  # 만약 헤드 다음이 None이라면 (리스트에 노드가 1개밖에 없다면)
                self.remove_first()                     # 헤드노드 삭제
            else:
                ptr = self.head                         # 커서를 헤드로 전환
                pre = self.head                         # 커서의 이전 노드 (현재는 같지만 아래 행에서 커서의 이전으로 전환함)

                while ptr.next is not None:             # 커서의 다음이 None가 아니라면 (커서가 마지막까지 가지 않았다면)
                    pre = ptr
                    ptr = ptr.next                      # 커서를 다음으로 전환

                pre.next = None                         # ptr 삭제
                self.current = pre                      # 주목 노드를 pre로 전환
                self.no -= 1                            # 노드의 개수 -1

    def remove(self, p):

        ''' 노드 p를 삭제 '''

        if self.head is not None:                       # 리스트가 비어있지 않다면
            if p is self.head:
                self.remove_first()
            else:
                ptr = self.head                         # ptr을 head로 초기화

                while ptr.next is not p:                # ptr의 다음이 p가 아니라면
                    ptr = ptr.next                      # ptr을 1씩 증가
                    if ptr is None:                     # ptr이 리스트를 벗어났다면
                        return

                ptr.next = p.next                       # p의 next(삭제하고자 하는 노드(p))를 p의 next로 전환 (두 단계 건너뜀)
                self.current = ptr                      # 주목 노드를 ptr
                self.no -= 1                            # 전체 노드 개수 -1

    def clear(self):

        '''노드 전체 삭제'''

        while self.head is not None:                    # 헤드가 None이 아닐 떄
            self.remove_first()                         # 헤드를 삭제
        self.current = None
        self.no = 0

    def next(self):

        '''주목노드를 다음으로 이동'''

        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):

        '''주목 노드를 출력'''

        if self.current is None:
            print('주목 노드가 존재하지 않음')

        else :
            print(self.current.data)

    def print(self):

        '''전체 노드 출력'''

        ptr = self.head

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

    def __iter__(self):

        ''' 이터레이블 반환 '''

        return LinkedListIterator(self.head)

class LinkedListIterator:

    ''' 클래스 LinkedList의 이터레이터용 클래스'''

    def __init__(self, head):
        self.current = head

    def __iter__(self):
        return self

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

실행코드

from enum import Enum
from linked_list import LinkedList

Menu = Enum('Menu',['add_first_node', 'add_last_node', 'delete_first_node', 'delete_last_node', 'print_current_node', 'move_current_node', 'claer', 'search', 'judgment', 'print_all_node', 'scan', 'exit'])

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

lst = LinkedList()

while 1:
    menu = select_Menu()

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

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

    elif menu == Menu.delete_first_node:
        lst.remove_first()

    elif menu == Menu.delete_last_node:
        lst.remove_last()

    elif menu == Menu.print_current_node:
        lst.print_current_node()

    elif menu == Menu.move_current_node:
        lst.next()

    elif menu == Menu.claer:
        lst.clear()

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

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

    elif menu == Menu.print_all_node:
        lst.print()

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

    else:
        break