什么是链表

链表是最流行、最高效的数据结构之一。基本上，链表是“节点”的集合，每个节点包含数据，next_和_previous，基本上next指的是下一个节点，previous指的是上一个节点。

可以说，数组和链表是相似的。但在数组中，元素存储在特定位置或索引中。

在链接列表中，所有内容都作为单独的对象运行。每个元素（节点）包含一些东西，数据，链接到下一个节点，链接到上一个节点。

链表的类型：

单链表：

每个节点包含数据和指向下一个节点的指针，是单向的。

图片描述

分析上图，它是从Head开始的，所以Head是入口点。如果链表为空，则头将为空。所以Head引用第一个节点，Last节点指向 null。

const linkedList = {
    head: {
        value: 5
        next: {
            value: 7                                             
            next: {
                value: 2
                next: {
                    value: 15
                    next: null  
                    }
                }
            }
        }
    }
};

基本示例，

// class of node
class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }

}



/* LindedList class. remember, if the head node is not passed then head will be null */
class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

/* lets create some nodes */

let node1 = new ListNode(5) // data will be 5
let node2 = new ListNode(7) // data will be 7
let node3 = new ListNode(2) //  data will be 2
let node4 = new ListNode(15) // data will be 15

node1.next = node2 // points to the node2
node2.next = node3 // points to the node2
node3.next = node4

let list = new LinkedList(node1) // Linked List completed

单链表的优点和用途

– 动态数据结构： 内存动态分配给链表。我们可以轻松地添加或删除元素。我们不需要考虑初始大小。
– 实现： 其他数据结构可以在这里轻松实现，例如队列和堆栈。
– 多功能性： Lined list可用于实现多种数据结构，例如堆栈、队列、图、truees和has表。

单链表的缺点

– 内存使用： 我们需要存储下一个数据的地址，因此需要更多的内存。
– 访问元素： 不可能直接访问任何元素。如果我们需要找到第n个值，那么我们需要遍历直到找到第n个元素。
– 反向遍历： 单链表不可能。因为我们没有前一个指针的内存地址。
– 更复杂的实现： 与Array类似，它的实现非常复杂。我们需要了解动态内存位置和指针操作。
– 缺乏缓存局部性： 它可能无法利用现代处理器中的缓存机制。它的性能较慢。

双向链表：

每个节点包含两个指针，一个指向下一个节点，一个指向前一个节点。

图片描述

在上图中，我们了解到，

prev：指前一个节点
数据：数据项
next：下一个节点的地址

下图显示了双向链表的表示，这里每个节点都包含next _和 _prev来指向下一个节点和上一个节点

图片描述

基本示例

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

}



class DoublyLinkedList {
    constructor(value) {
        this.head = {
            value: value,
            next: null,
            previous: null
        };
        this.length = 0;
        this.tail = this.head;
    }

    // Insert node at end of the list
    add(newNode) {
        this.tail.next = newNode;
        newNode.previous = this.tail;
        this.tail = newNode;
        this.length++;
    }

    printList() {
        let current = this.head;
        let result = [];
        while (current !== null) {
            result.push(current.value);
            current = current.next;
        }
        console.log(result.join(' '));
        return this;
    }
}

let numList = new DoublyLinkedList();
numList.add(new ListNode (12));
numList.add(new ListNode (13));
numList.add(new ListNode (14));
numList.add(new ListNode (15));
numList.add(new ListNode (16));
numList.add(new ListNode (17));
numList.printList();
console.log(numList)
console.log(numList.head)

双向链表的优点：

– 反转： 反转双向链表非常容易。
-遍历： 这个双向链表的遍历是双向的，这在单链表中是不可能的。
-删除： 与单链表相比，删除节点很容易。

双向链表的缺点：

与数组和单链表相比，它使用额外的内存。
遍历双向链表可能比遍历单链表慢
实现和维护双向链表可能比单链表更复杂。

双向链表的用途：

– 导航系统： 用于需要前后导航的导航系统。
– 撤消和重做： 各种应用程序也使用它来实现撤消和重做功能。
– MRU/LRU： 双向链表也用于构造MRU/LRU（最近/最少使用）缓存。
– 线程调度程序： 同样在许多操作系统中，线程调度程序（选择何时需要运行哪个进程的东西）维护当时运行的所有进程的双向链接列表。
– 浏览器： 下一页和上一页。
– 图像查看器： 下一张和上一张图像