链表

什么是链表？

链表是由一组节点组成的集合。每一个节点都使用一个对象的引用指向它的后续节点。指向另外一个节点的引用叫做链。（这个描述有点不能恍然大悟 😒）

为什么叫链表, 其实就和链子一样后面的一节挂在上一节后面 来看一下链表结构

链表的每个节点由元素(el),指针(next)组成

next 指向下一个元素,下个元素的 next 指向下一个元素... 直到最后 next 为 null

{
    el:"0",
    next: {
        el: "1",
        next:{
            el: "2",
            next: {
                .......
                next: null   // 链尾为null  结束
            }
        }
    }
}

列表分为

• 单项列表
• 双向列表
• 循环列表

单项列表

单项链表特点

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

单项链表实现

链表中的主要操作

• 创建节点
• 插入节点
• 搜索/遍历节点
• 删除节点
• 获取最后节点

初始化节点

• 指针指向空
• 存储数据

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

初始化链表

• head 链表
• length 链表长度

class linkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
}

创建节点

• append 方法

    append(el) {
        const node = new Node(el)
        if(this.head === null) {
            this.head = node
        } else {

            let current = this.head
            while(current.next) {
                current = current.next
            }
            current.next = node;

        }

        this.length++
    }

插入节点

• 头部插入
• 中间插入

头部插入

    appHead(el) {
        const node = new Node(el);
        if(this.head){
            const current = this.head
            node.next = current
        }

         this.head = node;

        this.length++

    }

中间插入

• 指定位置插入节点时候 当前插入位置必须在链表范围内
• 获取当前节点将当前节点 next 设置到新节点 node.next。将 新节点 node 设置当前节点 next

    insert(position, el) {

        // 插入元素必须在链表范围内
        if(position<0 || position > this.length) return false

        // 如果是第一位 走 头部插入
        if(position === 0) this.appHead(el) return;

        let previous = null    // 上一个节点
        let current = this.head  // 当前节点
        let index = 0
        while(index++< position) {

            previous = current
            current = current.next

        }
        node.next = current
        previous.next = node
        this.length++


    }

搜索节点

• 位置搜索
• 节点搜索

位置搜索

返回搜索到的节点

    searchPosition(position) {
         // 节点必须在链表范围内
        if(position < 0 || position > this.length) return null;
        let current = this.head
        while(position--) {
            current = current.next
        }

        return current
    }

节点搜索

通过节点元素进行查询

    find(el) {

        let current = this.head

        // 判断 当前节点 元素 是否登录查询节点元素 current 为空表示 该链表不存在该查询节点
        while (current !== null && current.el != el) {
            current = current.next
        }
        return current

    }

删除节点

• 删除指定节点

• 找到当前节点 移动当前节点 next 到 上一个节点 next

    delete(position) {
        // 节点必须在链表范围内
        if(position < 0 || position > this.length) return false;

        let previous = null
        let current = this.head
        let index = 0
        while(index++ < position) {
            previous = current
            current = current.next
        }

        previous.next = current.next
        this.length--
    }

获取最后节点

    // 获取最后一个节点
    findLast() {
        let current = this.head;

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

        return current;
    }

双向列表

单向列表值节点永远指向一个方向，那双向列表就是节点同时能够指向两侧。也是是一个节点同时存在上指针（指向上一个节点）和下指针（指向下节点）

节点结构

双向链表的节点对于单项列表节点就多了一个上指针（prev）

{   prev: null,  // 上指针
    el: el,
    next: null  // 下指针
}

双向链表实现

class Node {
  constructor(el) {
    this.prev = null;
    this.el = el;
    this.next = null;
  }
}
class DoubleLinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  append(el) {
    let node = new Node(el);
    let previous = null;
    let current = this.head;
    if (this.head) {
      while (current.next) {
        current = current.next;
      }
    }

    current.next = node;
    node.prev = current;
    this.length++;
  }
}

...

循环列表

• 单循环列表

单循环列表

单循环列表 就是将链表的尾部指向链表的头部这样就形成了循环