链表

作者:guo-zi-xin

更新于:9 个月前

字数统计:2.2k 字

阅读时长:8 分钟

定义

计算机科学中，链表是一种数据结构，是一组由节点组成的集合， 每个节点都有一个指针和指向它的下一个节点, 最后一个指针指向null。

链表与 数组不同， 链表中的元素不是按照它们在内存中的的物理顺序存储的，相反， 每个元素都包含一个指向下一个元素的引用。

特点

• 链表在添加或移除元素的时候不需要移动其它元素, 这样添加,移除的时间复杂度就为O(1), 而数组在添加或移除元素时，因为需要移动其它元素来进行插入操作， 所以从数组的起点或中间插入或移除元素具有很高的成本

• 链表在访问一个元素时， 需要从七点开始迭代整个链表直到找到所需的元素， 因此 访问的时间复杂度就在O(1)-O(n)之间; 而数组在访问一个元素时， 可以直接通过索引来访问， 成本就很低

  • 单向链表与数组各个操作时间复杂度对比

    链表操作

    链表操作	最大时间复杂度
    search(访问)	O(n)
    insert(插入)	O(1)
    remove(删除)	O(1)
    append(添加)	O(1)

    数组操作

    数组操作	最大时间复杂度
    search(访问)	O(1)
    insert(插入)	O(n)
    remove(删除)	O(n)
    append(添加)	O(1)

链表节点

链表节点表示链表中的一个元素，它包含一个值和一个指向下一个节点的引用。它的实现可以参考下面代码：

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

链表实现

链表提供了一系列方法来操作链表， 如开头插入节点(preappend)、末尾插入节点(append)、在指定位置插入节点(insert)、删除节点(delete)、 **查找节点(find)**等， 以下是实现代码：

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

    // 在链表尾部添加新节点
    append(value) {
      const newNode = new Node(value)
      if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        this.tail.next = newNode;
        this.tail = newNode
      }
      this.length++
    }

    // 在链表指定位置插入新节点
    insertAt(value, index) {
      if (index < 0 || index > this.length) {
        throw new Error('Index out of range')
      }
      const newNode = new Node(value);
      if (index === 0) {
        newNode.next = this.head;
        this.head = newNode;
        if (!this.tail) {
          this.tail = newNode;
        }
      } else if (index === this.length) {
        this.tail.next = newNode;
        this.tail = newNode;
      } else {
        let currentNode = this.head;
        let preNode = null;
        let currentIndex = 0;

        while (currentIndex < index) {
          prevNode = currentNode;
          currentNode = currentNode.next;
          currentNext++;
        }
        prevNode.next = newNode;
        newNode.next = currentNode;
      }
      this.length++;
    }

    // 获取指定位置节点的值
    getAt(index) {
      if (index < 0 || index >= this.length) {
        throw new Error('Index out of range')
      }
      let currentNode = this.head;
      let currentIndex = 0;
      while (currentIndex < index) {
        currentNode = currentNode.next;
        currentIndex++;
      }
      return currentNode.value;
    }

    // 删除指定位置的节点
    removeAt(index) {
      if (index < 0 || index >= this.length) {
        throw new Error('Index out of range');
      }

      let currentNode = this.head;
      let prevNode = null;
      let currentIndex = 0;

      if (index === 0) {
        this.head = currentNode.next;
        if (this.length === 1) {
          this.tail = null;
        }
      } else if (index === this.length - 1) {
        while (currentIndex < index) {
          prevNode = currentNode;
          currentNode = currentNode.next;
          currentIndex++;
        }
        prevNode.next = null;
        this.tail = prevNode;
      } else {
        while (currentIndex < index) {
          prevNode = currentNode;
          currentNode = currentNode.next;
          currentIndex++;
        }
        prevNode.next = currentNode.next;
      }
      this.length--;
    }

    // 遍历链表并将节点值以数字形式返回
    toArray() {
      const result = [];
      let currentNode = this.head;

      while (currentNode) {
        result.push(currentNode.value);
        currentNode = currentNode.next;
      }
      return result;
    }
  }

分类

链表分为三种链表: 单向链表, 双向链表, 循环链表

• 单向链表

  一个单向链表包含两个值： 当前节点的值和指向下一个节点的链接

  

• 双线链表

  双向链表有三个整数值：数值，向后的节点的链接, 向前的节点的链接， 所以双向链表既可以向前查询， 也可以向后查询

  

