链表

定义

在计算机科学中，一个链表是数据元素的线性集合，元素的线性顺序不是由它们在内存中的物理位置给出的。相反，每个元素指向下一个元素。它是由一组节点组成的数据结构，这些节点一起，表示序列。

在最简单的形式下，每个节点由数据和序列中下一个节点的引用组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。

更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的。

更快的访问，如随机访问，是不可行的。与链表相比，数据具有更好的缓存位置。

复杂度

增	删	查	改
o(1)	o(1)	o(n)	o(n)

代码实现

LinkedListNode

export default class LinkedListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
  
  toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }
}

LinkedList

import LinkedListNode from 'LinkedListNode';
import Comparator from 'Comparator';

export default class LinkedList {

  constructor(comparatorFunction) {
    this.head = null; // 头指针
    this.tail = null; // 尾指针
    this.compare = new Comparator(comparatorFunction);
  }
  
  /**
   * 链表头部添加节点
   * @param {*} value
   * @return {LinkedList}
   */
  prepend(value) {
    // 创建一个新节点
    const newNode = new LinkedListNode(value, this.head);
    // 头节点指向新建的节点
    this.head = newNode;
    
    // 如果没有尾部，则把新节点设置为尾部，头尾都指向一个节点
    if (!this.tail) {
      this.tail = newNode;
    }
    
    return this;
  }
  
  /**
   * 链表尾部添加节点
   * @param {*} value
   * @return {LinkedList}
   */
  append(value) {
    const newNode = new LinkedListNode(value, null);
    
    // 如果当前没有头节点
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      
      return this;
    }
    
    // 将最后一个节点的指针指向新增的节点
    this.tail.next = newNode;
    this.tail = newNode;
    
    return this;
  }
  
  /**
   * 插入节点
   * @param {*} value
   * @param {number} rawIndex
   * @return {LinkedList}
   */
  insert(value, rawIndex) {
    const index = rawIndex < 0 ? 0 : rawIndex;
    
    // 插入在链头情况
    if (index === 0) {
      this.prepend(value);
    } else {
      let count = 1; // 记录当前节点位置
      let currentNode = this.head; // 记录当前节点
      const newNode = LinkedListNode(value);
      while (currentNode) {
        if (count === rawIndex) {
          break;
        }

        currentNode = currentNode.next;
        count += 1;
      }
		
      // 插入在链中间情况
      if （currentNode) {
       	newNode.next = currentNode.next; // 将新节点的next设置为当前节点的next
      	currentNode.next = newNode; // 当前节点的next设置为当前节点
      } else {
        // 插入在链尾情况
        if (this.tail) {
          this.tail.next = newNode;
          this.tail = newNode;
        } else {
          // 空链表情况
          this.head = newNode;
          this.tail = newNode;
        }
      }
      return this; 
    }
  }
  
  /**
   * 删除所有值为value的节点
   * @param {*} value
   * @return {LinkedListNode}
   */
  delete(value) {
    // 空链表情况
    if (!this.head) {
      return null;
    }
    
    let deleteNode = null; // 即将被删除的节点

    // 删除头节点的情况，可能多个头节点都符合预期
    while (this.head && this.compare.equal(this.head.value, value)) {
      deleteNode = this.head;
      this.head = this.head.next;
    }
    
    let currentNode = this.head;
    
    if (currentNode !== null) {
      while (currentNode.next) {
        if (this.compare.equal(currentNode.next.value, value)) {
          deleteNode = currentNode.next;
          currentNode.next = currentNode.next.next;
        } else {
          currentNode = currentNode.next;
        }
      }
    }
    
    // 尾指针重定向，避免指向了一个已被删除的节点
    if (this.compare.equal(this.tail.value, value)) {
      this.tail = currentNode;
    }
    
    return deletedNode;
  }
  
  /**
   * 查找元素
   * @param {*} value
   * @params {function} callback
   * @return {LinkedListNode}
   */
  find(value, callback) {
    // 空链表情况
    if (!this.head) {
      return null;
    }
    
    let currentNode = this.head;
    
   	while (currentNode) {
      // 支持函数方式查找节点
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }
      
    	if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }
      
      currentNode = currentNode.next;
    }
    
    return null;
  }
  
  /**
   * 删除尾节点
   * @return {LinkedListNode}
   */
  detailTail() {
    const deletedTail = this.tail;
    
    // 单节点情况
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      
      return deletedTail;
    }
    
    let currentNode = this.head;
    while (currentNode.next) {
      if (!currentNode.next.next) {
        currentNode.next = null;
      } else {
        currentNode = currentNode.next;
      }
    }
    
    this.tail = currentNode;
    return deletedTail;
  }
  
  /**
   * 删除头节点
   * @return {LinkedListNode}
   */
  deleteHead() {
    if (!this.head) {
      return null;
    }
    
    const deletedHead = this.head;
    
    // 多节点情况
    if (this.head.next) {
      this.head = this.head.next;
    } else {
      // 单节点情况
     	this.head  = null;
      this.tail = null;
    }
    
    return deletedHead;
  }
  
  /**
   * 链表转为数组
   * @return {LinkedListNode[]}
   */
  toArray() {
    const nodes = [];
    let currentNode = this.head;
    
    while (currentNode) {
      nodes.push(currentNode.value);
      currentNode = currentNode.next;
    }
    
    return nodes;
  }
  
  /**
   * 反转链表
   * @return {LinkedListNode}
   */
  reverse() {
		let currNode = this.head;
    let prevNode = null; // 上一个节点
    let nextNode = null; // 下一个节点
    
    while (currNode) {
      // 存储下一个节点
      nextNode = currNode.next;
      
      // 更改当前节点的下一个节点为上一个节点
      currNode.next = prevNode;
      
      // 上一个节点为当前节点，当前节点为下一个节点
      prevNode = currNode;
      currNode = nextNode;
    }
    
    this.tail = this.head;
    this.head = prevNode;
    
    return this;
  }
  
}