1. Linked List ( 링크드 리스트, JavaScript 구현 )

Linked List ( 연결 리스트 )

linked list란?

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

구조

노드(Node)와 링크(Link)로 구성되며,

노드는 실제 정보를 담고 있는 하나의 단위이고,

링크는 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리라 할 수 있다.

노드의 시작점은 head, 끝점은 tail이라 부르며 노드의 추가, 삭제, 탐색이 가능하다.

 

종류

단일 연결 리스트 ( Singly Linked List )

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트 ( Doubly Linked List )

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

원형(환형) 연결 리스트 ( Circular Linked List )

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

 

배열과의 비교

배열은 각 값마다 고유한 인덱스를 가지고 있다.

이는 탐색에는 매우 유리하지만 삽입이나 삭제를 하는 부분에서 단점이 있다.

예를 들어 [1,2,3,5,6] 라는 배열에서 3과 5사이에 4를 삽입하고 싶다면

5,6의 인덱스를 뒤로 한칸씩 밀고 4를 빈 자리에 넣어줘야 한다.

위와 같은 과정은 배열의 복사, 이동을 통해 생기며, 삽입, 삭제의 규모가 커진다면 이는 많은 소요를 필요로 한다.

링크드 리스트는 이러한 단점을 해결하기 위해 나왔다.

링크드 리스트에서의 삽입은 삽입할 노드를 삽입할 위치의 이전노드, 다음노드와 연결만 해주면 되고,

삭제도 마찬가지로 삭제하고 싶은 노드에 연결되어있는 앞 뒤의 노드를 서로 이어주면 된다.

하지만 링크드 리스트는 탐색을 위해서는 항상 첫번째 노드부터 비교해야한다 하는 단점이 있다.

위에서 설명한 내용과 같이, 배열과 링크드 리스트는 장단점이 반대이므로

데이터 탐색이 많이 필요한 상황에서는 배열을 사용하고

데이터 삽입, 삭제가 많이 필요한 상황에서는 링크드 리스트를 사용하는 것이 효율적이다.

추가로 기본적인 두가지의 장점을 합쳐놓은 Chunked List, 이를 발전시킨 B+ 트리라는 자료 구조가 있다.

생활코딩 그림과 예제로 쉽게 차이를 알려주고 있음.

 

구현

1. 기본적인 단일 연결 리스트

const LinkedList = (() => {
    class LinkedList {
        constructor() {
            this.length = 0;
            this.head = null;
        }
     }

    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return LinkedList;
})();

연결 리스트와, 노드 클래스를 생성해주었고,

데이터 추가, 삭제, 탐색을 아래에 구현해 보면 다음과 같다.

 

2. 추가 ( add )

    add(value) {
        const node = new Node(value);
        let current = this.head;
        if ( !current ) {
            this.head = node;
            this.length++;
            return node;
        } else {
            while(current.next) {
            current = current.next;
        }
        current.next = node;
        this.length++;
        return node;
    }

위의 추가 메소드는 position을 인자로 받지 않고, 리스트의 맨 뒤에 추가만 가능한 메소드이다.

add 메소드에 value값을 넣어주면 새로운 Node 인스턴스를 생성 해주고

if문에서 현재 head가 비어있다면, 즉 리스트가 비어있다면 node를 head에 넣어주고

아니라면 next가 null일 때 까지 이동 후에 현재노드의 next에 추가해주고 length를 1 더해준다.

추가가 완료되면 추가한 노드를 리턴해준다.

 

3. 삭제 ( remove )

    remove(position) {
        let current = this.head;
        let before, remove, count = 0;

        if ( position === 0 ) {
            remove = this.head;
            this.head = this.head.next;
        } else {
            while (count < position) {
                before = current;
                remove = current.next;
                count++;
                current = current.next;
            }
            before.next = remove.next;
        }
        this.length--;
        return remove;
    }

remove 메소드에 position을 넣어 position에 있는 노드를 삭제해준다.

이때, position을 배열의 index라 생각하면 이해가 쉬움

하지만 배열과 다르게 삭제하려는 위치(position)까지 가려면 head부터 순차적으로 탐색해서 가야함.

if문에서 0번 노드, 즉 head를 삭제한다면

기존 head의 다음 노드를 head로 이동한 뒤에 length를 1 줄이고 삭제한 노드를 리턴해준다.

이외의 경우에서는

while문으로 next로 한칸씩 이동해서 position까지 찾아간 뒤에

해당 position의 노드를 삭제해주고, 삭제된 노드의 이전 노드와 다음 노드를 연결, length를 1 줄이고 삭제한 노드를 리턴해준다.

 

4. 탐색 ( search )

    search(position) {
        let current = this.head;
        let count = 0;
        while (count < position) { // position 위치만큼 이동합니다.
            current = current.next;
            count++;
        }
        return current.data;
    }

position위치의 노드를 찾기 위해 사용하는 메소드.

위의 remove와 비슷하게 작동하며, position까지 이동을 완료하면 해당 노드의 데이터를 리턴해준다.

 

전체 코드

const LinkedList = (() => {

    // LinkedList 클래스
    class LinkedList {
        constructor() {
            this.length = 0;
            this.head = null;
        }

        // 추가 메소드
        add(value) {
            const node = new Node(value);
            let current = this.head;
            if (!current) {
                this.head = node;
                this.length++;
                return node;
            } else {
                while(current.next) {
                      current = current.next;
                }
                current.next = node;
                this.length++;
                return node;
            }
        }        

        // 삭제 메소드
        remove(position) {
            let current = this.head;
            let before, remove, count = 0;

            if ( position === 0 ) {
                remove = this.head;
                this.head = this.head.next;
            } else {
                while (count < position) {
                    before = current;
                    remove = current.next;
                    count++;
                    current = current.next;
                }
                before.next = remove.next;
            }
            this.length--;
            return remove;
        }

        // 탐색 메소드
        search(position) {
            let current = this.head;
            let count = 0;
            while (count < position) {
                current = current.next;
                count++;
            }
            return current.data;
        }
    }

    // Node 클래스
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }

    return LinkedList;
})();