链表

2020年04月20日

算法

数组需要一块连续的内存空间来存储，对内存的要求比较高。
链表不需要一块连续的内存空间来存储，它通过“指针”将一组零散的内存块串联起来使用
三种最常见的链表结构：单链表、双向链表和循环链表

单链表

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
801336-20200419161045810-2041686313

与数组一样，链表也支持数据的查找、插入和删除操作。
在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。

从图中我们可以看出，针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)
801336-20200419161414896-1780354389
链表要想随机访问第 k 个元素，就没有数组那么高效了。**因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。**链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

js 实现单链表

/**
 * 1）单链表的插入、删除、查找操作；
 * 2）链表中存储的是int类型的数据；
 */

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

class SingleLinkedList {
  constructor() {
    this.head = new Node("head");
  }
  // 根据value查找节点
  findByValue(val) {
    let currentNode = this.head.next;
    while (currentNode !== null && currentNode.element !== val) {
      currentNode = currentNode.next;
    }
    return currentNode === null ? -1 : currentNode;
  }
  // 根据index查找节点，下标从0开始
  findByIndex(index) {
    let currentNode = this.head.next;
    let pos = 0;
    while (currentNode !== null && pos !== index) {
      currentNode = currentNode.next;
      pos++;
    }
    return currentNode === null ? -1 : currentNode;
  }
  // 查找前一个
  findPrev(value) {
    let currentNode = this.head;
    while (currentNode.next !== null && currentNode.next.element !== value) {
      currentNode = currentNode.next;
    }
    if (currentNode.next === null) {
      return -1;
    }
    return currentNode;
  }
  // 向链表末尾追加节点
  append(newElement) {
    const newNode = new Node(newElement);
    let currentNode = this.head;
    while (currentNode.next) {
      currentNode = currentNode.next;
    }
    currentNode.next = newNode;
  }
  // 指定元素向后插入
  insert(newElement, element) {
    const currentNode = this.findByValue(element);
    if (currentNode === -1) {
      console.log("未找到插入位置");
      return;
    }
    const newNode = new Node(newElement);
    newNode.next = currentNode.next;
    currentNode.next = newNode;
  }
  // 根据值删除
  remove(value) {
    const prevNode = this.findPrev(value);
    if (prevNode === -1) {
      console.log("未找到元素");
      return;
    }
    prevNode.next = prevNode.next.next;
  }
  // 遍历显示所有节点
  display() {
    let currentNode = this.head.next; // 忽略头指针的值
    while (currentNode !== null) {
      console.log(currentNode.element);
      currentNode = currentNode.next;
    }
  }
}

// Test
const LList = new SingleLinkedList();
LList.append("chen");
LList.append("curry");
LList.append("sang");
LList.append("zhao"); // chen -> curry -> sang -> zhao
console.log("-------------insert item------------");
LList.insert("qian", "chen"); // 首元素后插入
LList.insert("zhou", "zhao"); // 尾元素后插入
LList.display(); // chen -> qian -> curry -> sang -> zhao -> zhou
console.log("-------------remove item------------");
LList.remove("curry");
LList.display(); // chen -> qian -> sang -> zhao -> zhou
console.log("-------------find by item------------");
LList.findByValue("chen");
console.log("-------------find by index------------");
LList.findByIndex(2);
console.log("-------------与头结点同值元素测试------------");
LList.insert("head", "sang");
LList.display(); // chen -> qian -> sang -> head -> zhao -> zhou
LList.findPrev("head"); // sang
LList.remove("head");
LList.display(); // chen -> qian -> sang -> zhao -> zhou

循环链表

循环链表是一种特殊的单链表
它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。
801336-20200419161712465-1518149387

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表

双向链表

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
801336-20200419161922172-1176250872
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历

双向链表要比单链表更加高效是因为采用空间换时间的设计思想

js 实现双向链表

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
  }
}
class DoubleLinkedList {
  constructor() {
    this.head = new Node("head");
  }
  find(val) {
    let currentNode = this.head;
    while (currentNode !== null && currentNode.element !== val) {
      currentNode = currentNode.next;
    }
    return currentNode === null ? -1 : currentNode;
  }
  append(element) {
    const newNode = new Node(element);

    let currentNode = this.head;
    while (currentNode.next) {
      currentNode = currentNode.next;
    }
    currentNode.next = newNode;
    newNode.previous = currentNode;
  }
  insert(newElement, element) {
    const currentNode = this.find(element);
    if (currentNode === -1) {
      console.log("未找到插入位置");
      return;
    }
    const newNode = new Node(newElement);
    if (currentNode.next !== null) {
      newNode.next = currentNode.next;
      currentNode.next = newNode;
      newNode.previous = currentNode;
      newNode.next.previous = newNode;
    } else {
      currentNode.next = newNode;
      newNode.previous = currentNode;
    }
  }
  remove(element) {
    const currentNode = this.find(element);
    if (currentNode === -1) {
      console.log("要移除节点不存在");
      return;
    }
    if (currentNode.next !== null && currentNode.previous !== null) {
      /*首先是不是头尾节点的情况*/
      currentNode.previous.next = currentNode.next;
      currentNode.next.previous = currentNode.previous;
      currentNode.next = null;
      currentNode.previous = null;
    } else if (currentNode.previous === null) {
      /*当是头节点的时候*/
      this.head = currentNode.next;
      currentNode.next.previous = null;
      currentNode.next = null;
    } else if (currentNode.next == null) {
      /*当是尾节点的时候 */
      currentNode.previous.next = null;
      currentNode.previous = null;
    }
  }
  display() {
    let currentNode = this.head.next; // 忽略头指针的值
    while (currentNode !== null) {
      console.log(currentNode.element);
      currentNode = currentNode.next;
    }
  }
}