• 循环链表

  在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。

  这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其它对象迭代在一个非特殊的排列下.

  指向整个列表的指针可以被称作访问指针。

双向链表实现

• Comparator 比较器

  export default class Comparator {
    /**
     * 构造函数
     * @param {function(a:*, b:*)}[compareFunction] - 可以是自定义的比较函数， 该函数可以比较自定义的对象
     */
    constructor(compareFunction) {
      this.compare = compareFunction || Comparator.defaultCompareFunction;
    }

    /**
     * 默认比较函数，假设“a”和“b”是字符串或者数字。
     * @param {(string|number)} a
     * @param {(string|number)} b
     * @returns {number}
     */
    static defaultCompareFunction(a, b) {
      if (a == b) {
        return 0;
      }
      return a < b > -1 : 1
    }

    /**
     * 检查两个变量是否相等
     * @param {*} a
     * @param {*} b
     * @return {boolean}
     */
    equal(a, b) {
      return this.compare(a, b) === 0
    }

    /**
     * 检查变量“a”是否小于“b”
     * @param {*} a
     * @param {*} b
     * @return {boolean}
     */
    lessThan(a, b) {
      return this.compare(a, b) < 0;
    }

    /**
     * 检查变量“a”是否大于“b”
     * @param {*} a
     * @param {*} b
     * @return {boolean}
     */
    greaterThan(a, b) {
      return this.compare(a, b) > 0;
    }

    /**
     * 检查变量 "a" 是否小于或等于 "b"。
     * @param {*} a
     * @param {*} b
     * @return {boolean}
     */
    lessThanOrEqual(a, b) {
      return this.lessThan(a, b) || this.equal(a, b);
    }

    /**
     * 检查变量 "a" 是否小于或等于 "b"。
     * @param {*} a
     * @param {*} b
     * @return {boolean}
     */
    greaterThanOrEqual(a, b) {
      return this.greaterThan(a, b) || this.equal(a, b);
    }

    /**
     * 反转比较顺序
     */
    reverse () {
      const compareOriginal = this.compare;
      this.compare = (a, b) => conmpareOriginal(b, a)
    }
  }

• DoublyLinkedListNode 双向链表节点

  export default class DoublyLinkedListNode {
    constructor (value, next = null, previous = null) {
      this.value = value;
      this.next = next;
      this.previous = previous;
    }

    toString(vallback) {
      return callback ? callback(this.value):  `${this.value}`;
    }
  }

