什么是链表？

说实话关于什么是链表，这个东西要描述的清楚，要看写作能力，我就大概的描述一下，请自己百度一下相关的概念进行补充。

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它后面一个节点（即当前节点的后继节点，后面我就用后继来表示这个概念），该对象中还保存着当前节点所保存的数据。指向另一个节点的引用叫做链。

下面给出我在学习链表的时候别人绘制的一个链表图，提供参考

使用JavaScript浅谈链表

由于要标识链表的起始节点有点麻烦，所以我们会给链表给一个起始节点header，叫做头节点，从图中可以看出列表中的每一个节点就是一个对象形式的数据结构，这个对象里面有当前节点对应的元素和指向其他节点的链，所以我们抽象出来节点对应的数据结构：

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

在这里创建了一个节点对应的数据结构对象，也就是每一个对象就是上述代码中的一个对象，里面有节点对应的元素，指向其他节点的引用（链）。

对于链表的操作，我们要有增加，删除基本的操作，还要有输出链表的功能，以此看看我们所创建的链表是不是正确的。

关于增加节点，我们必须要指定在哪个节点之前或者之后增加（这里我们用在节点后面增加节点为例子），那么我们找到这个特殊节点的时候，这个特殊节点的next指向这个新增的节点，新增节点的next指向特殊节点之前next指向的节点（这里可能有点小绕，多读几遍就好了）

关于删除节点，我们需要找到待删除节点前面的那个节点，也就是特殊节点，使特殊节点的next指向待删除接节点的后继节点（也就是待删除节点的后面一个节点）那么我们就完成了节点的删除（请自行脑补画面，????）

现在我们创建一个链表类：

