링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해 주세요.

링크드 리스트의 동적 크기와 포인터 연결 특성을 활용해 스택, 큐, 덱, 해시맵 등을 구현할 수 있습니다.

1. 스택 (Stack)

LIFO(Last In First Out) - 마지막에 넣은 것을 먼저 꺼냅니다.

class Stack {
    Node top;

    void push(int data) {       // O(1)
        Node node = new Node(data);
        node.next = top;
        top = node;
    }

    int pop() {                 // O(1)
        int data = top.data;
        top = top.next;
        return data;
    }
}
// push(1) → push(2) → push(3) → pop() : 3 반환
// [3] → [2] → [1] → null
//  ↑ top

2. 큐 (Queue)

FIFO(First In First Out) - 먼저 넣은 것을 먼저 꺼냅니다.

class Queue {
    Node head, tail;

    void enqueue(int data) {    // O(1)
        Node node = new Node(data);
        if (tail != null) tail.next = node;
        tail = node;
        if (head == null) head = node;
    }

    int dequeue() {             // O(1)
        int data = head.data;
        head = head.next;
        if (head == null) tail = null;
        return data;
    }
}
// enqueue(1) → enqueue(2) → enqueue(3) → dequeue() : 1 반환
// head → [1] → [2] → [3] ← tail

3. 덱 (Deque)

양쪽 끝에서 삽입/삭제가 모두 가능한 자료구조입니다. 이중 연결 리스트로 구현합니다.

// 이중 연결 리스트 노드
class Node {
    int data;
    Node prev, next;
}

class Deque {
    Node head, tail;

    void addFirst(int data) { ... }  // O(1)
    void addLast(int data)  { ... }  // O(1)
    int removeFirst()       { ... }  // O(1)
    int removeLast()        { ... }  // O(1)
}

4. 해시맵 (HashMap)

해시 충돌 해결을 위해 체이닝(Chaining) 방식에 링크드 리스트를 활용합니다.

// 같은 해시값 → 링크드 리스트로 연결
index 0: [A|*] → [B|*] → null  // 충돌 발생 시 체이닝
index 1: [C|*] → null
index 2: null

// Java의 HashMap도 내부적으로 체이닝 사용
// 단, Java 8부터 체인 길이 8 이상이면 LinkedList → RedBlack Tree로 전환
HashMap<String, Integer> map = new HashMap<>();

5. 그래프 인접 리스트

각 정점의 인접 노드를 링크드 리스트로 표현합니다.

// 인접 리스트 표현
ArrayList<LinkedList<Integer>> graph = new ArrayList<>();

// 정점 0과 연결된 노드: 1 → 2 → 3
// 정점 1과 연결된 노드: 0 → 3
graph.get(0) // [1] → [2] → [3]
graph.get(1) // [0] → [3]

정리