[알고리즘와 자료구조] 노드 기반 자료 구조

📖 '누구나 자료구조와 알고리즘'책을 공부한 내용을 담고 있습니다.

14장 노드 기반 자료 구조

14.1 연결 리스트

연결 리스트(Linked List)
항목의 리스트를 표현하는 자료 구조

연결 리스트는 배열과 다르게 동작한다. 연결 리스트 내 데이터는 연속된 메모리 블록이 아니라 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다.
메모리에 곳곳에 흩어진 연결된 데이터는 노드(node)라 부른다. 그렇다면, 노드가 메모리 내에 서로 인접해 있지 않다면, 같은 연결 리스트에 속하는지 어떻게 알까?

연결 리스트 내 데이터 옆에는 다음 노드의 메모리 주소도 포함된다.

연결 리스트 ["a","b","c","d"]가 있다. 하지만 데이터를 저장하는 데 첫 번째 셀에는 실제 데이터가 들어 있고, 두 번째 셀에는 다음 노드의 시작 메모리 주소(링크)가 들어 있다. 마지막 노드의 링크는 null이다. 각 링크를 따라 전체 리스트를 연결하면 연결 리스트가 된다.

데이터	링크
"a"	1652

데이터	링크
"b"	1983

데이터	링크
"c"	2001

데이터	링크
"d"	null

14.2 연결 리스트 구현

연결 리스트를 코드로 구현해 보면, Node와 LinkedList라는 두 클래스로 구현한다. Node 클래스는 "once", "upon", "a", "time"이라는 문자열을 포함한 네 개의 노드로 이뤄진 리스트를 생성한다. next_node는 노드의 링크 역할을 하며, 실제 메모리 주소 대신 또 다른 Node 인스턴스를 참조한다. 그래도 결과는 같다. data 매서드는 노드의 데이터를 반환하고, next_node 매서드는 다음 노드를 반환한다. Linked List 클래스는 첫 번째 노드를 추적한다. 연결 리스트는 첫 번째 노드에만 즉시 접근할 수 있다.

class Node {
    constructor(data) {
        this.data = data;
        this.next_node = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    add(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next_node) {
                current = current.next_node;
            }
            current.next_node = newNode;
        }
    }
}

14.3 읽기

연결 리스트에서 읽기의 효율성을 알아보자. 연결 리스트는 배열처럼 1단계로 바로 값을 읽을 수 없다. 프로그램은 연결 리스트의 첫 번째 노드의 메모리 주소만 안다.

만약 세 번째 노드를 읽기 위해서는, 첫 번째 노드부터 링크를 따라 세 번째 노드로 가야 한다. 노드가 N일 때, 리스트의 마지막 노드를 읽으려면 N 단계가 걸린다.

• 코드 구현: 연결 리스트 읽기

class LinkedList {
    // 기존 코드

    read(index) {
        let current_node = this.head;
        let current_index = 0;

        while (current_node && current_index < index) {
            current_node = current_node.next_node;
            current_index++;
        }

        return current_node ? current_node.data : null;
    }
}

read 매서드에 찾는 노드의 인덱스를 넣는다. 첫 번째 노드부터 접근한다. 현재 인덱스를 기록해 언제 원하는 인덱스에 도달하는지 안다.

while문을 통해 현재 인덱스가 찾는 인덱스보다 작은 때까지 루프를 실행한다.
다음 노드에 접근해 그 노드를 새 current_node로 만든다. current_index도 1씩 증가한다.

원하는 노드에 도달하면 현재 노드의 값을 반환하고, current_node가 없으면, 리스트 끝에 도달했기 때문에 null를 반환한다.

14.4 검색

리스트 검색은 리스트 내 값을 찾아서 그 인덱스를 반환하는 것이다. 연결 리스트의 검색 속도는 O(N)이다.
리스트 검색 과정은 읽기와 비슷한 과정이다.

class LinkedList {
    // 기존 코드

    search(value) {
        let current_node = this.head;
        let current_index = 0;

        while (current_node) {
            if (current_node.data === value) {
                return current_index;
            }
            current_node = current_node.next_node;
            current_index++;
        }

        return null;
    }
}

14.5 삽입

배열에서는 값을 삽입할 때 다른 데이터를 이동해야되기 때문에 효율성이 O(N)이었다. 연결 리스트에서는 데이터를 이동하지 않아도 되기 때문에 성능 면에서 이점이 있다. 맨 앞에 값을 삽입할 때는 1단계가 걸린다. 중간 데이터에 값을 삽입할 때는 이전 데이터의 링크를 연결하기 위해서 해당 인덱스를 찾아서 삽입한다. 최악의 경우, N + 1 단계 걸린다.

