1.定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

本文章以单链表为例

1.1 节点

节点包含两部分，一部分是存储数据元素的数据域，一部分是存储指向下一个节点的指针域，上图，绿色是数据域，蓝色是指针域，他们一起共同构成一个节点。

let Node = function(data){    this.data = data;    this.next = null;}let node1 = new Node(1);let node2 = new Node(2);let node3 = new Node(3);node1.next = node2;node2.next = node3;console.log(node1.data, 'mmmmm')console.log(node1.next.data)console.log(node1.next.next.data)这就是一个简单的链表。复制代码

1.2 首尾节点

顾名思义，链表的第一个节点和最后一个节点

1.3 有头链表和无头链表

无头链表指第一个节点既有指针域也有数据域

有头链表是指第一个节点只有指针域 没有数据域

上图是无头链边，下图是有头链表

下边介绍，均用无头链表

2. 链表的实现

链表有以下方法

append 添加一个新元素insert 在指定位置插入一个元素remove 删除指定位置的节点remove_head 删除首节点remove_tail 删除尾节点indexOf 返回指定元素的索引、get 返回指定索引位置的元素tail 返回尾节点head 返回头节点length 返回链表的长度isEmpty 判断链表是否为空clear 清空链表prignf 打印整个链表

在代码中，每一步为大家解析

function LinkList(){    var Node = function(data){        this.data = data;        this.next = null;    }    let length = 0;    let head = null; // 头节点    let tail = null // 尾节点    // 添加节点    this.append = function(data) {        // 创建新节点        let new_node = new Node(data);        // 如果没有节点，那么头节点就是新节点，尾节点也是新节点        if(head === null) {            head = new_node;            tail = head;        }else {          //  后边只需要在尾节点后边新增加节点          //  然后把新节点点 变成尾节点            tail.next = new_node;             tail = new_node;        }                length +=1;        return true;    }           // 节点打印    this.printf = function(){        let curr_node = head;      // 节点打印 只需要一直 循环，直到节点的指针域不再链接新的节点        while(curr_node) {            console.log(curr_node.data);            curr_node = curr_node.next;        }    }    // 在 指定的位置插入一个元素   this.insert = function(index,data){        if(index < 0 || index > length) {            return null;        }else if (index ===length){           //  此时 只需要在尾节点直接添加新元素            this.append(data)        }else {            let new_node = new Node(data);            if(index === 0) {               //  如果为0 证明是要插到最前边，那么原来的头节点head 就是新元素的下一个节点，               //  新元素 自然就成为新的头节点                new_node.next = head;                head = new_node;            }else {                let curr_node = head;                let insert_index = 1;                //  循环是为了找到插入的位置 我们只需要找到要插入的位置的前一个节点                // 循环结束后 curr_node  就是new_node 的上一个节点                //  我们可以让index 为1 带入想象                 while(insert_index < index){                    insert_index +=1;                    curr_node = curr_node.next;                }                // 此时 curr_node 是 要插入位置的前一个节点                let next_node = curr_node.next;  //  将原本当前节点的下一个节点先变量存储                 curr_node.next = new_node;                   new_node.next = next_node;            }        }        length +=1;        return true    }    // 删除指定位置的节点    this.remove = function(index){        if(index < 0 || index >=length) {            return null        }else {            let del_node = null;            if(index === 0) {                // head 指向下一个节点，那么当前的head 自然就没啦                del_node = head;                head = head.next;            }else {                let curr_node = head;                let pre_node = null;                let del_index = 0;                // 找到需要删除的位置， del_index 表示被删除节点的所在索引，pre_node 表示被删除                // 节点的上一个节点， curr_node 表示需要被删除的节点                while(del_index < index){                    del_index +=1;                    pre_node = curr_node;                    curr_node = curr_node.next;                }                //  把curr_node 从链表里拿出来                del_node = curr_node;                pre_node.next = curr_node.next;                // 如果删除的是尾节点                if(curr_node.next === null){                    tail = pre_node;                }            }                            length -= 1;               del_node.next = null;               return del_node.data;           }    }    //  获取指定索引位置的节点，需要传入参数 index    this.get = function(index) {        if(index < 0 || index >= length) {            return null        }        let node_index = 0;        let curr_node = head;      // 遍历节点，找到索引位置的节点         while(node_index < index){            node_index +=1;           curr_node = curr_node.next;        }        return curr_node.data;     }    // 返回指定元素所在的位置 如果链表中没这个元素，返回-1 ，如果存在多个，返回第一个    this.indeOf = function(data){        let curr_node = head;        let index = -1;        while(curr_node) {            index +=1;            if(curr_node.data === data) {                return index            }else {                curr_node = curr_node.next;            }        }        return -1;    }    // 删除 尾节点     this.remove_tail = function() {         return this.remove(length -1)     }     // 删除头节点     this.remove_head = function(){         return this.remove(0)     }     // 返回链表的头节点的值     this.head = function(){         return this.get(0)     }     //返回链表尾节点的值     this.tail = function(){         return this.get(length -1)     }     // isEmpty     this.isEmpty = function(){         return length === 0;     }     // 清空链表     this.clear = function(){         head = null;         tail = null;         length = 0     }}let link = new LinkList();link.append(1)link.append(3)link.append(4)console.log(link.get(2),'2')console.log(link.head(),'3')console.log(link.tail(),'4')// link.remove(2)// link.insert(1,8)console.log(link.indeOf(4),'link.indeOf(2)')link.printf();复制代码

实现栈

实现队列

function Queue(){    let linklist = new LinkList();    // 如队列    this.enqueue = function(data){        linklist.append(data);    }    // 出队列    this.dequeue = function(){        linklist.remove_head()    }        //返回队首    this.head = function(){        return linklist.head()    }    // 返回队尾    this.tail = function(){        return linklist.tail()    }    // size     this.size = function(){       return linklist.length()    }    // clear    this.clear = function(){        linklist.clear()    }    //isEmpty    this.isEmpty = function(){        linklist.isEmpty()    }}复制代码

1. 使用迭代实现

function reverse_iter(head){    if(!head) {        return null    }         let pre_node = null;   // 前一个节点    let curr_node = head;  // 当前要翻转的节点   while(curr_node) {     let  next_node = curr_node.next;  //  记录当前节点的下一个节点     curr_node.next = pre_node;  // 当前节点指向前一个节点     pre_node = curr_node;   // 节点指针后移   向后滑动     curr_node = next_node;  //  节点指针后移   向后滑动   }       // 返回pre_node, 当循环结束时，pre_node指向翻转前链表的最后一个节点   //（翻转前的第一个节点head）的链域为NULL      return pre_node}复制代码

2. 递归实现

function reverise_digui(head){    if(!head){        return null;    }    //  终止条件  ： 找到链表的最后一个节点    if(head.next === null ) {        return head    }    // 从下一个节点开始进行翻转  先翻转后边的链表，//从后边的两个节点开始反转，依次向前  let new_head = reverise_digui(head.next)  head.next.next = head  //  将后一个链表节点指向前一个节点  head.next = null;  // 将原链表中的前一个节点指向后一个节点的指向关系断开 return new_head;}

总结： 链表其实并不难，所有的都是从简单到复杂，只要理解了其概念，从简单到复杂，然后再去leetcode 刷一些简单的题，你入大厂的敲门砖就开始了