JavaScript 中的数据结构和算法（单链表）第 1 部分

什么是链表？

大家好，这是有关 JavaScript 中的数据结构和算法的系列博客的第 5.1 部分，在此博客中，我将介绍链表。

什么是链表？

链表由节点组成，其中每个节点包含一个数据字段和指向列表中下一个节点的引用（链接）。- geeksforgeeks.org

可用操作列表

Push：在链表的末尾插入一个元素。
插入：在链接列表的给定索引处插入元素。
删除：删除链接列表的末尾元素。
RemoveAt：删除链接列表给定索引处的元素。
GetElementAt：获取链接列表给定索引处的元素。
IndexOf：返回链接列表中元素的索引。

Javascript 中链表的实现

让我们定义一个 ES6 类 Node，它有两个属性：data和next。data属性
保存的是我们要插入链表中的数据，next 属性保存的是指向下一个Node的指针。链表就是由多个 Node 组成的链，这些 Node 通过 next 指针相互连接。什么是指针？ 指针指向链表的下一个成员，如上图所示。

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

现在，让我们定义一个具有三个属性的 ES6 类链表：
count用于跟踪链表中元素的数量；head始终指向链表的起始节点，但最初它是未定义的；equalFun用于比较链表中的两个节点。在单个链表中，我们只有对头节点的引用。因此，要遍历链表，我们总是从头节点开始遍历。因此，后续方法我们将始终从头节点开始。

class LinkedList {
    constructor(func) {
        this.count = 0;
        this.head = undefined;
        this.equalFunc = func || defaultEq;
    }
}

推

在链表末尾添加元素时，可以有两种情况：

当头部未定义时，即链表为空。
当链表不为空时，我们需要将其附加到末尾。

首先，我们创建一个 Node，将元素作为其值传递，如果 head 未定义则将 head 分配给节点（{1}），否则，我们将定义一个等于 head 的current变量并循环，直到到达链表的末尾，即当节点的 next 为空（{2}）时，将结束 Node 的 next 分配给节点（{3}），添加元素后将始终增加 count 变量（{4}）。


push(element) {
        const node = new Node(element);
        let current = this.head;
        if (this.head == undefined) {
            this.head = node;  //1
        }else{
            while (current.next != null) { //2
                current = current.next
            }
            current.next = node; //3
        }
        this.count++ //4;
        return;
    }

获取元素

要通过索引获取元素，我们首先定义一个变量node，引用head ({1})，我们通过检查索引是否大于零且小于 count 来验证索引的越界错误。({2})；如果不是，则返回undefined ({5})，现在，从 0 开始遍历链表到索引({3})，返回节点 ({4})。此方法在链表的任何位置插入和删除元素时非常有用。


  getElementAt(index) {
        let node = this.head; // 1
        if (index >= 0 && index < this.count) { //2
            for (let i = 0; i < index; i++) { //3
                node = node.next;
            }
            return node; //4
        }
        return undefined; //5
    }

插入

在给定的位置插入一个元素；索引必须大于零并且小于等于计数，有两种情况，
我们首先定义一个引用头部的变量节点。

索引等于零 ({1})
- 检查头部是否未定义
  - 如果未定义则 head 等于节点
  - 否则，将头节点更改为新节点，并将节点的下一个更改为前一个头节点。

索引大于零 （{2}）
- 在列表中间或末尾添加一个元素。首先，需要循环遍历列表，直到到达所需位置。在本例中，我们将循环到索引 -1，也就是我们想要插入新节点之前的一个位置
- 当我们退出循环时，前一个变量将引用我们想要插入新元素的索引之前的元素，以及当前变量。
- 因此，我们首先将节点的下一个链接到当前节点，然后更改上一个节点和当前节点之间的链接。我们需要上一个节点的下一个节点。

insert(element, postion) {
        if (postion >= 0 && postion <= this.count) {
            const node = new Node(element);
            let current = this.head;
            if (postion == 0) { //1
                if (this.head == undefined) {
                    this.head = node;
                }
                this.head = node;
                node.next = current;
            } else {  
                let previous = this.getElementAt(postion - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
            }
         this.count++;
        }
    }

你可以在这里获得完整的源代码

结论：

方法	复杂
插入任意位置	在）
插入头部	O(1)
获取元素	在）

因此，请继续关注下一篇博客，我将在其中介绍链表的其余方法。

文章来源：https://dev.to/swarup260/data-structs-algorithms-in-javascript-single-linked-list-part-1-3ghg

JavaScript 中的数据结构和算法（单链表）第 1 部分什么是链表？

JavaScript 中的数据结构和算法（单链表）第 1 部分

什么是链表？

什么是链表？

可用操作列表

Javascript 中链表的实现

推

获取元素

插入

结论 ：

结论：