数据结构与算法的关系？

  1. 可以容纳数据的结构被称为数据结构(装数据的)，关注的是数据的逻辑、存储等(可以理解为是静态的)
  2. 算法是用来对数据结构进行处理的方法；(可以理解为是动态的，操作型的)

线性数据结构(一维数据结构)之数组

  • 简介： 线性的数据结构强调的事存储与顺序；简单的就是数组与链表；
  1. 数组：
    • 数组的底层是数组定长；当数组长度达到了设定的长度，js引擎会自动扩容；但是，js引擎自动扩容的时候，会消耗CPU，损耗性能；
    • 数组扩容方式：扩容不是在数组后面继续扩容；而是在新的空间，把之前的数组复制下来，然后多扩容相同长度的数组。
    • 扩容：长度为5的数组，js引擎会扩容成长度为10的数组，然后把原来的数组的内容按照顺序复制下来，新扩容的内容从第六位开始依次添加(内存的分配都是操作系统的分配)；
    • 优化：定义时就定义好大概的数组长度，尽量减少js引擎自动扩容的发生；
  2. 数组的特性：(数组的优缺点都基于该特性)
    • 存储在物理空间上是连续的；
    • 底层的数组长度是不可变的；(js语言会扩容)
    • 数组的变量指向的是数组第一个元素的位置;
  1. let a = [1,2,3,4,5,6]
  2. a[1],a[2],a[3];
  3. <!--这个中括号表示存储地址的偏移；在操作系统中，通过偏移查询数据，性能最好-->
  1. 优点：
    • 查询性能是最好的；指定查询某个位置
  2. 缺点：
    • 因为空间必须得是连续的，所以如果数组比较大；当系统的空间碎片较多的时候，容易存不下
    • 因为数组的长度是固定的，所以数组的内容难以被添加或删除；当数组删除某一个偏移位置的内容的时候，该位置后面的内容往前移
  1. var arr = new Array(10);
  2. <!--参数10就是定义该数组长度为10；这种方式性能较好-->

线性数据结构(一维数据结构)之链表(大多数使用的是单链表)

  1. 链表的特性：
    在空间上不是连续的；
     每存放一个值，都要多开销一个引用空间
    传递链表，必须传递链表的根节点，每一个节点都认为自己是根节点,因为每一个节点都只知道自己指向谁，不知道谁指向了自己(重要)
     需要删除某个节点的时候，只需要断开该节点的上一个节点的指向，把上一个节点的指向改为下一个节点即可
    2. 链表的优点：
    只要内存足够大，就能够存的下，不用担心空间碎片的问题
     链表的添加和删除非常的容易；
    3. 缺点：
    查询速度慢(查询某个位置);
     链表每一个节点都需要创建一个指向next的引用，浪费一些空间；当节点内数据越多的时候，这部分多开销的内存影响越少；
    4. 每一个节点都包括两个部分:
    1. 本事的变量数据
    2. 下一个节点的引用
    5. 链表的创建:
    1. function Node(value){
    2. this.value = value;
    3. this.next = null
    4. }
    5. var a = new Node(1);
    6. var b = new Node(2);
    7. var c = new Node(3);
    8. var d = new Node(4);
    9. a.next = b;
    10. b.next = c;
    11. c.next = d;
    12. d.next = null;
    13. console.log(a.value);
    14. console.log(a.next.value);
    15. console.log(a.next.next.value);
    16. console.log(a.nent.next.next.value);
    17. <!--
    18. 这种就是链表的基础写法：
    19. 输出结果为1，2，3，4    
    20. -->