数据结构（三）——链表

链表数据结构

要存储多个元素，数组（或列表）可能是最常用的数据结构。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。（尽管我们已经学过，JavaScript 有来自 Array 类的方法可以帮我们做这些事，但背后的情况同样如此。）
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

image.png

1.创建链表

//Node类表示我们想要添加到链表中的项。它包含一个 element 属性，该属性表示要加入链表元素的值；以及一个 next 属性，该属性是指向链表中下一个元素的指针
class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}
//比较两个 JavaScript 对象或值是否相等的自定义函数。
function defaultEquals(a, b) {
  return a === b;
}
class LinkedList {
  constructor(equalsFn = defaultEquals) {
    //用来存储链表中的元素数量
    this.count = 0;
    //用head 保存引用
    this.head = undefined; 
    //比较链表中的元素是否相等
    this.equalsFn = equalsFn; 
  }
}

2. 向链表尾部添加元素

向 LinkedList 对象尾部添加一个元素时，可能有两种场景：

• 链表为空，添加的是第一个元素；
• 链表不为空，向其追加元素。

  push(element) {
    //把 element 作为值传入，创建 Node 项
    const node = new Node(element);
    //定义一个指向链表中current 项的变量
    let current; 
    //如果head是undefined或者null,向链表中添加第一个
    if (this.head == null) {
      //让 head 元素指向 node 元素。下一个 node 元素会自动成为 undefined。
      this.head = node;
    } else {
      //要循环访问列表，找到最后一项。
      current = this.head;
      //当 current.next 元素为 undefined 或 null 时,就获得最后一项
      while (current.next != null) {//{5}
        current = current.next;
      }
      // 将其 next 赋为新元素，建立链接
      current.next = node;//{6}
    }
    //链表长度+1
    this.count++;
  }

链表最后一个节点的下一个元素始终是 undefined 或 null。

第一种情况
第二种情况

3. 从链表中移除元素

链表中移除元素也存在两种场景：

• 第一种是移除第一个元素，
• 第二种是移除第一个元素之外的其他元素。

  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      let current = this.head; // current 变量创建一个对链表中第一个元素的引用
      // 移除第一项
      if (index === 0) {
        //如果从链表中移除第一个元素
        this.head = current.next;
      } else {
        let previous;
        for (let i = 0; i < index; i++) {
          // 循环找到对应节点位置
          previous = current; // {6} 前一个元素的引用
          current = current.next; // {7} 后一个元素的引用
        }
        // 将 previous 与 current 的下一项链接起来：跳过 current，从而移除它
        previous.next = current.next;//{8}
      }
      this.count--; // 链表长度-1
      return current.element;
    }
    return undefined; // 不是有效位置 返回undefined
  }

第一种情况，从链表中移除第一个元素
第二种情况

4.循环迭代链表直到目标位置

迭代整个链表直到到达我们的目标索引 index（位置）。

 getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      // 检查越界值
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node; // 返回index后面的链表
    }
    return undefined; // 不是有效位置 返回undefined
  }
  // 重构 remove 方法
  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      let current = this.head; // current 变量创建一个对链表中第一个元素的引用
      // 移除第一项
      if (index === 0) {
        //如果从链表中移除第一个元素
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--; // 链表长度-1
      return current.element;
    }
    return undefined; // 不是有效位置 返回undefined
  }

5.在任意位置插入元素

链表中插入元素也存在两种场景：

• 第一种是插入第一个元素，
• 第二种是插入第一个元素之外的其他元素。

  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      // 检查越界值
      const node = new Node(element);
      if (index === 0) {
        // 在第一个位置添加
        const current = this.head;
        node.next = current; // {2}
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1); // {3}迭代链表，找到目标位置
        const current = previous.next; // {4}
        node.next = current; // {5}
        previous.next = node; // {6}
      }
      this.count++; // 更新链表的长度
      return true;
    }
    return false; // 越界了，就返回 false 值，没有添加元素到链表中
  }

第一种情况，在链表的起点添加一个元素
第二种情况

6. indexOf 方法：返回一个元素的位置

indexOf 方法接收一个元素的值，如果在链表中找到了它，就返回元素的位置，否则返回-1。

 indexOf(element) {
    let current = this.head; // {1}
    for (let i = 0; i < this.count && current != null; i++) {
      // {2}
      if (this.equalsFn(element, current.element)) {
        // 比较如果相等
        return i; // 返回对应位置
      }
      current = current.next; // {5}
    }
    return -1; // {6} 没有找到返回-1
  }

7.从链表中移除元素

remove(element) { 
 const index = this.indexOf(element); 
 return this.removeAt(index); 
}

8. isEmpty、size 和 getHead 方法

size 方法返回了链表的元素个数。
如果列表中没有元素，isEmpty 方法就返回 true，否则返回 false。
getHead获取head

size() { 
 return this.count; 
} 
isEmpty() { 
 return this.size() === 0; 
}
getHead() { 
 return this.head; 
}

9. toString 方法

toString 方法会把 LinkedList 对象转换成一个字符串。

  toString() {
    if (this.head == null) {
      //如果是null返回空 也可以用isEmpty()判断
      return "";
    }
    let objString = `${this.head.element}`; // 获取链表第一个字符串
    let current = this.head.next; //
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString; // 返回链表内容的字符串
  }