[WEEK02] 연결 리스트와 해시 테이블

연결 리스트 (Linked List)

[출처] https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/

 

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지는 자료구조다. 배열과 달리, 물리적으로 연속된 메모리 공간을 사용할 필요가 없고 동적으로 크기를 조절할 수 있다.

• 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드만 가리킴
  

  

• 이중 연결 리스트 (Doubly Linked List): 각 노드가 앞뒤 노드를 모두 가리킴
  

  

• 순환 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리킴
  

  

연결 리스트의 구조

• 노드(Node): 데이터와 다음 노드에 대한 포인터로 구성됨
• 헤드(Head): 연결 리스트의 첫 번째 노드를 가리키는 포인터
• 테일(Tail): 연결 리스트의 마지막 노드를 가리키는 포인터 (optional)

Python에서는 보통 클래스를 활용하여 노드를 정의하고 연결 리스트를 구성한다.

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)
    
    def delete(self, key):
        current = self.head

        if current and current.data == key:
            self.head = current.next
            return

        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        if current is None:
            return

        prev.next = current.next
    
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 사용 예시
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # 1 -> 2 -> 3 -> None

연결 리스트의 장점

• 동적 크기 조절 : 배열과 달리, 연결 리스트는 메모리를 동적으로 할당하므로 크기를 유동적으로 조절할 수 있다.
• 삽입 및 삭제 용이 : 중간에 데이터를 삽입하거나 삭제할 때, 요소를 이동할 필요 없이 포인터만 조정하면 된다. 이는 O(1)의 시간 복잡도로 가능하므로 효율적이다.

연결 리스트의 단점:

• 메모리 오버헤드 : 각 노드가 포인터를 저장해야 하므로, 배열에 비해 메모리 사용이 비효율적이다.
• 접근 속도 : 배열은 인덱스를 통해 O(1) 시간에 접근할 수 있지만, 연결 리스트는 순차적으로 따라가야 하므로 O(n) 시간이 걸린다.
• 캐시 지역성 부족 : 배열은 메모리에 연속적으로 저장되므로 CPU 캐시 활용이 뛰어나지만, 연결 리스트는 노드가 메모리에 흩어져 저장될 수 있어 성능이 저하될 수 있다.

---

해시 테이블 (Hash Table)

[출처] 파이썬 알고리즘 인터뷰

 

해시 테이블은 키(Key)와 값(Value)의 쌍을 저장하는 자료구조로, 빠른 데이터 접근이 가능하다. 리스트나 배열처럼 순차적으로 검색하는 것이 아니라, 키를 해시 함수(Hash Function)를 통해 특정 인덱스로 변환하여 데이터를 저장한다.

• 해시 함수(Hash Function) : 키를 특정한 인덱스로 매핑하는 함수
• 해시 충돌(Hash Collision) : 서로 다른 키가 같은 인덱스로 매핑될 때 발생하는 문제 (체이닝 또는 개방 주소법으로 해결 가능)
• 체이닝(Chaining) : 같은 해시 인덱스에 여러 개의 값을 리스트 형태로 저장하는 방식
• 개방 주소법(Open Addressing) : 충돌이 발생하면 다른 빈 공간을 찾아 저장하는 방식

Python의 dict()과 set()은 내부적으로 해시 테이블을 사용하여 빠른 검색과 삽입을 제공한다.

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])
    
    def get(self, key):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None
    
    def delete(self, key):
        index = self._hash(key)
        self.table[index] = [pair for pair in self.table[index] if pair[0] != key]

# 사용 예시
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 25)
print(ht.get("name"))  # Alice
ht.delete("name")
print(ht.get("name"))  # None

해시 테이블의 장점

• 빠른 데이터 접근 : 평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있다. 해시 함수를 통해 직접 인덱스를 계산하기 때문이다.
• 유연한 데이터 저장 : 다양한 유형의 데이터를 저장할 수 있으며, 키를 통해 쉽게 검색할 수 있다.
• 충돌 처리 가능 : 다양한 충돌 해결 기법(예: 체이닝, 오픈 어드레싱)을 통해 서로 다른 키가 동일한 해시값을 가질 때도 데이터를 저장할 수 있다.

해시 테이블의 단점

• 메모리 사용: 해시 테이블은 메모리를 비효율적으로 사용할 수 있다. 특히, 빈 슬롯이 많으면 메모리 낭비가 발생할 수 있다.
• 해시 함수의 품질: 해시 함수가 좋지 않으면 충돌이 많이 발생할 수 있으며, 이로 인해 성능이 저하될 수 있다. 최악의 경우 O(n)의 시간 복잡도가 될 수 있다.
• 정렬 불가: 해시 테이블은 데이터가 해시값에 따라 저장되므로, 키의 순서에 따라 정렬된 데이터를 저장할 수 없다.
• 복잡한 구현: 충돌 해결 및 동적 크기 조정 등을 고려해야 하므로 구현이 복잡할 수 있다.