class LinkedList {
    constructor() {
        // 代表链表的头节点
        this.header = new Node('header');
    }
    // find: 辅助函数，遍历链表，查找特殊节点
    find(element) {
        let currNode = this.header;
        while (currNode.element !== element) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // insert：链表插入节点函数
    insert(newElement, hasElement) {
        const newNode = new Node(newElement);
        const currNode = this.find(hasElement);
        // 请思考为什么这两句代码为什么不能切换顺序？
        newNode.next = currNode.next;
        currNode.next = newNode;

    }
    // findPrevious： 辅助函数，寻找待删除节点的前面那个节点
    findPrevious(element) {
        let currNode = this.header;
        while (!(currNode.next === null) && (currNode.next.element !== element)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // remove: 链表删除节点函数
    remove(delElement) {
        const prevNode = this.findPrevious(delElement);
        if (!(prevNode.next === null)) {
            prevNode.next = prevNode.next.next;
        }
    }
    // display: 链表显示函数
    display() {
        let currNode = this.header;
        // 由于header节点是我们方便操作链表的，其保存的数据在这里对链表没有关联，所以不输出该节点
        while (!(currNode.next === null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
}

现在我们来测试一下这个链表，测试结果如下：

使用JavaScript浅谈链表

可以看出这个链表的增加和删除没有问题，还行。

上面只是一个典型的单向链表，下面我们来看看双向链表

从单向链表来看，从头节点遍历到尾节点很简单，但是从尾节点向前遍历就很困难，所以我们该节点对象node添加一个指向该节点前面一个节点的链接，就会很容易了。

现在节点类如下：

// 节点类
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    }
}

现在在插入新节点的时候，我们还需要指定节点的previous对应的节点，代码如下：

// insert：链表插入节点函数
    insert(newElement, hasElement) {
        const newNode = new Node(newElement);
        const currNode = this.find(hasElement);
        newNode.next = currNode.next;
        newNode.previous = currNode;
        currNode.next = newNode;

    }

删除节点的时候，就比较方便了，不需要在查找前面的那个节点，直接找到待删除节点，然后设置该节点前一个节点的next，使其指向待删除节点的next，设置待删除节点的后面节点的previous指向待删除节点前面一个节点就行了。

代码如下：

 // remove: 链表删除节点函数
    remove(delElement) {
        const currNode = this.find(delElement);
        if (!( currNode.next === null)) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
        }
        currNode.next = null;
        currNode.previous = null;
    }

测试如下

使用JavaScript浅谈链表

测试结果正确。

完整代码如下：

// 节点类
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    }
}
// 链表类
class LinkedList {
    constructor() {
        // 代表链表的头节点
        this.header = new Node('header');
    }
    // find: 辅助函数，遍历链表，查找特殊节点
    find(element) {
        let currNode = this.header;
        while (currNode.element !== element) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // insert：链表插入节点函数
    insert(newElement, hasElement) {
        const newNode = new Node(newElement);
        const currNode = this.find(hasElement);
        newNode.next = currNode.next;
        newNode.previous = currNode;
        currNode.next = newNode;

    }
    // // findLast 辅助函数，寻找列表中的最后一个节点
    findLast() {
        let currNode = this.header;
        while (!(currNode.next === null)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // remove: 链表删除节点函数
    remove(delElement) {
        const currNode = this.find(delElement);
        if (!(currNode.next === null)) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
        }
        currNode.next = null;
        currNode.previous = null;
    }
    // display: 链表显示函数
    display() {
        let currNode = this.header;
        // 由于header节点是我们方便操作链表的，其保存的数据在这里对链表没有关联，所以不输出该节点
        while (!(currNode.next === null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
    // disReverse：反向输出列表
    disReverse() {
        let currNode = this.findLast();
        while (!(currNode.previous === null)) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    }
}

const linkedList = new LinkedList();
linkedList.insert('node1', 'header');
linkedList.insert('node2', 'node1');
linkedList.insert('node3', 'node1');
linkedList.insert('node4', 'node3');
// 调用display方法，显示的应该是
// node1
// node3
// node4
// node2
linkedList.display();
console.log('---------')

linkedList.remove('node4');
linkedList.display();
console.log('////////');
linkedList.disReverse();

最后，我们来看看循环列表

从双向列表我们可以很简单的实现从尾向前遍历，但是细心的你应该发现了，我们增加了很多代码，有没有更简单的办法了，当然是有的，使用循环列表可以很好解决这个问题。何谓循环，你可以想象成一个人从圆圈开始走，一直走他是不是可以走完所有的圆形轨迹，就相当于我们遍历了链表中所有的元素。

我们修改一下LinkedList类的构造函数：

constructor() {

// 代表链表的头节点

this.header = new Node('header');

this.header.next = header;

}

就这么简单，就实现了循环列表（自己仔细想一想是不是这样子????️）当然我们还要对相关函数进行小小的修改，就能达到我们想要的结构，完整代码如下：

// 节点类
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}
// 链表类
class LinkedList {
    constructor() {
        // 代表链表的头节点
        this.header = new Node('header');
        this.header.next = this.header;
    }
    // find: 辅助函数，遍历链表，查找特殊节点
    find(element) {
        let currNode = this.header;
        while (currNode.element !== element) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // insert：链表插入节点函数
    insert(newElement, hasElement) {
        const newNode = new Node(newElement);
        const currNode = this.find(hasElement);

        newNode.next = currNode.next;
        currNode.next = newNode;

    }
    // // findPrevious： 辅助函数，寻找待删除节点的前面那个节点
    findPrevious(element) {
        let currNode = this.header;
        while (!(currNode.next === null) && (currNode.next.element !== element)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    // remove: 链表删除节点函数
    remove(delElement) {
        const prevNode = this.findPrevious(delElement);
        const delNode = this.find(delElement);
        if (!(delNode.next === null)) {
            prevNode.next = delNode.next;
            delNode.next = null;
        }
    }
    // display: 链表显示函数
    display() {
        let currNode = this.header;
        // 由于header节点是我们方便操作链表的，其保存的数据在这里对链表没有关联，所以不输出该节点
        while (!(currNode.next === null) && !(currNode.next === this.header)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
}

const linkedList = new LinkedList();
linkedList.insert('node1', 'header');
// linkedList.display();
linkedList.insert('node2', 'node1');
// linkedList.display();
linkedList.insert('node3', 'node1');
// linkedList.display();
linkedList.insert('node4', 'node3');
// 调用display方法，显示的应该是
// node1
// node3
// node4
// node2
linkedList.display();
console.log('---------')
linkedList.remove('node3');
linkedList.remove('node4');
linkedList.display();

你如果愿意的话，可以继续添加其他方法，让你的链表更加的好用。

源代码和案例地址：https://gitee.com/mvc_ydb/data-structure/tree/master/linkedList

双向链表的插入函数有bug，现在已经修改如下：

  // insert：链表插入节点函数
    insert(newElement, hasElement) {
        const newNode = new Node(newElement);
        const currNode = this.find(hasElement);
        newNode.next = currNode.next;
        if (currNode.next&&currNode.next.previous !== null) {
            currNode.next.previous = newNode;
        }
        newNode.previous = currNode;
        currNode.next = newNode;

    }

需要修改后继节点的previous，请参考源码。

使用JavaScript浅谈链表

什么是链表？

相关推荐