链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。

JS中的简单链表实现：

  1. class Node {
  2.   constructor(element) {
  3.     this.element = element;
  4.     this.next = null;
  5.   }
  6. }
  8. class LinkNodeList {
  9.   constructor() {
  10.     // 链表
  11.     // 链表的第一个元素
  12.     this.head = null;
  13.     this.length = 0;
  14.   }
  15.   // 链表的相关操作
  16.   // 增删改查
  17.   // 增加
  18.   append(element) {
  19.     let node = new Node(element);
  20.     let curr;
  21.     // 两种情况：1.链表是空的 2.链表不是空的
  22.     if (this.head == null) {
  23.       // head是第一个
  24.       this.head = node;
  25.     } else {
  26.       // 遍历链表
  27.       curr = this.head;
  28.       while (curr.next) {
  29.         curr = curr.next;
  30.       }
  31.       curr.next = node;
  32.     }
  33.     this.length += 1;
  34.   }
  36.   removeAt(index) {
  37.     let curr = this.head;
  38.     let prev;
  39.     let i = 0;
  40.     if (index == 0) {
  41.       // 删除第一项
  42.       this.head = curr.next;
  43.     } else {
  44.       while (i < index) {
  45.         prev = curr;
  46.         curr = curr.next;
  47.         i++;
  48.       }
  49.       prev.next = curr.next;
  50.       // curr.next = null;
  51.     }
  52.     this.length -= 1;
  53.     return curr.element;
  54.   }
  56.   print() {
  57.     let curr = this.head;
  58.     let ret = [];
  59.     while (curr) {
  60.       ret.push(curr.element);
  61.       curr = curr.next;
  62.     }
  63.     console.log(ret.join('==>'));
  64.     return ret.join('==>');
  65.   }
  66. }
  68. let linkNode = new LinkNodeList();
  69. linkNode.append('哈喽');
  70. linkNode.append('你瞅啥');
  71. linkNode.append('嘿嘿');
  72. linkNode.append('瞅你咋的');
  74. linkNode.print();
  75. linkNode.removeAt(2);
  76. linkNode.print();

二叉树

二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

三种遍历方式：

  • 前序遍历：自己 -> left -> right
  • 中序遍历：left -> 自己 -> right
  • 后序遍历：left -> right -> 自己

eg:

  1.          1
  2.      /     \
  3.   2     3
  4.  / \         \
  5. 4  5          6

前序遍历：1 => 2 => 4 => 5 => 3 => 6
中序遍历：4 => 2 => 5 => 1 => 6 => 3
后序遍历：4 => 5 => 2 => 6 => 3 => 1

备注：所有子文档中的 算法题 均来自于 leetcode。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。