首頁 >web前端 >js教程 >使用 Javascript 處理單鍊錶和雙鍊錶的所有操作:- 最後一站解決方案

使用 Javascript 處理單鍊錶和雙鍊錶的所有操作:- 最後一站解決方案

王林
王林原創
2024-08-14 00:05:12856瀏覽

Approaching Single and Double Linked Lists Using Javascript With All Operations:- Last Stop Solution

連結清單

**1。單鍊錶

  1. 雙向鍊錶**

操作

**_1。前置/附加

  1. 插入中間
  2. 從末尾刪除
  3. 中間刪除
  4. 取得頭/尾
  5. 整體情況
  6. 反向鍊錶
  7. 單向遍歷(單鍊錶)
  8. 雙向遍歷(雙鍊錶)_**

具有所有上述操作的單鍊錶

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

class SingleLinkedList {

    constructor(value) {
        this.head = this.tail = new Node(value);
        this.size = 1;
    }

    append(value) {
        const newNode = new Node(value);
        this.tail.next = newNode;
        this.tail = newNode;
        this.size++;
    }

    prepend(value) {
        const newNode = new Node(value);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }

    insertInMiddle(value) {
        const newNode = new Node(value);
        let currentHead = this.head;
        const pos = Math.floor(this.size/2);
        let counter = 0
        while(currentHead) {
            if (++counter == pos){
                this.size++;
                const temp = currentHead.next;
                currentHead.next = newNode;
                newNode.next = temp;
                break;
            }
            currentHead = currentHead.next;
        }
    }

    traversal() {
        let currentNode = this.head;

        while (currentNode) {
            console.log(currentNode.value);
            currentNode = currentNode.next;
        }
    }

    deleteAtEnd() {
        let currentNode = this.head;

        while(currentNode) {
            if (currentNode.next.next === null) {
                currentNode.next = null;
                this.tail = currentNode;
                this.size--;
            }
            currentNode = currentNode.next;
        }
    }

    deleteAtMiddle() {
        let currentNode = this.head;
        const pos = Math.floor(this.size/2);
        let counter = 0;
        let previousCounter = null;

        while (currentNode) {
            if (counter++ === pos) {
                previousCounter.next = currentNode.next;
                this.size--;
            }
            previousCounter = currentNode;
            currentNode = currentNode.next;

        }
    }

    reverse() {
        let prevNode = null;
        let nextNode = null;
        let currentNode = this.head;

        while (currentNode) {
            nextNode = currentNode.next;
            currentNode.next = prevNode;
            if (prevNode === null) {
                this.tail = currentNode;
            }
            prevNode = currentNode;
            currentNode = nextNode;
        }

        this.head = prevNode;
    }
}


const test = new SingleLinkedList(3);
test.append(5);
test.append(9);
test.prepend(13);
test.prepend(20)
test.insertInMiddle(100);

console.log('Head ---> ', test.head);
console.log('Tail. -> ', test.tail);
console.log('-------------------');

test.traversal();
console.log('----------------After delete at End----------');
test.deleteAtEnd();
test.traversal();
console.log('----------------After delete at Middle----------');
test.deleteAtMiddle();
test.traversal();

console.log('----------------After Reverse Linked List----------');
test.reverse();
test.traversal();
console.log('Head ---> ', test.head);
console.log('Tail. -> ', test.tail);
/*
Head --->  Node {
  value: 20,
  next: Node { value: 13, next: Node { value: 100, next: [Node] } }
}
Tail. ->  Node { value: 9, next: null }
-------------------
20
13
100
3
5
9
----------------After delete at End----------
20
13
100
3
5
----------------After delete at Middle----------
20
13
3
5
----------------After Reverse Linked List----------
5
3
13
20
Head --->  Node {
  value: 5,
  next: Node { value: 3, next: Node { value: 13, next: [Node] } }
}
Tail. ->  Node { value: 20, next: null }
*/

