线性表数据结构

线性表

线性表就是数据排成像一条线的结构，每个线性表上的数据最多只有前和后两个方向。与线性表对立的是非线性表，如二叉树、堆、图就是非线性表结构。非线性表中，数据不只是简单的前后关系。线性表结构的数据结构有数组、链表、队列等。

数组

数组，用一组连续的内存空间存储一组相同类型的数据。

定义中牵扯到几个关键词：

• 连续的内存空间和相同的数据类型
  正是因为这两个限制，数组才能够随机访问，但这也让数组的很多操作变得低效，例如数组插入、删除数据，为了保证连续性，需要做数据搬移的工作。

数组的随机访问：

a[i]_address = base_address + i * data_type_size

base_address是数组首地址，data_type_size是每个元素的大小。因为相同元素，所以data_type_size相同。这也是为什么数组的小标通常从0开始，因为第一个元素的地址就是数组首地址。

高级语言中，针对数组类型都提供了容器类，如Java中的ArrayList、OC中的NSArray。这些容器类会将很多数组操作的细节封装起来，这些容器类都支持动态扩容，当存储空间不够时自动扩容为原来的若干倍。扩容涉及内存的申请和数据的搬移，比较耗时，如果事先知道存储的数据大小，最好在创建时事先指定好数组大小。

当遇到如下情况时优先选择使用数组：

• 特别关注性能或希望存储使用基本数据类型
• 数据大小事先已知，对数据的操作简单用不到容器类提供的大部分方法
• 多维数组时，用数组更加直观

对于业务开发，使用容器类就足够了，开发效率更高，损失的一点点性能不影响系统整体的性能。做非常底层的开发，如网络框架，性能优化要做到极致，优先使用数组。

链表

链表通过指针将一组零散的内存块串联在一起，每个内存块称为链表的结点。

这篇文章介绍三种常见的链表结构：单向链表、双向链表、循环链表。

• 单向链表

单链表.jpg

单向链表只有一个方向，结点只有一个后继指针next指向后面的结点。单项链表有两个点比较特殊。第一个结点也叫头结点，是用来记录链表的基地址，有了它我们可以遍历整条链表。最后一个结点也叫尾结点，尾结点指向一个空地址Null，表示这是链表上最后一个结点。

链表也支持查找、插入、删除操作。跟数组相比，链表的插入和删除操作只需改变相邻结点的指针，对应的时间复杂度为O(1)。而链表因为内存不连续，先要访问第K个元素只能根据指针依次遍历结点，直到找到相应的结点，对应的时间复杂度为O(n)。

• 循环链表
  循环链表是一种特殊的单向链表，它和单向链表唯一的区别是尾结点指向链表的头结点。

循环链表.jpg

循环链表的优点是从链尾到链头比较方便，当要处理的数据具有环形结构特点，适合采用循环列表，例如约瑟夫问题。

• 双向链表
  双向链表，支持两个方向，每个结点的后继指针next指向后面的结点，前驱指针prev指向前面的结点。

双向链表.jpg

双向链表需要额外的空间存储后继和前驱结点的地址，所以双向链表占用内存更多，但可以支持双向遍历，使得双向链表在某些情况的下的插入、删除、查询操作更高效。比如删除指定指针指向的结点，因为双向链表中保存了前驱结点的指针，单向链表为了找到前驱结点要从头遍历。再比如向指定结点前插入一个结点，查询一个有序链表等，双向链表的效率都要更高。

这就是用“空间换时间”的设计思想。当内存空间充足，追求代码执行速度，可以选择空间复杂度相对高但时间复杂度低的算法或数据结构。反过来，内存紧缺，使用时间复杂度高但空间复杂度低的算法或数据结构，这就是“时间换空间”设计思想。

• 双向循环链表
  把循环链表和双向链表结合在一起就是双向循环链表。

  
  双向循环链表.jpg

链表实现LRU缓存淘汰策略

缓存是一种提高数据读取性能的技术，但缓存大小有限，需要制定策略当缓存用满时，将哪些数据清理出去哪些数据保留。常见策略有三种：

• 先进先出策略FIFO(First in First out)
• 最少使用策略LFU(Least Frequently Used)
• 最近最少使用策略LRU(Least Recently Used)

下面说一些基于链表实现LRU缓存淘汰算法，维护一个有序单向链表，越靠近链表尾部的结点是越早访问的数据。当有新数据被访问，从链表头部开始遍历链表：

