Approche des listes chaînées simples et doubles à l'aide de Javascript avec toutes les opérations : - Solution de dernier arrêt

Liste chaînée

**1. Liste chaînée unique

1. Liste doublement liée**

Opérations

**_1. préfixer /append

1. Insérer au milieu
2. Supprimer des extrémités
3. Suppression au milieu
4. avoir tête/queue
5. obtenir en général
6. Liste chaînée inversée
7. Traversée à sens unique (liste à lien unique)
8. Traversée bidirectionnelle (double liste chaînée)_**

Liste chaînée unique avec toutes les opérations ci-dessus

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 }
*/

Liste double chaînée avec toutes les opérations ci-dessus

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

N'hésitez pas à me contacter si vous avez des questions/préoccupations. Disponible sur Linkedin.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!