배열과 연결 리스트의 상황에 따른 성능 차이는 정반대이다.

시나리오	배열	연결 리스트
앞에삽입	최악의 경우	최선의 경우
중간에삽입	평균적인 경우	평균적인경우
끝에삽입	최선의 경우	최악의 경우

• 코드 구현: 삽입

class LinkedList {
    // 기존 코드

    insert(index, data) {
        const newNode = new Node(data);

        if (index === 0) {
            newNode.next_node = this.head;
            this.head = newNode;
            return;
        }

        let current_node = this.head;
        let current_index = 0;

        while (current_node && current_index < index - 1) {
            current_node = current_node.next_node;
            current_index++;
        }

        if (current_node) {
            newNode.next_node = current_node.next_node;
            current_node.next_node = newNode;
        }
    }
}

14.6 삭제

배열과 연결 리스트의 시나리오 대조는 삽입과 똑같다.

연결 리스트 삭제에서 첫 번째 노드 삭제할 경우, 첫 번째 노드를 두 번째 노드로 바꾸면 되고, 다른 노드를 삭제할 경우, 삭제하려는 노드의 앞의 노드에 접근해서 해당 노드의 링크를 삭제하려는 노드의 뒤 노드를 가리키도록 바꾼다. 삭제된 노드는 연결리스트에서만 제거될 뿐, 메모리에는 남게 된다.

• 코드 구현

class LinkedList {
    // 기존 코드

    delete(index) {
        if (index === 0 && this.head) {
            this.head = this.head.next_node;
            return;
        }

        let current_node = this.head;
        let current_index = 0;

        while (current_node && current_index < index - 1) {
            current_node = current_node.next_node;
            current_index++;
        }

        if (current_node && current_node.next_node) {
            current_node.next_node = current_node.next_node.next_node;
        }
    }
}

14.7 연결 리스트 연산의 효율성

배열과 연결리스트의 시간 복잡도를 비교해보면 연결 리스트가 그렇게 효율적인진 않다. 연결 리스트를 효과적으로 쓰러면 삽입과 삭제 단계에서 O(1)이라는 점을 활요해야 한다.

14.8 연결 리스트 다루기

연결 리스트는 삽입이나 삭제할 때 다른 데이터를 이동하지 않아도 된다는 점이 좋다. 만약 배열에서 1000개의 이메일에서 하나의 이메일을 삭제하려면, 많은 양의 데이터를 이동시켜야 한지만, 연결 리스트는 그렇지 않아도 된다는 점이 장점이다.

14.9 이중 연결 리스트

이중 연결 리스트는 연결 리스트의 변형 중 하나로, 각 노드에 2개의 링크가 있다는 특징이 있다. 한 링크는 다음 노드를, 다른 한 링크는 앞 노드를 가리킨다. 첫 노드 뿐만 아니라 마지막 노드를 알고 있어서, 마지막 노드 읽기, 삽입, 삭제할 때도 1단계 걸린다.

앞과 뒤로 이동

일반 연결 리스트는 링크에 다음 노드의 주소만 있기 때문에 앞으로만 이동 가능하다. 하지만 이중 연결 리스트는 앞과 뒤의 주소를 알고 있어서 앞 뒤로 이동할 수 있다.

14.10 이중 연결 리스트 기반 큐

이중 연결 리스트는 O(1) 시간 복잡도로 데이터를 삽입/삭제할 수 있기 때문에 큐를 위한 완벽한 내부 자료구조다.

큐는 데이터의 끝에서 삽입할 수 있고, 앞에서만 삭제할 수 있다. 배열로 구현했을 때 삽입은 O(1)이지만, 삭제할 때 O(N)이 걸린다.
반면, 이중 연결 리스트는 끝에서 삽입하고 앞에서 삭제하는 데 모두 O(1)이다. 따라서 큐를 구현하는데 완벽하다.

요약

연결 리스트는 배열과 다른 방식으로 데이터를 저장한다. 연결 리스트는 동적 메모리 할당, 삽입, 삭제 등의 작업에서 유리하지만, 인덱스 접근 속도에서는 배열보다 느릴 수 있다. 이중 연결 리스트와 같은 변형을 통해 데이터 구조의 유연성을 높일 수 있다. 이중 연결 리스트는 큐와 같은 자료 구조를 효율적으로 구현하는 데 유용하다.