数据结构与算法基础: 链表

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。
相当于传统数组，链表的好处在于，添加或者移除元素的时候不需要移动其他元素。然而链表需要使用指针，因此实现链表时要额外注意。在数组中，我们阔以访问任何位置的任何元素，而想要访问链表中的一个元素，则需要从头开始迭代链表直到找到所需的元素。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，
但是并不会按线性的顺序储存数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
由于不必须按顺序储存，链表在插入的时候可以达到 o(1)的复杂度，比另一种线性表顺序表快得多，
但是查找一个节点或者访问特定编号的节点则需要 o(n)的时间，而顺序表响应的时间复杂度分别是 o(logn)和 o(1)。
特点：
无需预先分配内存,可以充分利用计算机内存空间，实现灵活的内存动态管理
插入/删除节点不影响其他节点
随机访问速度较慢
增加了结点的指针域，空间开销比较大
单向链表：
是链表中最简单的一种，它包含两个域，一个信息域和一个指针域。
这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
应用：
git commit、es6的Iterator、react的fiber算法。

链表和数组的区别

相比数组，链表(Linked List)是一种稍微复杂一点的数据结构，掌握起来也要比数组稍难一些。链表是通过“指针”将一组零散的内存块串联起来使用。数组的线性序是由数组的下标来决定的，而链表的的顺序是由各个对象中的指针来决定。

在多数编程语言中，数组的长度是固定的，一旦被填满，要再加入数据将会变得非常困难。在数组中，添加和删除元素也比较麻烦，因为需要把数组中的其他元素向前或向后移动。

创建链表

前置基础

表示链表中的第一个以及其他元素，需要一个 助手类 Node

export class Node {
  constructor(element) {
    // this.element = element
    // this.next = undefined
    [this.element, this.next] = [element, null]
  }
}
export function defaultEquals(a, b) {
  return a === b
}

创建链表

class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.head = undefined
    this.count = 0
    this.equalsFn = equalsFn
  }
}

链表尾部添加元素

push(element) {
  const node = new Node(element)
  let current
  if (this.head == null) {
    this.head = node
  } else {
    current = this.head
    while(current.next != null) {
      current = current.next
    }
    current.next = nide
  }
  this.count ++
}

链表中移除元素

removeAt(index) {
  if (index >= 0 && index < this.count ) {
    let current = this.head
    if (index === 0) {
      this.head = current.next
    } else {
      let previous
      for (let i = 0; i < index; i ++) {
        previous = current
        current = current.next
      }
      previous.next = current.next
    }
    this.count --
    return current.element
  }
  return undefined
}

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

getElementAt(index) {
  if (index >= 0 && index < this.count ) {
    let current = this.head
    for(let i = 0; i < index;  i++) {
      current = current.next
    }
    return current
  }
  return undefined
}

重构下remove方法

removeAt(index) {
  if (index >= 0 && index < this.count ) {
    let current = this.head
    if (index === 0) {
      this.head = current.next
    } else {
      let previous = this.getElementAt(index)
      current = previous.next
      previous.next = current.next
    }
    this.count --
    return current.element
  }
  return undefined
}

在任意位置插入元素

insert(element, index) {
  if (index >= 0 && index < this.count) {
    const node = new Node(element) 
    if (index === 0) {
      const current = this.head
      node.next = current
      this.head = node
    } else {
      const previous = this.getElementAt(index - 1)
      const current = previous.next
      node.next = current
      previous.next = node
    }
    this.count ++
    return true
  }
  return false
}

返回一个元素的位置

indexOf(element) {
  const current = this.head
  for (let i = 0; i < this.count && current != null; i++) {
    if (this.equalsFn(element, current.element)) {
      return i
    }
    current = current.next
  }
  return -1
}

从链表中移除元素

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

双向链表

和普通链表的区别在于，在链表中 一个节点只有链向下一个节点的链接，而双向链表中，链接是双向的，一个链向下一个元素，一个链向前一个元素

工具类Node需要拓展DoublyLinkedList