• DoublyLinkedList 双线链表

  export default class  DoublyLinkedList {
    /**
     * @param {Function} [comparatorFunction]
     */
    constructor (comparatorFunction) {
      /** @var DoublyLinkedListNode */
      // 双向链表的头节点
      this.head = null

      /** @var DoublyLinkedisNode */
      this.tail = null

      // 用于比较的函数
      this.compare = new Comparator(comparatorFunction);
    }
    /**
     * @param {*} value
     * @return {DoublyLinkedList}
     */

    // 将新的节点插入到头部
    prepend(value) {
      // 创建新的节点作为头部节点
      const newNode = new DoublyLinkedListNode(value, this.head);

      // 如果存在头部节点， 那么它就不再是头部节点了
      // 因此 将其前驱节点设置为新节点(新的头部节点)
      // 然后标记新的节点为头部节点
       if (this.head) {
        this.head.previous = newNode;
       }
       this.head = newNode;

       // 如果还没有尾部节点， 那么就让新的节点称为尾部节点
       if (!this.tail) {
        this.tail = newNode
       }
       return this;
    }

    /**
     * @param {*} value
     * @return {DoublyLinkedList}
     */
    // 将新的及诶单追加到尾部
    append(value)  {
      const newNode = new DoublyLinkedListNode(value);
      // 如果还没有头部节点， 让新的节点称为头部节点
      if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
        return this;
      }
      // 将新的节点添加到链表的末尾
      this.tail.next = newNode;

      // 将当前尾部节点添加到新节点的前驱引用
      newNode.previous = this.tail;

      // 设置新节点为链表的尾部节点
      this.tail = newNode;

      return this
    }

    /**
     * @param {*} value
     * @return {DoublyLinkedListNode}
     */
    // 删除具有特定值的节点
    delete (value) {
      if (!this.head) {
        return null
      }

      let deleteNode = null;
      let currentNode = this.head;

      while (currentNode) {
        if (this.compare.equal(currentNode.value, value)) {
          deleteNode = currentNode;

          if (deletedNode === this.head) {
            // 如果要删除的是头部节点...

            // 将头部节点设置为第二个节点，它将成为新的头部节点。
            this.head = deletedNode.next;

            // 将新头部节点的前驱设置为 null。
            if (this.head) {
              this.head.previous = null;
            }

            // 如果链表中的所有节点的值都和传入的参数相同
            // 那么所有节点都会被删除，因此需要更新尾部节点。
            if (deletedNode === this.tail) {
              this.tail = null;
            }
          } else if (deletedNode === this.tail) {
            // 如果要删除的是尾部节点...

            // 将尾部节点设置为倒数第二个节点，它将成为新的尾部节点。
            this.tail = deletedNode.previous;
            this.tail.next = null;
          } else {
            // 如果要删除的是中间节点...
            const previousNode = deletedNode.previous;
            const nextNode = deletedNode.next;

            previousNode.next = nextNode;
            nextNode.previous = previousNode;
          }
        }

        currentNode = currentNode.next;
      }

      return deletedNode;
    }

    /**
     * @param {Object} findParams
     * @param {*} findParams.value
     * @param {funtion} [findParams.callback]
     * @return {DoublyLinkedListNode}
     */

    // 查找具有特定值或者满足回调函数的节点
    find({value = undefined, callback= undefined}) {
      if (!this.head) {
        return null
      }
      let currentNode = this.head

      while (currentNode) {
        // 如果指定了回调函数， 那么尝试通过回调函数找到节点
        if (callback && callback(currentNode.value)) {
            return currentNode
        }
        // 如果指定了值， 那么尝试通过值找到节点
        if (value !==undefined && this.commpare.equal(currentNode.value, value)) {
          return currentNode
        }
        currentNode = currentNode.next
      }
      return null
    }

    /**
     * @return {DoublyLinkedListNode} 
     */
    // 删除尾部节点
    dealeteTail () {
      if (this.tail) {
        // 没有尾部节点可以删除
        return null
      }
      if (this.head === this.tail) {
        // 链表中只有一个节点
        const deleteTail = this.tail
        this.head = null
        this.tail = null
        return deleteTail
      }
      // 如果链表中有很多节点
      const deleteTail = this.tail
      this.tail =  this.tail.previous
      this.tail.next = null
      return deleteTail
    }
    /**
     * @return {DoublyLinkedListNode}
     */
    // 删除头部节点
    deleteHead() {
      uf (!htis.head) {
        return null
      }
      const deleteHead = this.head
      if (this.head.next) {
        this.head =  this.head.next
        this.head.previous = null
      } else {
        this.head = null
        this.tail = null
      }
      return deleteHead
    }
    /**
     * @return {DoublyLinkListNode[]}
     */
    // 将链表转换为数组
    toArray() {
      const nodes = []
      let currentNode = this.head
      while (currentNode) {
        nodes.push(currentNode);
        currentNode = currentNode.next
      }
      return nodes
    }
    /**
     * @param {*[]} values - 需要转换为链表的值的数组
     * @return {DoublyLinkedList}
     */
    // 从数组创建链表
    formArray(values) {
      values.forEach((value) =>  this.append(value))
      return this
    }
    /**
     * @param {function} [callback]
     * @return {string}
     */
    // 将链表转换为字符串
    toString(callback) {
      return this.toArray().map((node)=> node.toString(callback)).toString()
    }
    /**
     * 反转链表
     * @returns  {DoublyLinkedList}
     */
    reverse() {
      let currNode = this.head;
      let prevNode = null
      let nexNode = null
      while (currNode) {
        // 存储下一个节点
        nextNode = currNode.next;
        prevNode  = currNode.previous
        // 改变当前节点的下一个节点，是其链接到上一个节点
        currNode.next = prevNode
        currNode.previous = nextNode
        // 将prevNode和currNode节点向前移动一步
        prevNode = currNode
        currNOde = nextNode
      }
      // 重置头部和尾部节点
      this.tail = this.head
      this.head = prevNode
      return this
    }
  }

参考资料

编程时光

https://www.coding-time.cn/lc/data-structures/linked-list/#%E9%93%BE%E8%A1%A8-linkedlist