단일 대 이중 연결 목록

이 블로그에서는 JavaScript의 단일 연결 목록과 이중 연결 목록을 간략하게 비교합니다.

목록이란 무엇입니까?

목록은 객체의 순서를 유지하는 데 사용되는 데이터 구조입니다. array 과 달리 목록은 JavaScript의 실제 데이터 유형이 아니며 해당 항목에 색인을 제공하지 않습니다. 대신 목록이 생성되고 노드를 사용하여 목록 유형에 따라 순서를 유지하기 위해 이전 또는 다음 노드를 가리킵니다.

단일 연결 목록

단일 연결 목록을 만들려면 먼저 노드를 나타내는 클래스 또는 목록에서 수집하는 항목을 만듭니다. 이 클래스는 목록에 추가할 각 항목의 청사진을 나타냅니다.

아래 예에서는 Color를 노드 클래스로 사용하고 있습니다. 각 색상에는 이름과 목록의 다음 색상을 참조하는 속성.next이 있습니다. .next 속성은 색상이 생성될 때 기본적으로 null로 설정됩니다.

class Color {
    constructor(name){
        this.name = name;
        this.next = null;
    }
}

이 클래스Color를 사용하여 새 색상을 만들 수 있지만 다음 예제에서는 목록에서 처리하도록 하겠습니다.
Rainbow 클래스는 정렬된 목록을 유지하는 데 사용됩니다. push 메서드는 클래스 내부에 정의되어 있으며 목록 끝에 항목을 만들고 추가하는 데 사용됩니다.

class Rainbow {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(name){
        let newColor = new Color(name);
        if(this.length === 0) {
            this.head = newColor;
            this.tail = this.head;
        } else {
            this.tail.next = newColor;
            this.tail = newColor;
        }
        this.length++;
        return this;
    }

let list = new Rainbow()
list.push("Red")
list.push("Orange")
list.push("Yellow")

console.log(list)
// Rainbow {
//     head: Color { name: 'Red', next: Color { name: 'Orange', next: [Color] } },
//     tail: Color { name: 'Yellow', next: null },
//     length: 3
//   }

Singly Linked List는 헤드(빨간색)에서 테일(노란색)까지 한 방향으로만 흐릅니다.

마지막 값에 도달할 때까지 .next 항목을 찾기 위해 각 항목을 반복해야 하므로 Singly Linked List의 마지막 항목에 액세스하려고 할 때 시간에 신경을 쓰는 경우 문제가 될 수 있습니다. 작은 목록의 경우 문제가 되지 않을 수 있지만 목록이 커질수록 마지막 항목까지 반복하는 데 더 많은 시간이 걸리므로 선형 시간(O(n))의 Big O가 제공됩니다.

class Rainbow {

    ...

    get(index){ 
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let color = this.head;
        while (counter !== index) {
            color = color.next;
            counter++;
        }
        return color;
    }
}

list.get(1) // this is index of 1, so the 2nd item, Orange
// Color { name: 'Orange', next: Color { name: 'Yellow', next: null } }

이중 연결 목록

이중 연결 목록은 단일 연결 목록과 거의 동일하지만 목록의 이전 항목을 나타내는 prev라는 추가 속성이 있습니다. 이렇게 하면 목록에서 앞으로 또는 뒤로 이동할 수 있습니다.

class Color {
    constructor(name){
        this.name = name;
        this.next = null;
        this.prev = null;
    }
}

class Rainbow {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(name){
        let newColor = new Color(name);
        if(this.length === 0) {
            this.head = newColor;
            this.tail= newColor;
        } else {
            this.tail.next = newColor;
            newColor.prev = this.tail;
            this.tail = newColor;
        }
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        let count, color;
        if (index <= this.length/2){
            count = 0
            color = this.head;
            while (count != index){
                color = color.next;
                count++;
            }
            console.log("Moved Forward")
        } else {
            count = this.length - 1;
            color = this.tail;
            while (count != index){
                color = color.prev;
                count--;
            }
            console.log("Moved Backward")
        }
        return color;
    }
}

let list = new Rainbow()
list.push("Red")
list.push("Orange")
list.push("Yellow")

console.log(list)
// Rainbow {
//     head: <ref *1> Color {
//       name: 'Red',
//       next: Color { name: 'Orange', next: [Color], prev: [Circular *1] },
//       prev: null
//     },
//     tail: <ref *2> Color {
//       name: 'Yellow',
//       next: null,
//       prev: Color { name: 'Orange', next: [Circular *2], prev: [Color] }
//     },
//     length: 3
//   }

list.get(0)
// "Moved Forward"
// <ref *2> Color {
//   name: 'Red',
//   next: <ref *1> Color {
//     name: 'Orange',
//     next: Color { name: 'Yellow', next: null, prev: [Circular *1] },
//     prev: [Circular *2]
//   },
//   prev: null
// }

list.get(2)
// "Moved Backward"
// <ref *1> Color {
//   name: 'Yellow',
//   next: null,
//   prev: <ref *2> Color {
//     name: 'Orange',
//     next: [Circular *1],
//     prev: Color { name: 'Red', next: [Circular *2], prev: null }
//   }
// }

단일 연결 목록과 이중 연결 목록의 차이점

간단히 말해서 주요 차이점은 Singly Linked List는 한 방향으로만 이동할 수 있다는 것입니다. 이는 목록 끝에 있는 항목에 액세스해야 하는 경우 바람직하지 않을 수 있습니다. 이중 연결 목록은 역방향으로 이동할 수 있는 추가 속성.prev을 추적합니다. Doubly Linked List로 접근하면 시간이 단축되지만 추가 변수를 메모리에 저장해야 합니다.