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

1. 연결리스트 구조

- 배열이 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조인 반면 연결리스트는 떨어진 곳에 존대하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

- 배열이 미리 데이터 공간을 할당해야 하는 반면 연결 리스트는 미리 데이터 공간을 할당하지 않아도 되는 장점이 있음 (단, 연결을 위한 데이터 공간이 필요하므로 저장공간 효율이 높지 않음)

- 연결정보를 찾는 시간이 필요하므로 접근 속도가 느림

- 중간 데이터 삭제 시 앞뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요함

node	데이터 저장 단위 (데이터값, 포인터) 로 구성
pointer	각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list

2. 연결리스트 구현

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

class Linkedlist {

    constructor() {
        this.head = null;
        this.count = 0; // number of element we have in the list
        //this.equalsFn = eualsFn;
    }


    // 1. Add a new element to the end of the list
    push(element) {
        let node = new Node(element);   // {data: element, next: null}
        let current;

        // If empty make head
        if (this.head == null) {
            this.head = node;
        } else {
            current = this.head;

            while(current.next) {
                current = current.next;
            }

            current.next = node;

        }

        this.count++;

    }

    // 2. Insert a new element at a specified position in the list
    insertByIndex(element, index) {

        if (index >= 0 && index <= this.count) {

            const node = new node(element);
            if (index === 0) {
                const current = this.head;
                node.next = current;
                this.head = node;
            } else {
                const previous = this.getElementAt(index - 1);
                const current = previous.next;
                node.next = current;
                previous.next = node;
            }

            this.count++;
            return true;

        }

        return false;

    }

    // 3. Return the element of a specific position in the list. (search element by index)
    // If the element does not exist in the list, it returns undefined
    getElementAt(index) {
        
        if (index >= 0 && index <= this.count) {

            let node = this.head;
            for (let i = 0; i < index && node != null; i++) {
                node = node.next;
            }
            return node.data;
        }

        return undefined;

    }

    // 4. Remove an element from the list
    remove(element) {
        const index = this.indexOf(element);
        return this.removeAt(index);
    }

    // 5. Return the index of the element in the list
    // If the element does not exist in the list, it returns -1
    indexOf(element) {

        let current = this.head;
        for (let i = 0; i < this.count && current != null; i++) {
            if (element === current.data) {
                return i;
            }
            current = current.next;
        }
        return -1;
    }

    // 6. Remove an item by index
    removeAt(index) {

        if (index >= 0 && index < this.count) {
            let current = this.head;

            if (index === 0) {
                this.head = current.next;   // head.data의 값이 current.next의 값과 같아짐
            } else {
                let previous;
                for (let i = 0; i < index; i++) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.count--;
            return current.data;
        }

        return undefined;

    }

    // 7. isEmpty
    isEmpty() {
        return this.size() === 0;
    }

    // 8. size
    size() {
        return this.count;
    }

    // 9. get Head
    getHead() {
        return this.head;
    }

    // 10. toString
    toString() {

        if (this.head == null) {
            return '';
        }

        let objString = `${this.head.data}`;
        let current = this.head.next;
        for (let i = 0; i < this.size() && current != null; i++) {
            objString = `${objString},${current.data}`;
            current = current.next;
        }
        return objString;
    }

}

const linkedList = new Linkedlist();
linkedList.push(100);
linkedList.push(200);
linkedList.push(300);
linkedList.push(400);
linkedList.push(500);

console.log(linkedList.getElementAt(3));

linkedList.removeAt(2);
console.log(linkedList);

 

3. 이중연결리스트 구조

- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list

 

4. 이중연결리스트 구현

class DoublyNode {
    constructor (element, next, prev) {
        this.element = element;
        this.next = next;
        this.prev;
    }
}

class DoublyLinkedList extends Linkedlist{

    constructor(tail) {
        this.tail = undefined;
    }

    // insert
    insert (element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new DoublyNode(element);   // insert할 node
            let current = this.head;
            if (index === 0) {  // first item
                if (this.head == null) {
                    this.head = node;
                    this.tail = node;
                } else {
                    node.next = this.head;
                    current.prev = node;
                    this.head = node;
                }
            } else if (index === this.count) {  // last item
                current = this.tail;
                current.next = node;
                node.prev = current;
                this.tail = node;
            } else {
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
                current.prev = node;
                node.prev = previous;
            }
            this.count++;
            return true;
        }
        return false;
    }

    // remove
    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index === 0) {
                this.head = current.next;
                // If there is only one item, then we update tail as well NEW
                if (this.count === 1) {
                    this.tail = undefined;
                } else {
                    this.head.prev = undefined;
                }
            } else if (index === this.count - 1) {
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = undefined;
            } else {
                current = this.getElementAt(index);
                const previous = current.prev;
                previous.next = current.next;
                current.next.prev = previous;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }

}

 

소스참고: Learning JavaScript Data Structures and Algorithms