回炉重造12时辰(数据结构)-线性表
回炉重造12时辰(数据结构)-线性表
文章图片
线性表（Linear List）就是数据排成像一条线一样的结构，数据只有前后两个方向，线性表包含四种常见的数据结构，他们分别是：数组，链表，栈，队列。
线性表（Linear List）就是数据排成像一条线一样的结构，数据只有前后两个方向
文章图片
1.数组
1.1概念
数组（Array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是
最为简单、最为常用的数据结构。
数组的下标从0开始。
1.2存储原理
数组用一组连续的内存空间来存储一组具有相同类型的数据
文章图片
1.3操作
- 查询数据:直接根据下标查询。
int obj = arry[i] - 更新数据:根据下标进行数据更新。
arry[i] = 10 - 删除数据
- 如果删除的数据位于最后，直接删除即可
- 如果删除的数据位于中间，删除后需要将目标元素后面的元素统一往前移动
- 新增数据
- 尾部插入：直接将数据给到数组的尾部空闲位置，和更新数据很像。
- 中间插入：在数据的实际元素数量小于数组长度的情况下：由于数组的每一个元素都有其固定下标，所以首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。
- 超范围插入数据：这时就要对原数组进行扩容：可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统
统复制到新数组中。
- 读取和更新数据都是随机直接访问(按照下标访问)，因此时间复杂度为O(1)
- 插入数据进行数组扩容的时间复杂度为O(n)，插入并移动元素的时间复杂度也是O(n),综合起来插入操作的时间复杂度为O(n)
- 删除操作涉及到了元素的移动，因此时间复杂度为O(n)
- 遍历数据查询数据的操作时间复杂度是O(n),因为此种方式不是通过下标直接找到的数据
- 优点：数组的随机访问能力比较强，只要有下标就能够在时间复杂度为O(1)的情况下直接找到数据，效率较高。
- 缺点：插入和删除数据方面，由于数据是紧密的存储在连续的空间中，因此插入数据和删除数据都牵扯到大量元素的移动，因此效率比较低。
- ArrayList的底层数据结构是数组
- Redis和消息队列中也应用到了数据的数据结构
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元
素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据
域，另一个是存储下一个结点地址的指针域。（百度百科）
链表的分类
- 单向链表
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节
点的指针next
文章图片
- 双向链表
双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。
文章图片
- 循环链表
链表的尾节点指向头节点形成一个环，称为循环链表
文章图片
2.2 存储原理
链表在内存中的存储方式则是随机存储（链式存储）。
链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。
文章图片
2.3 操作
- 查找节点：链表只能从头节点开始向后一个一个节点逐一查找。
- 更新节点：找到要更新的节点，然后把旧数据替换成新数据。
- 插入节点：
- 尾部插入：把最后一个节点指向的next的指针指向新插入的节点就好
- 头部插入：将新插入的节点的next指针指向头节点，将新节点变为头节点
- 中间插入：新节点的next指针指向插入位置的节点；插入位置节点的前置节点的指针指向新的节点
- 删除节点：
- 尾部删除：将倒数第二个节点的next指针指向NULL即可
- 头部删除：把链表的头节点设为原先头节点的next指针即可
- 中间删除：把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可
- 查找节点 ： O(n)
- 插入节点：O(1)
- 更新节点：O(1)
- 删除节点：O(1)
优势：插入、删除、更新效率高，空间使用率高
缺点：查询效率低下，不能随机访问
2.6 应用
如树、图、Redis的列表、LRU算法实现、消息队列等
2.7 与数组的比较
- 数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些
- 链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适一些
- 数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。
栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。
最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。
3.2存储原理
文章图片
3.3操作
- 入栈：入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
- 出栈：出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
- 入栈和出栈的时间复杂度都是O(1)
- 当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组，通过前面学过的知识，可以得知入栈的时间复杂度是O(n)
- 函数的调用
- 浏览器网页的后退功能
队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。
队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。
4.2存储原理
文章图片
4.3操作
- 入队：入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。
- 出队：出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。
入队和出队都是O(1)
4.5应用
【回炉重造12时辰(数据结构)-线性表】资源池、消息队列、命令队列等等
