学习参考：
https://segmentfault.com/a/1190000017569816
https://www.jianshu.com/p/f254ec665e57
https://www.cnblogs.com/cc-freiheit/p/10591992.html

一、链表和数组的区别

大家都用过js中的数组，数组其实是一种线性表的顺序存储结构，它的特点是用一组地址连续的存储单元依次存储数据元素。而它的缺点也正是其特点而造成，比如对数组做删除或者插入的时候，可能需要移动大量的元素。
这里大致模拟一下数组的插入操作：

function insert(arr, index, data) {
    for (let i = arr.length; i >index; i--) {
        arr[i] = arr[i - 1];
    }
    arr[index] = data;
}

从上面的代码可以看出数组的插入以及删除都有可能会是一个O(n)的操作。从而就引出了链表这种数据结构，链表不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点，当然它也失去了数组在一块连续空间内随机存取的优点。

二、链表的定义

链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用叫做链。相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点(表头)开始迭代列表直到找到所需的元素。

其中，data中保存着数据，next保存着下一个链表的引用。上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。上图，值得注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。
由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为头节点，表示链表的头部。进过改造，链表就成了如下的样子：

三、链表的设计

我们设计链表包含两个类，一个是 Node 类用来表示节点，另一个事 LinkedList 类提供插入节点、删除节点等一些操作。

1.Node类

Node类包含两个属性： element 用来保存节点上的数据，next 用来保存指向下一个节点的链接，具体实现如下：

//节点
function Node(element) {
    this.element = element;   //当前节点的元素
    this.next = null;         //下一个节点链接
}

2.LinkedList类

LinkedList类提供了对链表进行操作的方法，包括插入删除节点，查找给定的值等。值得注意的是，它只有一个
属性，那就是使用一个 Node 对象来保存该链表的头节点。它的构造函数的实现如下：

//链表类
function LList () {
    this.head = new Node( 'head' );     //头节点
    this.find = find;                   //查找节点
    this.insert = insert;               //插入节点
    this.remove = remove;               //删除节点
    this.findPrev = findPrev;           //查找前一个节点
    this.display = display;             //显示链表
}

head节点的next属性初始化为 null ，当有新元素插入时，next会指向新的元素。链表可分为单向链表、双向链表、环链表等，其定义如下：

3.单向链表

单向链表的特点：

用一组任意的内存空间去存储数据元素（这里的内存空间可以是连续的，也可以是不连续的）
每个节点(node)都由数据本身和一个指向后续节点的指针组成
整个链表的存取必须从头指针开始，头指针指向第一个节点
最后一个节点的指针指向空（NULL）

链表中的几个主要操作：

创建节点
插入节点
搜索/遍历节点
删除节点
合并

初始化节点

指针指向空
存储数据

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

初始化单向链表每个链表都有一个头指针，指向第一个节点，没节点则指向NULL

class List {
    constructor() {
    this.head = null;
    }
}

创建节点

static createNode(key) {
    return new createNode(key);
}

这里说明一下，这一块我是向外暴露了一个静态方法来创建节点，而并非直接把它封装进插入操作里去，因为我感觉这样的逻辑会更加正确一些。从创建一个链表 -> 创建一个节点 -> 将节点插入进链表中。可能你会遇到一些文章介绍的方式是直接将一个数据作为参数去调用insert操作，在insert内部做了一个创建节点。

3.1插入节点（插入到头节点之后）

插入操作只需要去调整节点的指针即可,两种情况：

head没有指向任何节点，说明当前插入的节点是第一个
- head指向新节点
- 新节点的指针指向NULL
head有指向的节点
- head指向新的节点
- 新节点的指针指向原本head所指向的节点

function insert(node) {
    // 如果head有指向的节点
    if(this.head){
        node.next = this.head;
    }else {
        node.next = null;
    }
    this.head = node;
}

3.2插入节点（在尾节点处添加节点）

根据传入的元素定义一个节点，该元素作为这个节点的值
定义一个变量表示当前的节点
判断是否含有头节点,如果没有头节点，说明链表中还没有值，将传进来的这个值作为头节点；否则，对链表进行遍历，找到最后一个节点，将其next属性赋值为新增的节点
链表的长度+1

//在尾节点处添加节点
function append(element){
    let node = new node(element);
    let current;
    if(head == null){
        current = node
    }else{
        while(current.next){
            current = current.next;
        }
        current.next = node
    }
    length++;
}

3.3插入节点（指定位置）

将这个位置的前一个节点的next属性赋值为这个节点，并将它原先的下一个节点保存下来，赋值给现在这个节点的next属性

