数据结构-链表的生成和应用-一一网

前言

看过很多关于链表操作的文章，也很认真的背过，但由于没有应用层面的了解和使用场景的了解，映像并不深刻，基本上过段时间就忘，更不要说深入了解，那面试官拐个弯问你对链表的了解怎么办，fiber节点之间是如何建立联系的？队列可以怎么实现？node可写流的缓存区域可以怎么实现？我想不通过索引，不移动不相干的元素来实现元素增删操作？所以，特意去看下了链表的相关知识和伪代码的编写，希望正在阅读的你也能从我的总结里有所收获

链表

是什么

1.线性链式存储结构的数据（链表）常与线性顺序存储结构的数据（数组）做比较

链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的next指向。链表的特点和数组相反：访问元素慢，新增或删除元素快。
数组：数组顺序是由下标决定的，因此访问数组的元素速度很快；但是，往数组添加或删除元素时，需要把数组中的其他元素向前或向后移动，速度比较慢
链表&数组比较：在元素很多，经常要添加或删除元素，但不经常访问元素的场景下，用数组的性能比较低。这种场景下，可以用链表。

2.链表拥有很多结点，每个结点前半部分是数据域，后半部分是指针域（next），指针域指针指向下一个结点

代码实现

生成链表节点

/**
 * element 存储的数据
 * next 存储的下一个 数据的指针
 */
class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}
复制代码

生成链表

初始化表头数据constructor()

/**
 * 存储数据
 * add 新增
 * remove 移除
 * reverse 反转
 */
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;//链表长度
  }
 }
 module.exports = LinkedList;
复制代码

新增节点add()

思路:

添加的时候要考虑是否是第一次新增，

是：将head 指向新节点， next指向null（最初的head的next）
否：上一个节点的next指向自己

/**
 * @description 链表新增节点
 * index：插入位置
 * element 插入元素
 * 只有一个参数时候 默认是需要新增的元素，把index赋值给elemnt
 */
add(index, element) {
    if (arguments.length === 1) {
      //参数长度为1时 默认为是需要新增的元素，把index赋值给elemnt
      // index处理成this.size
      element = index;
      index = this.size;
    }
    let head = this.head;
    if (this.size === 0) {
      // 如果 是第一次 新建 将head 指向 新节点， next指向null（最初的head的next）
      this.head = new Node(element, head);
    } else {
      //  获取前一个节点this._node()待实现
      let preNode = this._node(index - 1); //索引从0开始 始终比长度小1
      if (!preNode) return;
      //   让当前新节点的next指向上一个节点的next,上一个节点的next指向 自己
      preNode.next = new Node(element, preNode.next);
    }

    this.size++;
  }
复制代码

获取前一个节点_node（）

//依据index通过遍历 获取上一个节点 
_node(index) {
    let current = this.head;
    for (let i = 0; i < index; i++) {
      //遍历直到i=的index
      current = current.next;
    }
    return current;
  }
复制代码

删除节点remove()

思路：找到要删除的节点的上一个节点，让他的next指向下一个节点（就是当前索引指向的节点）的下一个节点

remove(index) {
    let removeNode;
    if (index === 0) {
      removeNode = this.head;
      if (removeNode !== null) {
        this.head = this.head.next;
        this.size--;
      }
    } else {
      let preNode = this._node(index - 1);
      preNode.next = preNode.next.next;
      this.size--;
    }

    return removeNode;
  }
复制代码

链表反转 reverse()

递归实现

   reverse() {
    // 递归 但耗内存
    function r(head) {
      if (head === null || head.next === null) {
        return head;
      }
      let newHead = r(head.next);
      head.next.next = head;
      head.next = null;
      return newHead;
    }
    return r(this.head);
  }
复制代码

while循环实现

 reverse() {
    let head = this.head;
    if (head === null || head.next === null) {
      return head;
    }
    let newHead = null;
    while (head !== null) {
      let temp = head.next;
      head.next = newHead;
      newHead = head;
      head = temp;
    }
    return newHead;
  }
复制代码

小结：非要讨论两种实现方式的优劣递归会稍耗内存些，往往链表都用于底层代码的实现，那么需要更多考虑性能问题，所以while循环更合适些

实例测试

let li = new LinkedList();
li.add(1);
li.add(2);
li.add(3);
li.add(4);
li.add(1, 200);

console.dir(li, { depth: 100 });
li.remove(2)
console.dir(li, { depth: 100 });
console.dir(li.reverse(), { depth: 100 });
复制代码

测试效果

连续add后的打印链表

2.删除节点2后的打印效果，size为4 节点2已经不存在

3.反转链表

场景应用–生成队列

const LinkedList = require("链表的文件位置");

// 用链表 生成队列
class Queue {
  constructor() {
    // 有参数 new LinkedList（）,没参数 用 new LinkedList
    this.ll = new LinkedList();
  }
  poll() {
    //删除头部
    let removeNode = this.ll.remove(0);
    return removeNode && removeNode.element;
  }
  offer(element) {
    //添加 尾部
    this.ll.add(element);
  }
}
module.exports = Queue;
复制代码

题外话：new 构造函数后面有()和没()的区别———-（留个坑，后面写一个new的原理）

有实参有括号就会重载构造函数，用户自定义传入的参数会赋给构造函数做实例自己的初始化默认值