연결 리스트 기초 개념

배열과 연결 리스트의 차이점을 이해하는 것이 중요합니다. 배열은 연속된 메모리 공간에 저장되지만, 연결 리스트는 각 요소가 다음 요소를 가리키는 포인터로 연결됩니다. 이로 인해 삽입/삭제 시 시간 복잡도가 다르며, 특히 중간 위치에서의 조작이 유연합니다.

203. 연결 리스트 요소 제거

가상 헤드 노드를 사용하면 첫 번째 노드 삭제 시 처리가 간편해집니다. 실제 헤드가 삭제될 수 있으므로, 반환할 때는 가상 헤드의 다음 노드를 반환해야 합니다.

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;

while (current.next != null) {
    if (current.next.val == targetValue) {
        current.next = current.next.next;
    } else {
        current = current.next;
    }
}
return dummy.next;

재귀적 접근

재귀는 끝에서부터 시작하여 역순으로 처리합니다. 현재 노드의 값이 삭제 대상이라면 다음 노드를 반환하고, 그렇지 않으면 자신을 반환합니다.

public ListNode removeElements(ListNode node, int value) {
    if (node == null) return null;
    
    node.next = removeElements(node.next, value);
    return node.val == value ? node.next : node;
}

707. 연결 리스트 설계

단일 연결 리스트와 양방향 연결 리스트 두 가지 방식으로 구현할 수 있습니다. 가상 헤드를 사용하면 삽입/삭제 로직이 일관되게 유지됩니다.

단일 연결 리스트 구현

class MyLinkedList {
    private int size;
    private ListNode dummyHead;

    public MyLinkedList() {
        this.size = 0;
        this.dummyHead = new ListNode(0);
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode cur = dummyHead;
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size++;
    }

    public void addAtTail(int val) {
        ListNode cur = dummyHead;
        while (cur.next != null) cur = cur.next;
        cur.next = new ListNode(val);
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) prev = prev.next;
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next = prev.next.next;
        size--;
    }
}

양방향 연결 리스트 구현

양방향 연결 리스트는 앞뒤로 탐색이 가능하며, 인덱스가 중앙 근처인지 끝 근처인지 판단하여 효율적인 탐색을 수행할 수 있습니다.

class MyLinkedList {
    private int size;
    private ListNode head, tail;

    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode cur = index >= size / 2 ? tail : head;
        for (int i = 0; i < (index >= size / 2 ? size - index : index + 1); i++) {
            cur = index >= size / 2 ? cur.prev : cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        ListNode prev = head;
        for (int i = 0; i < index; i++) prev = prev.next;
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next.prev = newNode;
        newNode.prev = prev;
        prev.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        ListNode prev = head;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next.next.prev = prev;
        prev.next = prev.next.next;
        size--;
    }
}

206. 연결 리스트 반전

반전은 세 개의 포인터를 사용하여 순차적으로 연결을 뒤집는 방식입니다.

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    ListNode nextTemp = null;

    while (current != null) {
        nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

재귀 방식 (후행 재귀)

끝까지 도달한 후, 돌아오면서 연결을 뒤집습니다.

public ListNode reverseList(ListNode node) {
    if (node == null || node.next == null) return node;
    
    ListNode last = reverseList(node.next);
    node.next.next = node;
    node.next = null;
    return last;
}

재귀의 구조를 명확히 이해하고, 매번 호출 스택의 상태를 추적하는 연습이 필요합니다.