具有上述所有操作的雙鍊錶

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class DoubleLinkedList {
    constructor(value) {
        this.head = this.tail = new Node(value);
        this.size = 1;
    }

    append(value) {
        const newNode = new Node(value);
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
        this.size++;
    }

    prepend(value) {
        const newNode = new Node(value);
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
        this.size++;
    }

    insertAtMiddle(value) {
        if (this.size <= 1) {
            this.append(value);  // If size is 1 or less, append the new node at the end
            return;
        }

        const newNode = new Node(value);
        const pos = Math.floor(this.size / 2);
        let counter = 0;
        let currentNode = this.head;

        while (currentNode) {
            if (counter++ === pos) {
                const nextNode = currentNode.next;
                currentNode.next = newNode;
                newNode.prev = currentNode;
                newNode.next = nextNode;
                if (nextNode) {
                    nextNode.prev = newNode;
                }
                this.size++;
                break;
            }
            currentNode = currentNode.next;
        }
    }

    traverseForward() {
        let currentNode = this.head;
        while (currentNode) {
            console.log(currentNode.value);
            currentNode = currentNode.next;
        }
    }

    traverseReverse() {
        let lastNode = this.tail;
        while (lastNode) {
            console.log(lastNode.value);
            lastNode = lastNode.prev;
        }
    }

    deleteAtEnd() {
        if (this.size === 1) {  // Handle the case where there's only one element
            this.head = this.tail = null;
            this.size = 0;
            return;
        }

        const lastNode = this.tail;
        this.tail = lastNode.prev;
        this.tail.next = null;
        this.size--;

        // Optional: nullify references to help garbage collection
        lastNode.prev = null;
    }

    deleteAtMiddle() {
        if (this.size <= 1) {
            this.deleteAtEnd();  // If size is 1 or less, simply delete the last element
            return;
        }

        let currentNode = this.head;
        const pos = Math.floor(this.size / 2);
        let counter = 0;

        while (currentNode) {
            if (counter++ === pos) {
                const prevNode = currentNode.prev;
                const nextNode = currentNode.next;

                if (prevNode) {
                    prevNode.next = nextNode;
                }
                if (nextNode) {
                    nextNode.prev = prevNode;
                }
                this.size--;

                // Optional: nullify references to help garbage collection
                currentNode.next = currentNode.prev = null;
                break;
            }
            currentNode = currentNode.next;
        }
    }

    reverseList() {
        let currentNode = this.head;
        let prevNode = null;
        let nextNode = null;

        while (currentNode) {
            nextNode = currentNode.next;
            currentNode.next = prevNode;
            currentNode.prev = nextNode;

            prevNode = currentNode;
            currentNode = nextNode;
        }

        // Swap head and tail
        this.tail = this.head;
        this.head = prevNode;
    }
}

// Test the implementation
const test = new DoubleLinkedList(3);
test.append(5);
test.append(9);
test.prepend(13);
test.prepend(20);

console.log('Head:', test.head.value);  // 20
console.log('Tail:', test.tail.value);  // 9
console.log('Size:', test.size);        // 5
console.log('-------------------------');
test.traverseForward();                 // 20 -> 13 -> 3 -> 5 -> 9
console.log('-------------Reverse Traversal------------');
test.traverseReverse();                 // 9 -> 5 -> 3 -> 13 -> 20
console.log('---------Insert At Middle ----------------');
test.insertAtMiddle(100);
test.traverseForward();                 // 20 -> 13 -> 3 -> 100 -> 5 -> 9
console.log('-------deleteAtEnd-----------');
test.deleteAtEnd();
test.traverseForward();                 // 20 -> 13 -> 3 -> 100 -> 5
console.log('-------deleteAtMiddle-----------');
test.deleteAtMiddle();
test.traverseForward();                 // 20 -> 13 -> 100 -> 5
console.log('-------Reverse Double Linked List-----------');
test.reverseList();
test.traverseForward();                 // 5 -> 100 -> 13 -> 20

如果您有任何疑問/疑慮,請隨時與我聯絡。可在 Linkedin 上找到。

以上是使用 Javascript 處理單鍊錶和雙鍊錶的所有操作:- 最後一站解決方案的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn