이 글에서는 배열과 연결리스트에 대해서 알아보겠다.

배열과 연결리스트는 모두 선형 자료구조로 비슷하면서도 반대의 특성을 가지고 있다.

배열은 데이터를 물리적 주소에 순차적으로 저장하며 인덱스를 가지고 있어 바로 접근할 수 있기 때문에 접근 속도가 매우 빠르다. 그러나, 배열은 크가가 고정되어 있기 때문에 처음 지정된 사이즈보다 더 많은 데이터를 넣으려면 배열의 크기를 늘리는 연산을 해야하고 데이터 삽입/삭제시 해당 위치 다음칸에 있는 데이터를 모두 한칸씩 뒤로 밀거나 앞으로 당겨오는 연산을 해야하기 때문에 데이터 삽입/삭제에는 약한 모습을 보인다.

연결리스트는 데이터를 저장할 때 데이터만 저장하는 것이 아니라 다음 데이터의 물리적 주소까지 같이 저장한다. (단순 연결리스트는 다음 데이터의 주소를, 이중 연결리스트는 이전 주소와 다음 주소를 모두 저장)

특정 데이터에 접근할 때 인덱스로 바로 접근할 수 있었던 배열과 달리 첫 노드부터 원하는 노드까지 링크를 따라가야 접근이 가능하기 때문에 배열에 비해 접근 속도는 떨어진다.

하지만 반대로, 데이터를 삽입/삭제 할 때에는 물리적 주소에 구애받지 않고 앞/뒤 노드의 주소만 끼워넣을 노드의 주소로 바꿔주면 되기 때문에 삽입/삭제는 배열보다 빠르다.

자바스크립트로 구현한 양방향 연결리스트(Double Linked List)

/**
 * 연결리스트(LinkedList)에서 사용할 노드 클래스
 */
class Node {
    constructor(_prev, _data, _next) {
        this.prev = _prev;
        this.data = _data;
        this.next = _next;
    }
}

/**
 * LinkedList 자료구조 클래스
 */
class LinkedList {
    constructor() {
        let head = null;
        let tail = null;
        let size = 0;

        /**
         * 해당 인덱스의 노드를 반환
         */
        const node = (index) => {
            if (index < size / 2 ) {
                // 인덱스가 사이즈의 절반보다 작으면 앞(head)에서부터부터 탐색
                let cursor = head;
                for (let i = 0; i < index; i++) {
                    cursor = cursor.next;
                }
                return cursor;
            } else {
                // 인덱스가 사이즈의 절반보다 크면 뒤(tail)에서부터 탐색
                let cursor = tail;
                for (let i = size -1; i > index; i--) {
                    cursor = cursor.prev;
                }
                return cursor;
            }
        };

        /**
         * 리스트의 맨 앞에 노드를 추가
         * @param data
         */
        this.addFirst = (data) => {
            const newNode = new Node(null, data, head);
            if (head !== null) {
                head.prev = newNode;
            }
            head = newNode;
            size ++;
            if (head.next === null) {
                tail = newNode;
            }
        };

        /**
         * 리스트의 맨 뒤에 노드를 추가
         * @param data
         */
        this.addLast = (data) => {
            const newNode = new Node(tail, data, null);
            if (tail !== null) {
                tail.next = newNode;
            }
            tail = newNode;
            size ++;
            if (tail.prev === null) {
                head = newNode;
            }
        };

        /**
         * 인덱스를 지정해 노드를 추가
         * @param k
         * @param data
         */
        this.add = (k, data) => {
            const prev = node(k-1);
            if (prev === null) {
                this.addFirst(data);
            } else {
                const next = prev.next;
                const newNode = new Node(prev, data, next);
                prev.next = newNode;
                if (next !== null) {
                    next.prev = newNode;
                }
                size ++;
                if (next === null) {
                    tail = newNode;
                }
            }
        };

        /**
         * 리스트의 맨 앞 노드를 삭제
         */
        this.removeFirst = () => {
            if (head) {
                let temp = head;
                head = temp.next;
                if (head === null) {
                    tail = null;
                } else {
                    head.prev = null;
                }
                temp = null;
                size--;
            }
        };

        /**
         * 리스트의 맨 뒤 노드를 삭제
         */
        this.removeLast = () => {
            if (tail) {
                let temp = tail;
                tail = temp.prev;
                if (tail === null) {
                    head = null;
                } else {
                    tail.next = null;
                }
                temp = null;
                size --;
            }
        };

        /**
         * 인덱스를 지정해 노드를 삭제
         * @param index
         */
        this.remove = (index) => {
            let target = node(index);
            if (target) {
                const prev = target.prev;
                const next = target.next;

                if (prev === null) {
                    return this.removeFirst();
                }

                if (next === null) {
                    return this.removeLast();
                }

                prev.next = target.next;
                next.prev = target.prev;
                target = null;
                size --;
            }
        };

        /**
         * Head를 반환
         */
        this.getHead = () => head;

        /**
         * Tail을 반환
         */
        this.getTail = () => tail;

        /**
         * 해당 인덱스의 노드를 반환
         * @param k
         */
        this.get = (k) => node(k);

        /**
         * 리스트의 크기를 반환
         */
        this.size = () => size;

    }
}

const linkedList = new LinkedList();

//-----삽입-----
linkedList.addFirst('사과'); // 사과
linkedList.addFirst('귤'); // 귤-사과
linkedList.addLast('바나나'); // 귤-사과-바나나
linkedList.addLast('오렌지'); // 귤-사과-바나나-오렌지
linkedList.add(2, '레몬'); // 귤-사과-레몬-바나나-오렌지

//-----삭제-----
linkedList.removeFirst(); // 사과-레몬-바나나-오렌지
linkedList.removeLast(); // 사과-레몬-바나나
linkedList.remove(0); // 사과-바나나

//-----리스트 출력-----
const result = [];
let cursor = linkedList.getHead();

while(cursor) {
    result.push(cursor.data);
    cursor = cursor.next;
}

console.log(result);