[ALGORITHM] 연결리스트, 스택, 큐, 해시 테이블

연결리스트(Linked List)

연결리스트는 인덱스를 통해 빠른 접근은 가능하지만 크기가 불변인 배열의 단점을 보완하기 위해 생긴 자료구조이다. 기본적으로 파이썬은 리스트가 이 연결리스트의 기능들을 지원한다.

• Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다.
• Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가지고 있다.
• Head : 연결리스트에서 가장 시작점인 데이터를 의미한다.
• Tail : 연결리스트에서 가장 마지막 데이터를 의미한다.
• Next = None(Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(Null)이다.

연결리스트는 필요한 데이터를 찾을때 시작점(head)부터 pointer를 따라 해당 데이터를 찾기 때문에 O(n)의 시간 복잡도를 갖는다. 하지만 배열은 인덱스로 값을 찾기 때문에 O(1)의 시간복잡도를 갖는다.

연결리스트는 데이터를 중간에 삽입하거나 삭제할때 O(1)의 시간복잡도를 갖는다. 반대로 배열의 경우는 데이터를 중간에 삽입하거나 삭제할때 먼저 데이터가 들어갈 빈공간을 만들어줘야 하기 때문에 O(n)의 시간 복잡도를 갖는다.

연결리스트 구현

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

class LinkedList:
    def __init__(self, data):
        init = Node('init')
        self.head = init
        self.tail = init

        self.현재노드 = None
        self.데이터수 = 0

    def __len__(self):
        return self.데이터수

    def __str__(self):
        현재노드 = self.head
        현재노드 = 현재노드.next
        s = ''

        for i in range(self.데이터수):
            s += f'{현재노드.data}, '
            현재노드 = 현재노드.next

        return f'[{s[:-2]}]'

    def __iter__(self):
        현재노드 = self.head
        현재노드 = 현재노드.next
        while 현재노드:
            yield 현재노드.data
            현재노드 = 현재노드.next

    def append(self, data):
        새로운노드 = Node(data)
        self.tail.next = 새로운노드
        self.tail = 새로운노드
        self.데이터수 += 1

    def insert(self, input_index, input_data):
        현재노드 = self.head
        현재노드 = 현재노드.next
        for i in range(input_index):
            현재노드 = 현재노드.next

        신규노드 = Node(input_data)
        신규노드.next = 현재노드.next
        현재노드.next = 신규노드
        self.데이터수 += 1

    def pop(self):
        마지막값 = self.tail.data
        현재노드 = self.head

        for i in range(self.데이터수):
            if 현재노드.next is self.tail:
                self.tail = 현재노드
                break
            현재노드 = 현재노드.next

        self.데이터수 -= 1
        return 마지막값

    def find(self, data):
        index = -1
        현재노드 = self.head

        for i in range(self.데이터수 + 1):
            if 현재노드.data == data:
                return index
            index += 1
            현재노드 = 현재노드.next

        return -1

스택

스택을 배울때 개념을 이해하기 가장 쉬운 방법은 접시 쌓는 것을 연상하면 된다. 스택이란 나중에 넣은 데이터가 먼저 반환되도록 설계한 자료구조인데 이것이 마치 접시를 쌓았을때 가장 위의 접시부터 가져오는 것과 같은 개념이기 때문이다. (Last In First Out - LIFO)

스택구조에서 데이터의 입력은 push로 출력은 pop으로 실행할수 있다.

파이썬에서는 append와 pop을 이용해 데이터를 추가하고 삭제하는데 pop의 경우 삭제하면서 삭제한 값을 return해주고 리스트 내에서 삭제된다.

스택 구현

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        if self.top is None:
            return None
        
        topNode = self.top
        self.top = self.top.next

        return topNode

    def is_empty(self):
        return self.top is None

큐

큐의 경우 줄서기를 연상하면 개념을 이해하기 쉽다. 나중에 들어온 값이 먼저 나가는 스택과 달리 큐는 먼저 들어온 값이 먼저나가는 선입선출(First In First Out - FIFO) 방식을 사용하는데 줄서기의 먼저 줄선 사람이 먼저 입장하는 것과 개념이 같다.

큐구조에서 데이터의 입력은 push로 출력은 get으로 실행할수 있다.

파이썬에서는 스택과 마찬가지로 append와 pop(0)을 사용하여 데이터를 입출력 할수 있는데 가장 먼저 들어온 값을 먼저 출력하기 때문에 pop 괄호안에 0을 써준것을 확인할 수 있다. 마찬가지로 0번째 입력값을 return하고 원래 리스트에서 0번째 인덱스 값을 삭제한다. 삭제하고 나서는 1번 인덱스에 있던 값이 0번 인덱스를 갖는다.

큐 구현

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

class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        if not self.front:
            self.front = Node(value, None)
            return

        node = self.front
        while node.next:
            node = node.next
        node.next = Node(value, None)

    def pop(self):
        if not self.front:
            return None

        node = self.fromt
        self.front = self.front.next

        return node.item

    def is_empty(self):
        return self.front is None

해시 테이블

인덱스를 이용해 데이터를 찾는 배열과 달리 해시 테이블은 key와 value로 이루어져 있어 데이터를 찾을때 key값을 이용하는데 이는 사전을 생각해보면 이해하기 쉽다. 사전에서 뜻(value)을 알고 싶은 단어(key)를 찾는 것처럼 key값을 이용해 value값을 가져오는것과 같은 개념이기 때문이다. 실제로 파이썬에서 해시 테이블 기능을 제공하는 자료형 이름이 dictionary이다.

해시 테이블은 입력받은 key값을 해시함수로 돌려서 반환된 해시코드를 배열의 인덱스 값으로 환산해서 데이터에 접근하는 자료구조로 key값을 이용해 배열에 다이렉트로 접근하기 때문에 검색시간이 매우 빠르다.

해시함수는 key 값이 얼마나 크던 상관없이 동일한 크기의 해시값을 반환하는데 그렇기 때문에 무한에 가까운 key값으로 해쉬할수를 돌리면 같은 해시코드가 반환될수도 있어서 같은 인덱스 값에 여러 values가 들어가 충돌(collision)이 발생할수도 있다. 이를 해결하기 위해 배열 방에 데이터를 바로 저장하는게 아니라 배열 방 안에 Linked List를 선언하고 데이터가 들어올때마다 Linked List에 값을 추가해 준다. 이를 해시 체이닝이라고 한다. 이 경우 key값으로 배열 방을 찾는데 시간복잡도가 N(1)이지만 Linked List에서 다시 또 검색을 해야하기 때문에 시간복잡도가 증가하게 된다.

해시테이블의 크기는 가변적인데 로드팩터 지수에 따라 크기를 늘려간다. 로드팩터란 해시테이블의 전체 크기중 데이터가 차지하는 비율을 말하는데 데이터 양이 이 로드팩터를 넘어가게 되면 크기를 더블링한다.

크기를 고정하고 충돌(collision)을 해결한 방법도 있습니다. 이를 oppen addressing이라고 하는데 할당받은 key값에 이미 value가 있는경우 그 다음 배열방에 값을 삽입하는 방법으로 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 문제가 있다.

해시 테이블 구현

import collections


class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

class MyHashTable:
    def __init__(self):
        self.size = 100
        self.table = collections.defaultdict(ListNode)

    def put(self, key, value):
        index = key % self.size

        new_node = ListNode(key, value)

        item = self.table(index)
        if not item:
            self.table[index] = new_node
        while item:
            if item.key == key:
                item.value = value
                return
            if not item.next:
                break
            item = item.next
        item.next = new_node

    def get(self, key):
        index = key % self.size
        if self.table[index].value is None:
            return -1

        p = self.table[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1

    def remove(self, key):
        index = key % self.size
        if self.table[index].value is None:
            return

        p = self.table[index]
        if p.key == key:
            self.table[index] = ListNode() if p.next is None else p.next
            return

        prev = p
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev, p = p, p.next