export class DoublyNode extends Node {
  constructor(element, next, prev) { // next好像没啥用
    super(element)
    this.prev = prev
  }
}
export class DoublyLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn)
    this.tail = undefined; // 最后一个元素的引用
  }
}

向链表尾部添加元素

push(element) {
  const node = new DoublyNode(element);
  if (this.head == null) {
    this.head = node;
    this.tail = node; // NEW
  } else {
    // attach to the tail node // NEW
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }
  this.count++;
}

在任意位置插入新元素

insert(element, index) {
  if(index >= 0 && index <= this.count) {
    let node = new DoublyNode(element)
    let current = this.head;
    // 起点位置插入一个新元素
    if (index === 0) {
      // 如果双向链表为空 只需要把head和tail执行这个新节点
      if (this.head == null) {
        this.head = node
        this.tail = node
      } else {
        // current变量将是链表中第一个元素的引用
        node.next = this.head
        current.prev = node
        this.head = node
      }
    } else if (index === this.count) {
      current = this.tail
      current.next = node
      node.prev = current
      this.tail = node
    } else {
      const previous = this.getElementAt(index - 1)
      current = previous.next
      node.next = current
      previous.next = node
      node.prev = previous
      current.prev = node
    }
    this.count ++
    return true
  }
  return false
}

循环链表

循环链表尾部的next引用指向头部节点，定义CircularLinkedList类的insert方法

export class CircularLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn)
  }
  // 链表尾部的next指向head
  insert(element, index) {
    if(index >= 0 && index <= this.count) {
      let node = new DoublyNode(element)
      let current = this.head;
      // 起点位置插入一个新元素
      if (index === 0) {
        // 如果双向链表为空 只需要把head和tail执行这个新节点
        if (this.head == null) {
          this.head = node
          node.next = this.head
        } else {
          // current变量将是链表中第一个元素的引用
          node.next = current
          current = this.getElementAt(this.size())
          this.head = node
          current.next = this.head
        }
      }  else {
        const previous = this.getElementAt(index - 1)
        node.next = previous.next
        previous.next = node
      }
      this.count ++
      return true
    }
    return false
  }
}

从任意位置移除元素

考虑修改循环链表的head元素

removeAt(index) {
  if (index >= 0 && index <= this.count) {
    let current = this.head
    if (index === 0) {
      if (this.size() === 1) {
        this.head = undefined
      } else {
        const removed = this.head
        current = this.getElementAt(this.size())
        this.head = this.head.next
        current.next = this.head
        current = removed
      }
    } else {
      const previous = this.getElementAt(index - 1)
      current = previous.next
      previous.next = current.next
    }
    this.count --
    return current.element
  }
  return undefined
}

有序链表

保持元素有序的链表结构,除了使用排序算法之外，我们还阔以将元素插入到正确的位置来保证链表的有序性

• 声明SortedLinkedList类

export const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
}
export function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}
export class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn)
    this.equalsFn = equalsFn;
    this.compareFn = compareFn
  }
}

有序插入元素

会用下面代码覆盖insert方法

getIndexNextSortedElement(element) {
  let current = this.head
  let i = 0;
  for (; i < this.size() && current; i ++) {
    const comp = this.compareFn(element, current.element)
    if (comp === Compare.LESS_THAN) {
      return i
    }
    current = current.next
  }
  return i
}
insert(element, index = 0) {
  if (this.isEmpty()) {
    return super.insert(element, index === 0 ? index : 0)
  }
  const pos = this.getIndexNextSortedElement(element) 
  return super.insert(element, pos)
}

链表内是否存在环

合并俩个有序链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var mergeTwoLists = function (l1, l2) {
  if (!l1) {
    return l2
  } else if (!l2) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l2.next, l1)
    return l2
  }
}
// test
var l1 = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 4,
      next: null
    }
  }
}
var l2 = {
  val: 1,
  next: {
    val: 3,
    next: {
      val: 4,
      next: null
    }
  }
}
var total = mergeTwoLists(l1,l2)
console.log(total)

参考链接

• Learning-JavaScript-Data-Structures