리스트

오늘은 선형리스트와, 연결리스트에 대해 알아보겠습니다.

 

선형리스트

선형리스트는와 연결리스트는 리스트 중 가장 단순한 연결 구조로 되어있습니다.

선형 리스트 동일한 자료형들이 순서를 갖습니다. 인덱스로 접근할 수 있기 때문에 접근이 빠르고 관리하기 편하다는 장점이 있는 반면,

자료 삽입, 삭제시 자료의 인덱스가 변해 최대 O(n)의 시간 복잡도를 가지기에 느리다는 단점과 배열으로 구현하기 때문에 갖는 메모리 비효율성이 있습니다.

 

연결리스트

연결리스트에선 원소를 노드라 합니다. 그리고 노드는 데이터와 뒤쪽 노드를 가리키는 포인터를 갖습니다.

 

그럼 포인터로 이용한 연결 리스트, 커서로 이용한 연결 리스트, 원형 이중 연결 리스트를 구현한 예시를 보여드리겠습니다.

 

 

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

이 것은 leet code 에서 포인터로 연결한 연결리스트 예제입니다.

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

앞서 말씀드린 것 처럼 데이터 val 과 포인터 next가 있습니다.

 

다음은 리트코드의 원소 삭제 문제입니다.

https://leetcode.com/problems/remove-linked-list-elements/

Remove Linked List Elements - LeetCode

#외쳐 갓 스택오버플로우

class Solution:
    def removeElements(self, head, val):
    	#탐색을 위한 더미 생성.
        dummy = ListNode(-1)
        dummy.next, curr = head, dummy
        
        while curr.next:
        	#원소 전체 순회
            
            if curr.next.val == val:
            	#다음 원소의 데이터가 삭제할 데이터와 같으면?
                
                curr.next = curr.next.next
                #다음 원소는 다다음 원소가 됨.
            else:
            	#다음 원소의 데이터가 삭제할 데이터와 다르면?
                curr = curr.next
                
                #다음 데이터 조회.
                
        # 전체 순회할 때 원소와 삭제원소가 같을 경우 조회하지 않고 넘었으로, 자연스레 dummy는 삭제한 자료만 남게됩니다. :) 
        return dummy.next

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

배열의 크기가 정해져 변하지 않는 경우, 커서를 이용해 연결 리스트를 구현할 수 있습니다. 포인터를 사용한 경우 인스터스 생성과 소멸을 반복하기에 상당한 메모리 확보, 해제 비용을 필요로 합니다. 때문에 이 방법을 통해 효율적인 보완이 가능합니다.

커서는 인덱스로 나타낸 뒤쪽 포인터를 뜻하며, 인스턴스를 계속 생성하는게 아니라 큰 배열 하나를 만들어 해당 배열에 데이터와 포인터를 삽입키는 방식으로 구현합니다. (동적 메모리 할당)

 

데이터 삭제시 : 현재포인터(인덱스)를 데이터가 가지고 있던 다음포인터로 갱신하고 배열의 내용을 삭제합니다.

 

그리고 삭제된 레코드 그룹을 관리할 때 빈칸 목록(free list)을 사용하는데, 사실 이해 못했습니다. 하..CS 솔직히 너무 어렵네요.하아...

https://ko.wikipedia.org/wiki/%EB%B9%88%EC%B9%B8_%EB%AA%A9%EB%A1%9D

빈칸 목록 - 위키백과, 우리 모두의 백과사전

 

3. 원형 이중 연결 리스트

원형 이중 연결 리스트는 맨 마지막 노드가 맨 앞 원소의 포인터를 가르키기 때문에 다음 원소의 포인터 (next) 뿐 아니라 이전 원소의 포인터 (prev) 를 갖는 차별점이 있습니다. 또 이전 원소의 포인터가 있기 때문에 양방향 스캔이 가능한 특징이 있습니다.

 

다음은 지금 공부하는 'Do It! 자료 구조와 함께 배우는 알고리즘 입문 편'에서 구현한 원형 이중 연결리스트 입니다. 책 정말 좋아요 :)!

# 원형 이중 연결 리스트 구현하기

from __future__ import annotations
from typing import Any, Type
from enum import Enum

class Node:  # 원형 이중 연결 리스트용 노드 클래스
    def __init__(self, data: Any = None, prev: Node = None,
                 next: Node = None) -> None:
        self.data = data
        self.prev = prev or self
        self.next = next or self
        # 파이썬 논리 연산자 참고


class DoubleLinkedList:
    def __init__(self) -> None:
        self.head = self.current = Node()
        self.no = 0

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

    def is_empty(self) -> bool:  # 더미 노드를 참조하므로 비어있는 것
        return self.head.next is self.head

    def search(self, data: Any) -> Any:  # 맨 앞에 더미 노드가 있으므로 다음 노드부터 검색
        cnt = 0
        ptr = self.head.next
        while ptr is not self.head:
            if data == ptr.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 print_current_node(self) -> None:
        if self.is_empty():
            print('주목 노드는 없습니다.')
        else:
            print(self.current.data)

    def print(self) -> None:
        ptr = self.head.next
        while ptr is not self.head:
            print(ptr.data)
            ptr = ptr.next

    def print_reverse(self) -> None:
        ptr = self.head.prev
        while ptr is not self.head:
            print(ptr.data)
            ptr = ptr.prev

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

    def prev(self) -> bool:
        if self.is_empty() or self.current.prev is not self.head:
            return False
        self.current = self.current.prev
        return True

    def add(self, data: Any) -> None:
        node = Node(data, self.current, self.current.next)
        self.current.next.prev = node
        self.current.next = node
        self.current = node
        self.no += 1

    def add_first(self, data: Any) -> None:
        self.current = self.head
        self.add(data)

    def add_last(self, data: Any) -> None:
        self.current = self.head.prev
        self.add(data)

    def remove_current_node(self) -> None:
        if not self.is_empty():
            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) -> None:
        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) -> None:
        self.current = self.head.next
        self.remove_current_node()

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

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

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

    def __reversed__(self) -> DoubleLinkedListReverseIterator:
        return DoubleLinkedListReverseIterator(self.head)


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

    def __iter__(self) -> DoubleLinkedListIterator:
        return self

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


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

    def __iter__(self) -> DoubleLinkedListReverseIterator:
        return self

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

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 = DoubleLinkedList()

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.add(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.prev()

    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.모든노드역순출력:
        lst.print_reverse()

    elif menu == Menu.모든노드스캔:
        for e in lst:
            print(e)

    elif menu == Menu.모든노드역순스캔:
        for e in reversed(lst):
            print(e)

    else:
        break