• 如果此数据已经缓存在链表中，将遍历得到的结点从原来的位置删除，再插入到链表的头部；
• 如果链表中没有缓存过，且缓存未满，直接将结点插入链表头部；
• 如果链表中没有缓存过，且缓存已满，将尾结点删除，再将新的数据插入链表头部；

这样就用链表实现了LRU缓存。

栈

栈是这样一种数据结构，越先存入栈中的数据，越后从栈中移除。后进者先出，先进者后出，这就是典型的栈结构。

当某个数据集合只涉及在一段插入和删除数据，且满足后进先出、先进后出的特性，应该首选栈这种数据结构。

栈的实现

栈可以用链表和数组实现，用数组实现的叫做顺序栈，用链表实现的叫做链式栈。

栈的应用

栈作为一个基础数据结构应用场景很多

• 函数调用栈
  操作系统给每个线程分配一块独立的内存空间，这块内存被组织成栈这种结构，用来存储函数调用的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，函数执行完毕将函数对应的栈帧出栈。

  
  函数栈.jpg

• 栈在表达式求值中的应用
  通过两个栈实现表达式求值，一个保存操作数的栈，另一个保存运算符的栈。从左向右遍历表达式，数字压入操作数栈，遇到运算符，与运算符栈的栈顶元素比较优先级，如果比栈顶元素优先级高，就将当前运算符压入栈。如果比栈顶元素优先级低或相等，从运算符栈取栈顶运算符，从操作数栈栈顶取两个操作数进行计算，再把计算完的结果压入栈，继续比较。如下图

表达式求值.jpg

• 浏览器前进后退功能
  使用两个栈X和Y，将首次浏览的页面依次压入栈X，点击后退按钮时，依次从栈X中出栈并将出栈数据依次压入栈Y。点击前进按钮时，依次从栈Y中取出数据压入栈X中。当栈X没有数据时，说明没有页面可以后退浏览了。当栈Y没有数据，说明没有页面可以前进浏览了。

  
  浏览器.jpg

队列

队列，就像排队买票，先来的先买后来的站在末尾排队。先进者先出，就是“队列”。队列也是一种操作受限的线性表数据结构。只能将数据放到队尾，叫做入队；从队列头部取元素，叫做出队；
队列可用数组和链表实现，数组实现的队列叫做顺序队列，链表实现的队列叫做链式队列。

队列.png

队列需要两个指针：head指针指向队头；tail指针，指向队尾。结合下图理解，a、b、c、d依次入队后，队列中的head指针指向0的位置，tail指针指向4的位置

dequeue_1.jpg

两次出队操作后，head指向2的位置，tail仍指向4的位置

dequeue_2.jpg

随着不停的入队出队，tail 和 head会持续向后移动。当tail移动到最右边时，即使数组中还有空间，也无法继续往队列中添加数据了。

此时需要通过数据搬移来解决这个问题，但如果每次出队都搬移整个队列的数据，出队的时间复杂度从O(1)变为O(n)。我们可以在没有空闲空间的情况下，入队时集中做一次数据搬移操作即可，这样出队保持不变。

循环队列

用数组来实现队列的时候，在 tail==n 时，会有数据搬移，这样入队操作性能就会受到影响，循环队列也可以解决这个问题。

CircularQueue.jpg

队列大小为8，当前head=4，tail=7。当再有新元素入队，放入7的位置，但不把tail更新为8，而是在环中后移一位到0的位置，再有新元素入队放入位置0。通过这样，避免了数据搬移。实现循环队列的关键是，确定好队满和队空的判定条件。

队满判断条件：head = tail;
队空判断条件：(tail+1)%n = head;

阻塞队列

阻塞队列是在队列基础上增加了阻塞条件。队列为空时，从队头取数据会被阻塞，直到队列中有了数据才能返回；队列已满，插入数据的操作会被阻塞，直到队列有空闲位置再插入。这个定义其实就是“生产者-消费者模型”，使用阻塞队列可以实现“生产者-消费者模型”。

并发队列

线程安全的队列叫并发队列。简单的实现是在出队和入队时加锁，但加锁粒度大并发度会降低，同一时刻只能运行一个存或取操作。

以上内容是对学习极客时间王争出品的数据结构与算法之美的总结，若感兴趣可以去订阅学习！