检查postion是否越界,若没有越界，则创建一个节点
定义一个变量表示当前的节点，初始化为头节点，表示从头节点开始遍历；一个变量表示当前节点的前一个节点，作用是插入节点时方便找到前一个节点
判断是否在头节点前添加，如果是就将头节点赋给node的next属性，并且头节点改为这个节点；否则，遍历出这个位置的节点，将该节点插入到这个位置的节点前面
链表的长度+1

function insert(position,element){
    let node = new Node(element);
    let current = head;
    let previous;//当前节点的前一个节点，在position处添加节点，就是在previos和current之间添加
    if(position = 0){
        node.next = head;
        head = node;
    }else{
        for(let i = 0;i< position;i++){
            pervious = current;
            current = current.next;
        }

        pervious.next = node;
        node.next = current;
    }
    length++;
    return true;
}



//插入节点

function insert ( newElement , item ) {
    var newNode = new Node( newElement );
    var currNode = this.find( item );
    newNode.next = currNode.next;
    currNode.next = newNode;
}

3.4删除节点

这里分三种情况：

所要删除的节点刚好是第一个，也就是head指向的节点
- 将head指向所要删除节点的下一个节点(node.next)
要删除的节点为最后一个节点
- 寻找到所要删除节点的上一个节点(prevNode)
- 将prevNode中的指针指向NULL
在列表中间删除某个节点
- 寻找到所要删除节点的上一个节点(prevNode)
- 将prevNode中的指针指向当前要删除的这个节点的下一个节点

function  delete(node) {
    // 第一种情况
    if(node === this.head){
        this.head = node.next;
        return;
    }
    // 查找所要删除节点的上一个节点
    let prevNode = this.head;
    while (prevNode.next !== node) {
        prevNode = prevNode.next;
    }
    // 第二种情况
    if(node.next === null) {
        prevNode.next = null;
    }
    // 第三种情况
    if(node.next) {
        prevNode.next = node.next;
    }
}

3.5删除指定节点

function removed(element){
    let node = new Node(element);
    let pervious;
    let nextNode;
    let current = head;
    if(head != null){

        while (current != node){
            pervious = current;
            current = current.next;
            nextNode = current.next;
        }  

        pervious.next = nextNode;
        length--;
        return true;
    }else{
        return false;
    }    
}

3.6删除指定位置节点

function removedAt(position){
    let current = head;
    let pervious;
    let nextNode;
    let i = 0;

    while(i < position){
        pervious = current;
        current = current.next;
        nextNode = current.next;
    }

    pervious.next = nextNode;
    length--;
    return true;
}

3.7搜索节点

从head开始查找
找到节点中的key等于想要查找的key的时候，返回该节点

function find(key) {
    let node = this.head;
    while(node !== null && node.key !== key){
        node = node.next;
    }
    return node;
}

3.8查询某个位置是哪个节点

function searchElement(element){
    //输入元素，找到该元素后返回该元素的位置
    if(head != null){
        let node = new Node(element);
        let current;
        let index = 0;
        if(head == node){
        return 0;
        }else{
        current = head;
        while(current != node){
            current = current.next;
            index++;
        }
        return index;
        }
    }else{
        return -1;
    }
}

3.9查询某个节点是在哪个位置

function searchPosition(position){
    let i = 0;
    let current = head;
    while(i< position){
    current = current.next;
    i++;
    }
    return current;
}

3.10显示链表

function display () {
    var currNode = this.head;
    while ( !(currNode.next == null) ){
        console.log( currNode.next.element );
        currNode = currNode.next;
    }
}

3.11单向链表整体的代码

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

