연결 리스트 (Linked List)

JayJi·2026년 4월 12일

목록 보기

3/30

문제	난이도	핵심
1406번 — 에디터	실버 II	커서 위치 삽입/삭제
5397번 — 키로거	실버 II	커서 이동 시뮬레이션
1158번 — 요세푸스 문제	실버 IV	순환 구조
2346번 — 풍선 터뜨리기	실버 III	순환 시뮬레이션

1. 개념

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드의 주소를 함께 저장하는 자료구조다.

노드들이 포인터로 연결된 사슬 구조다.

배열은 인덱스로 임의 접근이 가능하지만, 삽입/삭제 시 원소를 밀어야 한다.
연결 리스트는 임의 접근은 느리지만, 특정 위치의 삽입/삭제가 O(1) 이다.

단순 연결 리스트 (Singly):  [1] → [2] → [3] → null
이중 연결 리스트 (Doubly):  null ← [1] ⇄ [2] ⇄ [3] → null

2. 배열 vs 연결 리스트

	배열	연결 리스트
임의 접근 (인덱스)	O(1)	O(N)
삽입 / 삭제 (중간)	O(N)	O(1)
삽입 / 삭제 (앞/뒤)	O(N) / O(1)	O(1)
메모리	연속 공간	분산 공간
캐시 효율	좋음	나쁨

삽입/삭제가 빈번하고 순서가 중요한 경우 → 연결 리스트
인덱스로 빠르게 접근해야 하는 경우 → 배열

3. 핵심 포인트 2가지

알고리즘 문제에서는 직접 구현보다 LinkedList 또는 두 개의 스택을 쓴다

Java의 LinkedList는 이중 연결 리스트로 구현되어 있어 바로 활용할 수 있다.
단, 커서 이동이 필요한 에디터 류 문제는 두 개의 스택으로 푸는 것이 훨씬 간결하고 빠르다.

커서 왼쪽 스택   커서 오른쪽 스택
[1, 2, 3]   |   [4, 5]
               ↑ 커서

커서 이동 왼쪽: 왼쪽 스택에서 pop → 오른쪽 스택에 push
커서 이동 오른쪽: 오른쪽 스택에서 pop → 왼쪽 스택에 push
삽입: 왼쪽 스택에 push
삭제: 왼쪽 스택에서 pop

삽입/삭제 시 포인터 연결 순서가 중요하다

직접 구현할 때 포인터 연결 순서를 잘못 바꾸면 노드를 잃는다.
새 노드를 삽입할 때는 기존 연결을 끊기 전에 새 노드를 먼저 연결한다.

// ❌ 잘못된 순서 — prev.next를 먼저 바꾸면 next 노드를 잃음
prev.next = newNode;
newNode.next = prev.next;  // 이미 newNode를 가리키고 있음

// ✅ 올바른 순서
newNode.next = prev.next;  // 새 노드가 다음을 먼저 가리키고
prev.next = newNode;       // 그 다음 이전 노드가 새 노드를 가리킴

4. 코드

노드 클래스 직접 구현 (단순 연결 리스트)

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // 맨 앞에 삽입 — O(1)
    void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 맨 뒤에 삽입 — O(N)
    void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) { head = newNode; return; }
        Node cur = head;
        while (cur.next != null) cur = cur.next;
        cur.next = newNode;
    }

    // 특정 노드 뒤에 삽입 — O(1) (노드를 알고 있을 때)
    void addAfter(Node prev, int data) {
        Node newNode = new Node(data);
        newNode.next = prev.next;  // 새 노드가 먼저 연결
        prev.next = newNode;       // 그 다음 이전 노드 연결
    }

    // 맨 앞 삭제 — O(1)
    void removeFirst() {
        if (head == null) return;
        head = head.next;
    }

    // 특정 값 삭제 — O(N)
    void remove(int data) {
        if (head == null) return;
        if (head.data == data) { head = head.next; return; }
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.data == data) {
                cur.next = cur.next.next;  // 삭제할 노드를 건너뜀
                return;
            }
            cur = cur.next;
        }
    }
}

두 개의 스택으로 에디터 커서 구현

Deque<Character> left  = new ArrayDeque<>();  // 커서 왼쪽
Deque<Character> right = new ArrayDeque<>();  // 커서 오른쪽

// 커서 왼쪽으로 이동
if (!left.isEmpty()) right.push(left.pop());

// 커서 오른쪽으로 이동
if (!right.isEmpty()) left.push(right.pop());

// 커서 왼쪽에 문자 삽입
left.push(c);

// 커서 왼쪽 문자 삭제 (백스페이스)
if (!left.isEmpty()) left.pop();

Java LinkedList 활용

LinkedList<Integer> list = new LinkedList<>();

list.addFirst(1);    // 맨 앞에 추가 — O(1)
list.addLast(2);     // 맨 뒤에 추가 — O(1)
list.add(1, 99);     // 인덱스 1 위치에 추가 — O(N)

list.removeFirst();  // 맨 앞 삭제 — O(1)
list.removeLast();   // 맨 뒤 삭제 — O(1)
list.remove(1);      // 인덱스 1 삭제 — O(N)

int val = list.get(0);  // 인덱스 접근 — O(N)

5. 시간복잡도

연산	배열	연결 리스트
맨 앞 삽입/삭제	O(N)	O(1)
맨 뒤 삽입/삭제	O(1)	O(1)
중간 삽입/삭제 (위치 알 때)	O(N)	O(1)
중간 삽입/삭제 (탐색 포함)	O(N)	O(N)
인덱스 접근	O(1)	O(N)

"위치를 알 때" O(1)이 연결 리스트의 핵심 장점이다.
탐색까지 포함하면 결국 O(N)이므로, 순서대로 순회하며 삽입/삭제하는 상황에서 진가를 발휘한다.

6. 주의사항

Java LinkedList를 인덱스로 접근하면 O(N)이다. get(i)를 반복문 안에서 쓰면 O(N²)이 된다. 순회가 필요하면 Iterator 또는 for-each를 사용하라.
커서 이동 문제는 두 스택 풀이가 정석이다. LinkedList의 ListIterator로도 풀 수 있지만, 두 스택 방식이 더 직관적이고 빠르다.
직접 구현 시 head가 null인 경우를 항상 먼저 처리하라. 빈 리스트에 삭제나 탐색을 시도하면 NullPointerException이 발생한다.
포인터 연결 순서를 반드시 지켜라. 삽입 시 새 노드의 next를 먼저 연결하고, 이전 노드의 next를 나중에 바꿔야 한다.