2020-10-13（数据结构基础）

数组

有限个相同类型的变量组成有序集合，每个变量都是一个元素。

内存

由一个个连续的内存单元组成，每个内存单元都有自己的地址，这些单元中，部分是被占用的，部分是空闲的。

而数组就是在内存单元中顺序存储，每个元素之间紧密连接。

数组基本操作

• 读操作（get）
  因为数组元素是有序的，所以我们通过其下标就可以直接准确地获取到想要的元素，如list[3]，就是获取到其第四个元素。需要注意的是，下标不能越界。
• 更新（update）
  直接通过数组下标就可以替换数组对应元素的值，如list[3] = 10;

由于上述两个操作的执行时间都与数组长度无关，所以我们可以确定其时间复杂度为O(1)。

• 插入（insert）

  • 尾插入
    当数组元素个数小于数组长度时，数组尾部是有空余空间的，所以往尾部插一个元素非常简单，直接更新index为数组元素长度的位置为新插入的元素
  • 中间插入
    这时我们还是当作数组元素个数小于数组长度，我们需要将插入位置往后的元素，从右往左遍历，依次向右移动一位，然后将插入位置更新为新插入的元素
  • 超范围插入
    首先，我们需要将数组扩容，然后再进行插入操作，扩容的话，可以创建一个大小为原来数组两倍的新数组，将原来数组依次插入，完成复制，再进行插入。

• 删除（delete）
  由于删除元素不可能涉及到数组的扩容，完全就是数组元素位置的移动，所以比较简单，如，删除了中间元素，删除位置往后的元素从左到右依次向左移动一位即可。

综上，插入和删除操作，均涉及到数组元素的移动，所以其时间复杂度为O(n)。

总结

数组是有序的集合，所以我们在访问内部元素时，非常高效便捷，只需要传入index即可，但是一旦想要操作（增、删），其他部分元素会被迫移动位置，效率受到影响。
所以一般在读操作较多，写操作较少的场景，数组比较受欢迎。

---

链表

链表是由一个个节点组成的无序排列的数据结构

单向链表

是时候来张图了

image.png（图片来自漫画算法）

每个节点包括两部分组成

• 数据部分（data）
• 指针部分（next）指向下一个节点（尾节点指向null）

这里要注意的是，看起来它的结构像这样，但是它在内存空间中，是见缝插针地进行存储的，并不像数组一样需要占用一段连续的空间。

在进行查找时，如果我们知道了一个节点，要查找其他节点只能逐级往下进行查找。（next -> next -> next）

如果想要从后往前查找呢？

双向链表

image.png（图片来自漫画算法）
这就很明显啦。
听懂掌声。。。

链表操作

• 读取操作
  链表我们都说了，只能根据next指针一级一级往下查找，所以如果我们要查找一组链表从头节点开始往后的第3个元素，那就需要先定位到头节点，然后头节点的next，next节点的next，再重复一次，才能找到目标元素

• 更新操作
  前提是我们已经找到了该节点，那直接将其data部分给替换掉即可。

• 插入操作

  • 尾插入
    只需要将链表的尾节点的next指针指向新插入的节点即可。
  • 中间插入
    将插入的新节点的next指针指向插入位置的节点，然后将插入位置的前一个节点的next指针指向插入的新节点。
  • 头插入
    将插入的新节点的next指针指向头节点，再将其变为头节点即可。
    链表的修改就不需要考虑扩容的问题，只要内存够，就可以一直插入

• 删除操作
  也有三种（尾删除、中间删除、头删除），懂得自然懂...（前一个的next指向null，前一个的next指向要删除的节点的next，将原来头节点的next设定为头节点即可）

栈和队列

物理结构和逻辑结构

物理结构指的是实实在在真正存在于内存中的结构，而逻辑结构一般是抽象的，底层通过物理结构实现，表现形式为其特有的结构。

image.png（图片来自漫画算法）

栈

栈类似于用瓶子接水，在重力的作用下，先接进去的水肯定在底部，后进去的在顶部。这个过程就是进栈，而出栈的过程就像喝水，瓶口的水就是后接进去的。（说水会混合的杠精打死）简言之就是FILO，先进后出。
具体用数组和链表实现的话，数据就是一环接一环，数组中需要一个数据长度的连续的内存空间，而链表中只需要零散的内存空间即可。

再来讨论下时间复杂度，入栈操作相当于尾插入，无论是数组还是链表都是O(1)。出栈的话相当于尾切割，也是一样。

队列

在收银台，大家都排过队吧，一个接一个的进入队列，一个接一个的买单付款，先来的先付款，遵守秩序（插队的人，出门右转🔪）。

如果用数组来实现队列的出队和入队：
具体一点，一个横向数组，左侧队头，右侧队尾。出队时，左侧少一个元素，入队时，右侧多一个元素，那么如果往复循环多次，那数组长度肯定是不够的，那么我们如何在不扩容的前提下，顺利入队呢？

循环队列

简单来说就是重复利用数组空余的空间，队头出队后，第一个位置就空出来了，如果左侧空间大于2，那就可以满足将第一个位置设为队尾，新入队的元素依次往后排列，一图胜万言

image.png image.png

这样一来，就避免了数组扩容和整体移动的麻烦事。

扩展：双端队列、优先队列（二叉堆）

散列表

也叫哈希表，是key-value的键值对，输入键就能马上得出其对应的值。

中转站-哈希函数

将每一个对象的key转换成数组对应的index。
一般来说，每一个对象都对应一个hashCode，这是他们的唯一标识符，几乎都是一个整型变量。我们想要把key转为index，需要通过key与数组长度的模运算：
index = hashCode(key) & Array.length;
hashCode是一个通过key获取其对应的整型标识符的方法。

散列表的读写操作

• 1、写操作（put）
  在散列表插入新的键值对（entry），将key转换成index，然后将数组中index位置的元素替换为新的value，但是数组的长度有限，会出现该位置已经被占用情况。

  哈希冲突

  解决方法有两种

  • 开放寻址法：
    该位置冲突了，就重新寻找一个位置，直至找到为止。
  • 链表法：
    HashMap为例，每个数组元素对应一个链表，当哈希冲突时，直接将新元素插入到该位置的链表中即可。

• 2、读操作（get）
  通过给定的key，找到对应的元素value。第一步先找到对应的index（by hashFunc），如果该inde对应的值的key不为给定的key，则沿着链表往下继续寻找，直至找到。

• 3、扩容（resize）
  既然会冲突，那么一直让它冲突也不现实，这样会导致单个元素的链表长度越来越大，对后续元素的插入造成诸多影响，所以在一定条件下，我们需要进行扩容。

  判断条件就是：hashMap.size >= Capacity（hashMap当前的长度）x LoadFactory（负载因子，默认为0.75f）

  具体是怎么扩容的呢？

  • 1. 创建一个长度为两倍的新数组；
  • 2. 遍历原数组，将每个元素重新hash进新的数组中。
       经过扩容的散列表会变得稀疏，减少哈希冲突的概率，提高读写效率。

小结：

• 数组：相同类型，有序集合，顺序存储，随机访问；
• 链表：链式数据结构，若干节点，前后指针，随机存储，顺序访问；
• 栈：先进后出，可用数组或链表实现；
• 队列：先进先出，可用数组或链表实现；
• 散列表：也叫哈希表，key-value，哈希函数转换index和key，哈希冲突（开放寻址和链表法解决），扩容条件：size >= capacity * loadFactory

目前为止，介绍的数据结构均为线性的。