// 链表
class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0; // length 同数组 length 与下标关系
    }

    // 追加元素
    append(element) {
        let node = new Node(element);
        let current = null;  // 指针？

        if (this.head === null) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }

    // 任意位置插入元素
    insert (position, element) {
        if (position >= 0 && position <= this.length) {
            let node = new Node(element);
            let current = this.head;
            let previous = null;
            let index = 0;
            if (position === 0) {
                this.head = node;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            this.length++;
            return true
        }
        return false
    }

    // 移除指定位置元素
    removeAt(position) {
        if (position > -1 && position < length) {
            let current = this.head;
            let previous = null;
            let index = 0;
            if (position === 0) {
                this.head = current.next;
            } else {
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.length--;
            return current.element;
        }
        return null
    }

    // 寻找元素下标
    findIndex(element) {
        let current = this.head;
        let index = -1;
        while (current) {
            if (element === current.element) {
                return index + 1;
            }
            index++;
            current = current.next;
        }

        return -1;
    }

    // 删除指定文档
    remove(element) {
        let index = this.findIndex(element);
        return removeAt(index);
    }

    isEmpty() {
        return !this.length;
    }

    size() {
        return this.length;
    }

    // 输出字符串
    toString() {
        let current = this.head;
        let string = '';
        while (current) {
            string += ` ${current.element}`;
            current = current.next;
        }
        return string;
    }
}

var ll = new LinkedList();
console.log(ll);
ll.append(2);
ll.append(6);
ll.append(24);
ll.append(152);

ll.insert(3, 18);
console.log(ll);
console.log(ll.findIndex(24));

test2.js

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

// 单链表
class SingleList {
    constructor() {
        this.size = 0;  // 单链表的长度
        this.head = new Node('head');  // 表头节点
        this.currNode = '';  // 当前节点的指向
    }

    // 判断单链表是否为空
    isEmpty() {
        return this.size === 0;
    }

    // 获取单链表的最后一个节点
    findLast() {
        let currNode = this.head;

        while (currNode.next) {
            currNode = currNode.next;
        }

        return currNode;
    }

    // 单链表的遍历显示
    display() {
        let result = '';
        let currNode = this.head;

        while (currNode) {
            result += currNode.data;
            currNode = currNode.next;
            if(currNode) {
                result += '->';
            }
        }
        console.log(result);
    }

    // 从当前位置向前移动 n 个节点。
    advance(n, currNode = this.head) {
        this.currNode = currNode;

        while ((n--) && this.currNode.next) {
            this.currNode = this.currNode.next;
        }

        return this.currNode;
    }

    // 在单链表中寻找item元素
    find(item) {
        let currNode = this.head;

        while (currNode && (currNode.data !== item)) {
            currNode = currNode.next;
        }

        return currNode;
    }

    // 显示当前节点
    show() {
        console.log(this.currNode.data);
    }

    // 获取单链表的长度
    getLength() {
        return this.size;
    }

    // 向单链表中插入元素
    insert(item, element) {
        let itemNode = this.find(item);

        if(!itemNode) {  // 如果item元素不存在
            return;
        }

        let newNode = new Node(element);

        newNode.next = itemNode.next; // 若currNode为最后一个节点，则currNode.next为空
        itemNode.next = newNode;

        this.size++;
    }

    // 在单链表中删除一个节点
    remove(item) {
        if(!this.find(item)) {  // item元素在单链表中不存在时
            return;
        }

        // 企图删除头结点
        if (item === 'head') {
            if (!(this.isEmpty())) {
                return;
            } else {
                this.head.next = null;
                return;
            }
        }

        let currNode = this.head;

        while (currNode.next.data !== item) {
            // 企图删除不存在的节点
            if (!currNode.next) {
                return;
            }
            currNode = currNode.next;
        }


        currNode.next = currNode.next.next;
        this.size--;
    }

    // 在单链表的尾部添加元素
    append(element) {
        let currNode = this.findLast();
        let newNode = new Node(element);

        currNode.next = newNode;
        this.size++;
    }

    // 清空单链表
    clear() {
        this.head.next = null;
        this.size = 0;
    }}

let myList = new SingleList();let arr = [3, 4, 5, 6, 7, 8, 9];

for(let i=0; i<arr.length; i++){
    myList.append(arr[i]);}

myList.display();  // head->3->4->5->6->7->8->9
console.log(myList.find(4));  // Node {data: 4, prev: null, next: Node}
myList.insert(9, 9.1);myList.insert(3, 3.1);myList.display();  // head->3->3.1->4->5->6->7->8->9->9.1
myList.remove(9.1);myList.remove(3);myList.display();  // head->3.1->4->5->6->7->8->9
console.log(myList.findLast());  // Node {data: 9, prev: null, next: null}
console.log(myList.advance(4));  // Node {data: 6, prev: null, next: Node}
console.log(myList.getLength());  // 7
myList.clear();myList.display();  // head

判断单链表中是否有环

var myList = new SingleList()
var arr = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

arr.forEach(item => myList.append(item))

var C = myList.find('C')
var G = myList.findLast()
G.next = C

// 现在链表有环

写个函数来判断链表是否有环，使用了快慢指针，如果快指针走到最后为null，说明链表没有环，如果两个指针在某个时刻相等了，则说明链表有环。

function hasCycle (head) {
    // 至少 2 个节点才能构成一个环
    if (!head || !head.next) {
        return false;
    }
    // 设置快慢指针
    let slow = head;
    let fast = head.next;
    // 如果快指针一直没有追上慢指针
    while (slow !== fast) {
        // 如果没有环，则快指针会抵达终点
        if (!fast || !fast.next) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    // 如果有环，那么快指针会追上慢指针
    return true;
};
hasCycle(myList)// 输出：this list has rings

4.双向链表

如果你把上面介绍的单向列表都看明白了，那么这里介绍的双向列表其实差不多。

从上面的图可以很清楚的看到双向链表和单向链表的区别。双向链表多了一个指向上一个节点的指针。