1️⃣ 线性数据结构之数组

线性数据结构强调存储与顺序

2️⃣ 数组的特性

  1. 储存在物理空间上是连续的
  2. 底层的数组长度是不可变的
  3. 数组的变量，指向了数组的第一个元素的位置
  • 优点：查询性能好
  • 缺点：
    1. 因为空间必须得是连续的，所以如果数组比较大，当系统的空间碎片比较多的时候，容易存不下
    2. 因为数组的长度是固定的，所以数组的内容难以被添加和删除

2️⃣ 数组的实际操作

  1. // 声明一个数组
  2. let arr = [1, 2, 3, 4, 5];
  3. // 为数组最后一位添加一个数字 6
  4. arr.push(6);
  5. // 实际上是开辟了一个新的储存空间生成一个这样的数组 [1 , 2, 3, 4, 5, 6] 在赋值给 arr
  6. let arr = [1, 2, 3, 4, 5, 6];

1️⃣ 线性数据结构之链表

image.png

2️⃣ 链表的特点

  1. 空间上不是连续的
  2. 每存放一个值，都要多开销一个引用空间
  • 优点:
    1. 只要内存足够大，就能存的下，不用担心空间碎片的问题
    2. 链表的添加和删除非常的容易
  • 缺点:
    1. 查询速度慢 ( 指查询某个位置 )
    2. 链表每一个节点都需要创建指向 next 的引用，浪费一些空间，当节点内数据越多的时候，这部分多开销的内存影响越少
      1. // 链表结构
      2. var b = {
      3. value: 2,
      4. next: null,
      5. };
      6. var a = {
      7. value: 1,
      8. next: b,
      9. };
      10. console.log(a.next == b); // true

2️⃣ 创建一个单项链表

  1. // 创建一个链表
  2. function Node(value) {
  3.   this.value = value;
  4.   this.next = null;
  5. }
  6. var a = new Node(1);
  7. var b = new Node(2);
  8. var c = new Node(3);
  9. a.next = b;
  10. b.next = c;
  11. c.next = null;
  12. console.log(a.value); // 1
  13. console.log(a.next.value); // 2
  14. console.log(a.next.next.value); // 3

2️⃣ 创建一个双向链表

双向链表的优点，无论给出哪一个节点，都能对整个链表进行遍历
双向链表的缺点，对耗费一个引用空间，而且构建起来比较复杂

  1. function Node(value) {
  2.   this.value;
  3.   this.next = null;
  4.   this.pre = null;
  5. }
  7. var node1 = new Node(1);
  8. var node2 = new Node(2);
  9. var node3 = new Node(3);
  10. var node4 = new Node(4);
  11. var node5 = new Node(5);
  13. node1.next = node2;
  14. node2.pre = node1;
  15. node2.next = node3;
  16. node3.pre = node2;
  17. node3.next = node4;
  18. node4.pre = node3;
  19. node4.next = node5;
  20. node5.pre = node4;

1️⃣ 线性数据结构的遍历

遍历：将一个集合中的每一个元素进行获取并查看

  1. // 创建一个链表
  2. function Node(value) {
  3.   this.value = value;
  4.   this.next = null;
  5. }
  7. var a = new Node(1);
  8. var b = new Node(2);
  9. var c = new Node(3);
  11. a.next = b;
  12. b.next = c;
  13. c.next = null;
  15. function bianli(root) {
  16.   var temp = root;
  17.   while (true) {
  18.     if (temp != null) {
  19.       console.log(temp.value, temp);
  20.       // 输出
  21.       // 1 Node {
  22.       //   value: 1,
  23.       //   next: Node { value: 2, next: Node { value: 3, next: null } }
  24.       // }
  25.       // 2 Node { value: 2, next: Node { value: 3, next: null } }
  26.       // 3 Node { value: 3, next: null }
  27.     } else {
  28.       break;
  29.     }
  30.     temp = temp.next;
  31.   }
  32. }
  33. bianli(a);

1️⃣ 线性数据结构的递归

  1. function Node(value) {
  2.   this.value = value;
  3.   this.next = null;
  4. }
  6. var a = new Node(1);
  7. var b = new Node(2);
  8. var c = new Node(3);
  10. a.next = b;
  11. b.next = c;
  12. c.next = null;
  14. function bianli(node) {
  15.   if (node == null) return;
  16.   console.log(node.value);
  17.   // 输出
  18.   // 1
  19.   // 2
  20.   // 3
  21.   bianli(node.next)
  22. }
  23. bianli(a);

1️⃣ 链表的逆置

  1. function Node(value) {
  2.   this.value = value;
  3.   this.next = null;
  4. }
  6. var a = new Node(1);
  7. var b = new Node(2);
  8. var c = new Node(3);
  10. a.next = b;
  11. b.next = c;
  12. c.next = null;
  14. // 链表递归函数
  15. function bianli(node) {
  16.   if (node == null) return;
  17.   console.log(node.value);
  18.   bianli(node.next)
  19. }
  21. // 链表逆置函数
  22. function nizhi(node) {
  23.   if (node.next.next == null) { // 代表当前节点事倒数第二个节点
  24.     node.next.next = node; // 让最后一个节点指向自己 ( 倒数第二个节点 )
  25.     return node.next;
  26.   } else {
  27.     var result = nizhi(node.next);
  28.     node.next.next = node;
  29.     node.next = null;
  30.     return result;
  31.   }
  32. }
  33. bianli(a);
  34. /* 
  35.  * 1
  36.  * 2
  37.  * 3 
  38.  */
  39. nizhi(a) // 执行链表逆置的函数
  40. bianli(c);
  41. /* 
  42.  * 3
  43.  * 2
  44.  * 1 
  45.  */