연결 리스트

배열(리스트)은 크기가 고정되어 있고,

중간에 다른 원소를 넣고 빼려면 다른 원소들까지 옮겨야 하므로 비싼 연산을 수반한다.

연결 리스트는 일련의 원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는다.

리스트는 참조 정보가 포함된 Node로  구성된다.

 

Node(Head) -> Node ->... -> Node -> NULL

LinkedList 클래스

class LinkedList {
    constructor() {
        this.length = 0;  // 전체 Node 개수
        this.head = null; // 첫 Node
    }
}

Node 정의.

LinkedList.prototype.Node = class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

맨 끝에 추가할 때는 Node가 하나라도 있을 때랑 하나도 없을 때를 구분해야 한다. (하나라도 있다면 head는 바뀌지 않으니까)

    // 리스트의 맨 끝에 원소 추가
    append(element) {
        const Node = this.Node;
        let node = new Node(element), current;

        if (this.head === null) { // head가 비어있다면
            this.head = node;
        } else {
            current = this.head;

            // 마지막 원소를 발견할 때까지 계속 루프 순환한다.
            while (current.next) {
                current = current.next;
            }

            // 마지막 원소를 링크할 수 있게 노드를 할당한다.
            current.next = node;
        }

        this.length++;

        return this;
    }

삭제할 때 역시 지우려는 Node가 첫 번째 Node인지 아닌지에 따라 달라진다.

    // 해당 위치에 원소 삭제
    removeAt(position) {
        // 범위 외의 값인지 체크한다.
        if (position > -1 && position < this.length) {
            let current = this.head, previous, index = 0;

            // 첫 번째 원소 삭제
            if (position === 0) {
                this.head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.length--;

            return current.element;
        } else {
            return false;
        }
    }

해당 position에 element를 넣는 메서드도 첫 번째에 넣냐 아니냐에 따라 달라진다.

    // 해당 위치에 원소 삽입
    insert(position, element) {
        const Node = this.Node;
        if (position > -1 && position < this.length) {
            let node = new Node(element), current = this.head, previous, index = 0;

            if (position === 0) {
                node.next = current;
                this.head = node;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }

                node.next = current;
                previous.next = node;
            }

            this.length++;

            return true;
        } else {
            return false;
        }
    }

 전체 구현을 해보면

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

    // 리스트의 맨 끝에 원소 추가
    append(element) {
        const Node = this.Node;
        let node = new Node(element), current;

        if (this.head === null) { // head가 비어있다면
            this.head = node;
        } else {
            current = this.head;

            // 마지막 원소를 발견할 때까지 계속 루프 순환한다.
            while (current.next) {
                current = current.next;
            }

            // 마지막 원소를 링크할 수 있게 노드를 할당한다.
            current.next = node;
        }

        this.length++;

        return this;
    }

    // 해당 위치에 원소 삽입
    insert(position, element) {
        const Node = this.Node;
        if (position > -1 && position < this.length) {
            let node = new Node(element), current = this.head, previous, index = 0;

            if (position === 0) {
                node.next = current;
                this.head = node;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }

                node.next = current;
                previous.next = node;
            }

            this.length++;

            return true;
        } else {
            return false;
        }
    }

    // 해당 위치에 원소 삭제
    removeAt(position) {
        // 범위 외의 값인지 체크한다.
        if (position > -1 && position < this.length) {
            let current = this.head, previous, index = 0;

            // 첫 번째 원소 삭제
            if (position === 0) {
                this.head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.length--;

            return current.element;
        } else {
            return false;
        }
    }

    // 원소를 삭제
    remove(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }

    // 해당 원소의 인덱스 반환
    indexOf(element) {
        let current = this.head, index = 0;

        while (current) {
            if (element === current.element) {
                return index;
            }

            index++;
            current = current.next;
        }

        return -1;
    }

    // 원소가 하나도 없으면 true 아니면 false
    isEmpty() {
        return this.length === 0;
    }

    // 전체 원소 개수
    size() {
        return this.length;
    }

    // 원소의 값만 출력하려면 객체의 toString메서드를 overriding해야한다.
    toString() {
        let current = this.head, string = '';

        while (current) {
            string += current.element;
            current = current.next;
        }

        return string;
    }

    getHead() {
        return this.head;
    }
}

사용 예시

const ll = new LinkedList();;
ll.append(1);
ll.append(2);
ll.append(4);
console.log(ll.size()); // 3
ll.insert(2, 3);
console.log(ll.size()); // 4
ll.removeAt(1);
console.log(ll.size()); // 3

 

 

 

 

참고문헌: Learning Javascript Data Structures and Algorithm - 로이아니 그로네즈

git repository: https://github.com/taeheongo/Data-Structures-and-ALgorithm