var list = new DoubleLinkedList();
list.append("one");
list.insert("two", "one");
list.insert("three", "two");
list.insert("four", "three");
// list.display();

list.append("A");
list.append("B");
list.insert("B2", "B");
// list.display();
list.remove("one");
// list.display();
console.log(list.find("A").previous);
// console.log(list.find('four').previous)
// console.log(list.head.element)

链表 VS 数组性能大比拼

801336-20200419162344175-472578080
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别

和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。

几个写链表代码技巧

技巧一：理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄漏

删除链表结点时，也一定要记得手动释放内存空间

技巧三：利用哨兵简化实现难度

单链表的插入操作

if (head == null) {
  head = new_node; //插入头结点
}
new_node->next = p->next;
p->next = new_node;

单链表的删除操作

p->next = p->next->next;

if (head->next == null) {
   head = null; // 删除尾节点
}

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

技巧四：重点留意边界条件处理

我经常用来检查链表代码是否正确的边界条件有这样几个：

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

技巧五：举例画图，辅助思考

技巧六：多写多练，没有捷径

6 个常见的链表操作

链表反转

/* 
双指针解法
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
*/

var reverseList = function (head) {
  let pre = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = pre;
    pre = cur; // pre前进一位
    cur = next; // cur前进一位
  }
  return pre;
};
/**
 * 递归解法
 */
var reverseList = function (head) {
  if (head == null || head.next == null) {
    return head;
  }
  const current = reverseList(head.next);
  //例如，1，2，3，4，5,null
  //current是5
  //head是4
  //head.next 是 5
  //head.next.next 就是5指向的指针，指向当前的head（4）
  //5-4-3-2-1-null
  head.next.next = head;
  //注意把head.next设置为null，切断4链接5的指针
  head.next = null;
  //每层递归返回当前的节点，也就是最后一个节点。（因为head.next.next改变了，所以下一层current变4，head变3）
  return current;
};

动态图
1632933523

回文链表

/**
 * 栈
 * 定义一个数组，循环遍历链表，将链表中的每个节点都放入栈中，再一一比较。
 */
var isPalindrome = function (head) {
  const stack = [];
  let temp = head;
  while (temp) {
    stack.push(temp);
    temp = temp.next;
  }
  while (head) {
    if (head.val !== stack.pop().val) {
      return false;
    }
    head = head.next;
  }
  return true;
};

/**
 * 快慢指针
定义两个指针slow和fast初始分别指向head和head.next。
我们可以思考一下：slow每次向后走一格，fast每次向后走两格，当fast或fast.next到链表末尾时，slow指针正好走到链表的中心位置（如果是奇数个节点，正好是中心；如果是偶数个节点，则是中心前一个节点）。
所以，当slow走到中心后，我们只需要，将slow.next也就是中心之后的链表段进行翻转。
再将原来的head和翻转后的slow.next进行一一比对即可。
 */
var isPalindrome = function (head) {
  let slow = head,
    fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let back = reverseList(slow.next);
  while (back) {
    if (head.val !== back.val) {
      return false;
    }
    head = head.next;
    back = back.next;
  }
  return true;
};
function reverseList(head) {
  if (!head || !head.next) return head;
  const r = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return r;
}

链表中环的检测

/**
 * 利用Map结构 判断是否有重复 时间复杂度为O(N)
通过遍历链表方式把每一个节点都通过set方式到Map对象中；
set之前先通过has方式判断Map对象中是否存在该结点，如果存在，则为有环；
当遍历完成也就是 next 指针指向null的话，则为无环。
 */
var hasCycle = function (head) {
  let map = new Map();
  while (head) {
    if (map.has(head)) {
      return true;
    } else {
      map.set(head);
      head = head.next;
    }
  }
  return false;
};

/**
 * 快慢指针 时间复杂度O(1)
当快指针的下一位仍有数值时，通过while继续移动快慢指针；
如果快指针和慢指针相遇（重合），说明该链表是有环链表，返回True；
如果快指针走到链表尾仍没有遇到慢指针，说明是无环链表，返回False。
 */
var hasCycle = function (head) {
  let p1 = head;
  let p2 = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      return true;
    }
  }
  return false;
};

合并两个有序链表

/**
 首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。
 我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。
 然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：
 如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。
 否则，我们对 l2 做同样的操作。
 不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元

 */
var mergeTwoLists = function (list1, list2) {
  const prehead = new ListNode(-1);

  let prev = prehead;
  while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
      prev.next = list1;
      list1 = list1.next;
    } else {
      prev.next = list2;
      list2 = list2.next;
    }
    prev = prev.next;
  }

  // 合并后 list1 和 list2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
  prev.next = list1 === null ? list2 : list1;

  return prehead.next;
};

删除链表倒数第 n 个结点

/**
 * 双指针
 */
var getKthFromEnd = function (head, n) {
  let ret = new ListNode(0, head),
    slow = (fast = ret);
  // fast向后移动n个位置
  while (n--) fast = fast.next;
  // fast走到最后，slow此时是倒数第n个元素的前一个
  while (fast.next !== null) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return ret.next;
};

求链表的中间结点

/**
 * 双指针
 */
var middleNode = function (head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    head = head.next;
  }
  return slow;
};

原文链接: https://jesse121.github.io/blog/articles/2020/04/20.html

版权声明: 转载请注明出处.

前端之路

路漫漫其修远兮，吾将上下而求索

链表

单链表