[자료구조] 단일 & 이중 연결 리스트 - javascript

들어가기 전에...

해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 강의에 나온 코드를 최대한 효율적이고 수정했기에 강의 속 코드보다 좋은 코드일 것이라 생각한다.

📌 단일 연결 리스트

// 노드 형식
class Node { 
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

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

    // 맨 뒤에 노드 추가
    push(val) {
        let newNode = new Node(val);

        if (!this.head) {
            // 만약 head가 없다면
            this.head = newNode; // next에 newNode를 연결
            this.tail = this.head; // tail도 head로 설정 => 첫 값이기 때문에
        } else {
            // 만약 head가 있다면
            this.tail.next = newNode; // next에 newNode 연결
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

    // 맨 뒤 노드 추출
    pop() {
        if (!this.head) return undefined;

        let current = this.head;
        let newTail = current;

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

        this.tail = newTail;
        this.tail.next = null;
        this.length--;

        if (this.length === 0) {
            // 요소가 하나일 때 예외처리
            this.head = null;
            this.tail = null;
        }
        return current;
    }

    // 맨 앞 노드 추출
    shift() {
        if (!this.head) return undefined;

        let current = this.head;
        this.head = current.next;
        this.length--;
        if (this.length === 0) this.tail = null;
        return current;
    }

    // 맨 앞 노두 추가
    unshift(val) {
        let newNode = new Node(val);

        newNode.next = this.head;
        this.head = newNode;

        if (!this.head) {
            this.tail = this.head;
        }

        this.length++;
        return this;
    }

    // 특정 인덱스의 노드 얻기
    get(index) {
        if (index < 0 || index >= this.length) return null;

        let count = 0;
        let current = this.head;

        while (count !== index) {
            current = current.next;
            count++;
        }

        return current.val;
    }

    // 특정 인덱스의 노드 수정
    set(index, val) {
        let foundNode = this.get(index);
        if (foundNode) {
            foundNode.val = val;
            return true;
        }
        return false;
    }

    // 특정 인덱스에 노드 넣기
    insert(index, val) {
        if (index < 0 || index > this.length) return false;

        if (index === 0) this.unshift(val);
        else if (index === this.length) this.push(val);
        else {
            let newNode = new Node(val);
            let pre = this.get(index - 1);
            newNode.next = pre.next;
            pre.next = newNode;
        }

        return true;
    }

    // 특정 인덱스의 노드 삭제
    remove(index) {
        if (index < 0 || index >= this.length) return undefined;

        if (index === 0) return this.shift();
        if (index === this.length - 1) return this.pop();

        let pre = this.get(index - 1);
        let removed = pre.next;
        pre.next = removed.next;
        this.length--;
        return removed;
    }

    // 역순으로 리스트 수정
    reverse() {
        if (this.length === 0 || this.length === 1) return this;

        // head, tail 바꾸기
        [this.head, this.tail] = [this.tail, this.head];
        let cur = this.tail;
        let [pre, next] = [null];

        for (let i = 0; i < this.length; i++) {
            next = cur.next;
            cur.next = pre; // cur의 마지막을 이전 노드로 설정해서 순서 바꾸기
            pre = cur; // 하나씩 pre, cur 이동
            cur = next;
        }

        return this;
    }
}

📌 이중 연결 리스트

// 노드 형식
class Node{
    constructor(val) {
        this.val = val;
        this.next = null;
        this.pre = null;
    }
}

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

    // 맨 뒤에 노드 추가
    push(val) {
        let node = new Node(val);

        if(this.head === null) {
            this.head = node;
        }
        else {
            this.tail.next = node;
            node.pre = this.tail;
        }

        this.tail = node;
        this.length ++;
        return this;
    }

    // 맨 뒤 노드 추출
    pop() {
        if(this.length === 0) return undefined;

        let popedNode = this.tail;

        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = popedNode.pre; // 꼬리 새로 지정
            this.tail.next = null; // 꼬리 연결 끊기

        }
        popedNode.pre = null; // 꼬리 연결 끊기
        this.length --;
        return popedNode;
    }

    // 맨 앞 노드 추출
    shift() {
        if(this.length === 0) return undefined;

        let shiftedNode = this.head;

        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = this.head.next;
            this.head.pre = null;
        }

        shiftedNode.next = null;
        this.length --;
        return shiftedNode;
    }

    // 맨 앞 노드 추가
    unshift(val) {
        let newNode = new Node(val);

        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.pre = newNode;
            this.head = newNode;
        }

        this.length ++;
        return this;
    }

    // 특정 인덱스 값 추출
    get(index) {
        if(index < 0 || index >= this.length) return null;

        let curNode;

        if(index <= this.length/2) {
            curNode = this.head;
            for(let i = 0; i < index; i++) {
                curNode = curNode.next;
            }
        } else {
            curNode = this.tail;
            for(let i = this.length-1; i > index; i--) {
                curNode = curNode.pre;
            }
        }
        return curNode;
    }

    // 특정 인덱스의 노드 수정
    set(index, value) {
        let node = this.get(index);
        if(node) {
            node.val = value;
            return true;
        }
        return false;
    }

    // 특정 인덱스에 노드 추가
    insert(index, value) {
        if(index < 0 || index >= this.length) return false;
        let newNode = new Node(value);

        if(index === 0) this.unshift(value);
        else if(index === this.length-1) this.push(value);
        else {
            let cur = this.get(index);
            cur.pre.next = newNode;
            newNode.pre = cur.pre;
            newNode.next = cur;
            cur.pre = newNode;
        }

        this.length ++;
        return this;
    }

    // 특정 인덱스 삭제
    remove(index) {
        if(index < 0 || index >= this.length) return false;

        this.length --;

        if(index === 0) return this.shift();
        if(index === this.length-1) return this.pop();

        let removedNode = this.get(index);
        let beforeNode = removedNode.pre;
        let afterNode = removedNode.next;
        beforeNode.next = afterNode;
        afterNode.pre = beforeNode;
        removedNode.pre = null;
        removedNode.next = null;
        this.length --;
        return removedNode;
    }
}