단일 연결리스트

5 min read

단일 연결리스트는 각 노드가 데이터와 다음 노드를 가리키는 next 포인터를 가진 자료구조다. 배열처럼 데이터가 메모리에 붙어 있을 필요가 없고, 노드들이 next를 통해 한 방향으로 이어진다.

head -> [data | next] -> [data | next] -> [data | next] -> null

이 구조의 장점은 앞쪽 삽입과 삭제가 단순하다는 것이다. 새 노드를 만들고 그 노드의 next를 기존 head로 연결한 뒤, head를 새 노드로 바꾸면 된다. 데이터 전체를 밀어낼 필요가 없으므로 O(1)에 끝난다.

void addFirst(int data) {
    Node node = new Node(data);
    node.next = head;
    head = node;
}

반대로 인덱스 접근은 약하다. list.get(1000)을 하려면 head에서 시작해서 next를 1000번 따라가야 한다. 배열처럼 주소를 계산해서 바로 이동할 수 없기 때문에 접근은 O(n)이다.

삽입과 삭제를 볼 때 주의할 점

연결리스트를 설명할 때 “삽입/삭제가 O(1)”이라고만 말하면 반쪽짜리 답변이 된다. 정확히는 삽입하거나 삭제할 위치의 노드 참조를 이미 알고 있을 때 O(1)이다. 그 위치를 찾기 위해 처음부터 탐색해야 한다면 탐색 비용 O(n)이 먼저 든다.

예를 들어 특정 값을 삭제하려면 보통 이전 노드를 알아야 한다. 단일 연결리스트에서는 현재 노드가 이전 노드를 모른다. 그래서 head부터 따라가며 삭제 대상의 직전 노드를 찾아야 한다.

void delete(int target) {
    if (head == null) return;
 
    if (head.data == target) {
        head = head.next;
        return;
    }
 
    Node prev = head;
    while (prev.next != null && prev.next.data != target) {
        prev = prev.next;
    }
 
    if (prev.next != null) {
        prev.next = prev.next.next;
    }
}

단일 연결리스트가 어울리는 상황

단일 연결리스트는 한 방향으로만 처리해도 충분하고, 앞쪽 삽입/삭제가 많거나 노드를 하나씩 이어 붙이는 구조가 자연스러울 때 쓸 수 있다. 다만 일반적인 리스트처럼 get(index)를 자주 하거나, 전체 데이터를 빠르게 순회해야 하는 경우에는 배열이나 동적 배열이 더 나은 경우가 많다.

면접 문제에서는 연결리스트 뒤집기, 사이클 탐지, 중간 노드 찾기 같은 문제가 자주 나온다. 이 문제들은 연결리스트 자체를 실무에서 많이 쓰느냐와 별개로, 포인터를 잃지 않고 순서를 바꾸는 감각을 보기 좋기 때문이다.

Node reverse(Node head) {
    Node prev = null;
    Node cur = head;
 
    while (cur != null) {
        Node next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
 
    return prev;
}

면접에서 말할 포인트

단일 연결리스트는 next만 따라가는 한 방향 구조다. 앞쪽 삽입/삭제는 O(1)이지만, 특정 위치 접근이나 값 탐색은 O(n)이다. 삽입/삭제가 O(1)이라는 말은 위치를 이미 알고 있다는 전제가 붙는다. 이 전제를 함께 말해야 배열과 연결리스트의 차이를 더 정확하게 설명할 수 있다.

Backlinks