这里需要强调几个关键点：
首先，它是一个序列，这意味着元素按照先到先得的原则出现。如果有多个元素，第一个元素没有前驱，最后一个元素没有后继。其他元素只有一个前任和后继者。另外，强调线性表的局限性。事实上，无论计算机变得多么强大，它能处理的元素都是有限的。
如果线性表记为(a1,ai-1,ai,ai+1,an)，则表中ai-1领先ai，ai领先ai+1，ai-1据说是ai的直接结果。前体元素ai+1 是ai 的直接后继元素。
因此，线性表元素的数量n(n=0)被定义为线性表的长度。当n=0时，称为空列表。
1.1 线性表数组
1.1.1 操作
(1) 定义线性表
线性表存储结构定义：
正如你所看到的，这里我们封装了一个结构体。事实上，我们封装了数组并添加了一个当前长度的变量。
总结一下，顺序存储结构封装需要三个属性：
存储空间的起始位置，即数组数据的存储位置，就是线性表存储空间的存储位置。
线性表的最大存储容量：数组的长度MaxSize。
线性表当前长度：length。
注意，数组的长度需要和线性表当前的长度区分开来：
数组的长度是存储线性表的存储空间的总长度，初始化后一般不会改变。
线性表的当前长度是线性表中元素的数量，该长度会发生变化。
(2)获取元素
实现GetElem的具体操作，即返回线性表L中第i个位置元素的值。就程序而言，非常简单。我们只需要返回数组的第i-1个下标的值即可。
(3)插入元素
1、如果插入位置不合理，会抛出异常；
2、如果线性表的长度大于等于数组的长度，则抛出异常或者动态增加数组容量；
3、从最后一个元素向前遍历到第i个位置，并将它们向后移动一个位置；
4、在位置i处填写要插入的元素；
5. 线性工作台长度+1。
(4)删除元素
1、如果删除位置不合理，会抛出异常；
2、移除被删除的元素；
3、从被删除的元素位置遍历到最后一个元素位置，并分别向前移动一个位置；
4. 工作台长度-1。
1.1.2 优缺点
线性表的顺序存储结构，无论在哪里存储和读取数据，时间复杂度都是O(1)。插入或删除时，时间复杂度为O(n)。这说明它更适合元素数量比较稳定、不频繁插入和删除元素、更多操作是访问数据的应用。
（一）优势
不需要添加额外的存储空间来表达表中元素之间的逻辑关系。
您可以快速访问表中任何位置的元素。
（二）缺点
插入和删除操作需要移动大量元素。
当线性表的长度变化较大时，很难确定存储空间的容量。
很容易造成存储空间的“碎片”。
1.2 线性表的链表
前面我们讲的线性表的顺序存储结构最大的缺点就是插入和删除时需要移动大量元素，这显然很耗时。那么我们能不能想出一个办法来解决这个缺点或者遗憾呢？要解决这个问题，我们就得考虑这个问题产生的原因！为什么插入和删除时需要移动大量元素？原因是两个相邻元素的存储位置也存在邻居关系。它们在记忆中的位置是很接近的，中间没有间隙。当然，它们不能快速插入和删除。
线性表链接存储结构的特点是用一组任意的存储单元来存储线性表的数据元素。这组存储单元可以存储在内存中任何未被占用的位置。与顺序存储结构相比，每个数据元素只需存储在一个位置。
1.2.1 单链表
现在链式存储结构中，除了存储数据元素信息外，还必须存储其后续元素的存储地址（指针）。也就是说，除了存储自身的信息之外，还需要存储指示其直接后继的存储位置的信息。我们将存储数据元素信息的字段称为数据字段，而存储直接后继位置的字段称为指针字段。指针字段中存储的信息称为指针或链。这两部分信息组成的数据元素称为存储图像，称为节点。 n个节点链接成链表，是线性表（a1,a2,a3,an）的链接存储结构。由于该链表的每个节点只包含一个指针字段，因此称为单链表。
对于线性表来说，必须有头和尾，链表也不例外。我们将链表中第一个节点的存储位置称为头指针，最后一个节点指针为NULL。
头指针：
1、头指针是指指向链表第一个节点的指针。如果链表有头节点，则它是指向头节点的指针。
2、头指针具有标识功能，因此头指针常以链表的名称（指针变量的名称）来命名。
3、无论链表是否为空，头指针都不为空。
4、头指针是链表的必要元素。
头节点：
1. 建立头节点是为了统一和方便操作。它放在第一个元素的节点之前，它的数据字段一般没有意义（但也可以用来存储链表的长度）。
2、有了头节点，在第一个元素节点之前插入节点和删除第一个节点的操作与其他节点的操作统一。
3、头节点不一定是链表的必要元素。
1.2.1.1 操作
(1) 定义单链表
我们看到，节点由存储数据元素的数据字段和存储后续节点地址的指针字段组成。假设p是指向线性表第i个元素的指针，那么我们可以使用节点ai的数据字段中p-data的值作为数据元素。节点ai的指针域可以用p-next来表示，p-next的值为一个指针。那么p-next指向谁呢？当然是指向第i+1个元素啦！即指向ai+1的指针。
问题：如果p-data=ai，那么p-next-data=？
答案：p-下一个数据=ai+1。
(2)读取元素
在线性列表的顺序存储结构中，我们很容易计算出任意元素的存储位置。但是在单向链表中，第i个元素在哪里呢？我们没办法从一开始就知道，只能从第一个节点开始逐一寻找。因此，实现GetElem操作获取单链表第i个元素的数据相对麻烦。
1、声明一个节点p指向链表的第一个节点，并从1开始初始化j；
2.当j
3、如果链表末尾p为空，则说明第i个元素不存在；
4. 否则，如果查找成功，则返回节点p的数据。
(3)插入元素
我们先来看一下单链表的插入。假设存储元素e的节点为s。要实现节点p、p-next、s之间逻辑关系的改变，可以参考下图来思考：
想了想，我们发现根本不需要打扰其他节点，只需要对s-next和p-next的指针做一点小小的改变即可。
s-下一个=p-下一个；
p-下一个=s;
我们通过图片来解读这两个代码。
那么我们来考虑一下大多数初学者最容易搞砸的问题：这两行代码的顺序可以调换一下吗？第一个p-下一个=s；那么s-下一个=p-下一个；
你注意到了吗？如果先执行p-next，就会先覆盖到s的地址，那么s-next=p-next实际上就等于s-next=s。因此，这两句话在任何情况下都不能颠倒。初学者一定要注意这一点~
主意：
1、声明一个节点p指向链表的头节点，并从1开始初始化j；
2、当j1时，遍历链表，将p的指针向后移动，继续指向下一个节点，j累加1；
3、如果链表末尾p为空，则说明第i个元素不存在；
4、否则，查找成功，系统中生成空节点s；
5、将数据元素e赋值给s-data；
6、将两条标准语句插入到单链表中；
7.返回成功。
(4)删除元素
现在我们来看一下单链表的删除操作。
假设元素a2的节点是q。要实现删除节点q的单链表的操作，实际上就是绕过其前驱节点的指针，指向后继节点。那么我们要做的其实就是一步：
它可以是这样的：p-next=p-next-next;也可以是这样的：q=p-next； p-下一个=q-下一个。
主意：
1、声明节点p指向链表的第一个节点，并初始化j=1；
2、当j1时，遍历链表，让P的指针向后移动，继续指向下一个节点，j累加1；
3、如果链表末尾p为空，则说明第i个元素不存在；
4、否则，如果查找成功，则将要删除的节点p-next赋值给q；
5、删除单链表的标准语句是p-next=q-next；
6、将节点q中的数据赋值给e作为返回；
7. 释放q 节点。
1.2.1.2 单链表的整表建立
对于顺序存储结构的线性表的整个建表，我们可以通过数组的初始化来直观的理解。
单链表与顺序存储结构不同。它不像顺序存储结构那样集中。它的数据可以分散在内存的各个角落，而且它的增长也是动态的。对于每个链表，其所占用空间的大小和位置不需要提前分配，可以根据系统情况和实际需要即时生成。
创建单链表的过程就是动态生成链表的过程。从“空链表”的初始状态开始，依次建立各个元素节点，并将其一一插入到链表中。
主意：
1.声明一个节点p和计数器变量i；
2、初始化一个空链表L；
3、让L的头结点的指针指向NULL，即以头结点创建单链表；
4、循环实现后续节点的赋值和插入。
(1)头插入方法建立
头插入法从空链表开始，生成一个新节点，读取数据存入新节点的data域，然后将新节点插入到当前链表的头部，直到链表末尾。简单来说，就是将新添加的元素放在header之后的第一个位置：先让新节点的next指向头节点之后，然后让header的next指向新节点。
(2)尾部插入方法的建立
虽然头插入法是创建链表的简单算法，但生成的链表中节点的顺序与输入的顺序相反。就像现实社会一样，我们鄙视插队、不遵守纪律的孩子。在编程中，我们不必这样做。我们可以扭转思路：将所有新节点插入到末尾。该算法称为尾部插入。
1.2.1.3 删除整个单链表
当我们不打算使用这个单链表时，就需要销毁它（真的很残忍，别直接给别人就销毁了~）。
其实就是将内存中的它释放出来，留出空间给其他程序或者软件使用。
主意：
1.声明节点p和q；
2.将第一个节点分配给p，将下一个节点分配给q；
3、循环执行释放p并将q赋值给p的操作；
在这个算法代码中，一个常见的错误是有些同学认为不需要q变量。他们只需要写free(p); p=p-下一个；直接在循环体中？
但这世上没有无缘无故的爱。这会带来什么问题呢？
你必须知道p是一个节点。除了数据字段之外，它还有一个指针字段。当我们执行free(p); 时，我们实际上是删除整个节点并释放内存。然后我们删除整个表
需要一个一个地删除节点，所以我们需要q来记录p的下一个节点。
1.2.1.4 优点和缺点
我们从存储分配方式、时间性能、空间性能三个方面进行比较。
(1)存储分配方法
顺序存储结构使用连续的存储单元来顺序存储线性表的数据元素。
单链表采用链式存储结构，使用一组任意存储单元来存储线性表的元素。
(2)时间表现
搜索：顺序存储结构O(1)，单链表O(n)
插入和删除：
顺序存储结构平均需要移动链表长度的一半，需要O(n) 时间。
计算出单链表中某个位置的指针后，插入和删除时间仅为O(1)
(3)空间性能
顺序存储结构需要预先分配存储空间。如果分配量很大，很容易造成空间浪费。如果分配量很小，很容易发生溢出。
单链表不需要分配存储空间，只要存在就可以分配，并且元素数量不受限制。
总而言之，
如果线性表需要频繁的查找和很少的插入、删除操作，则应使用顺序存储结构。
如果需要频繁插入和删除，则应使用单链表结构。
例如，在游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，大部分时间都是读取的，所以应该考虑使用顺序存储结构。
玩家在游戏中的武器或装备列表可以在玩家玩游戏时随时添加或删除。这时不适合使用顺序存储，可以使用单链表结构。
当线性表的元素数量变化较大或者根本不知道大小时，最好采用单链表结构，这样就不需要考虑存储空间的大小了。
而如果提前知道线性表的大概长度，比如一年有12个月，一周有7天从周一到周日，这种顺序存储结构会高效很多。
1.2.2 静态链表
用数组描述的链表称为静态链表，这种描述方法称为游标实现方法。
1.2.2.1 定义静态链表
我们对数组的第一个和最后一个元素进行特殊处理，它们的数据不存储数据。我们通常将未使用的数组元素称为备用链表。数组的第一个元素，即下标为0的元素的cur，存储的是备份链表第一个节点的下标。数组的最后一个元素，即下标为MAXSIZE-1的cur，存储的是第一个有值元素的下标，相当于单链表中的头节点。
1.2.2.2 插入
1.2.2.3 删除
回收空闲光标。
1.2.2.4 优点和缺点
优势：
插入和删除操作时，只需要修改光标，不需要移动元素，从而改善了顺序存储结构中插入和删除操作需要移动大量元素的缺点。
缺点：
没有解决连续存储分配（数组）带来的表长度难以确定的问题。
顺序存储结构的随机存取特性丢失。
总的来说，静态链表实际上是为没有指针的编程语言设计的一种方法，用来实现单链表的功能。
虽然我们可以使用单链表来代替静态链表，但是这种思维方式非常巧妙，你应该理解它的思想，以备不时之需。
1.2.2.5 单链表面试题
题目：快速找到长度未知的单链表的中间节点。
既然是面试题，就要有普通方法和高级方法。
普通的方法很简单，首先遍历单链表，确定单链表的长度L。然后再次从头节点开始，循环L/2次，找到单链表的中间节点。
算法复杂度为：O(L+L/2)=O(3L/2)。
进阶方法：使用快指针和慢指针！
利用快慢指针的原理：设置两个指针*search和*mid指向单链表的头节点。 *search的移动速度是*mid的2倍。当*search指向结束节点时，mid正好在中间。这也是统治者的想法。
1.2.3 循环链表
对于单链表，由于每个节点只存储一个向后指针，因此当到达尾标记时，向后链接操作停止。也就是说，这样只能索引后继节点，而不能索引前驱节点。这会导致什么问题？例如，不从头节点开始就不可能访问所有节点。
其实解决这个问题并不麻烦。只需要将单链表中终端节点的指针从空指针改为指向头节点，问题就解决了。将单链表中终端节点的指针尾由空指针改为指向头节点，使得整个单链表形成一个环。这种首尾相连的单链表就成为单循环链表，简称循环链表。
注意：这并不意味着循环链表必须有头节点。
其实循环链表和单链表的主要区别在于判断空链表的条件。原来是判断head-next是否为null，现在是判断head-next是否等于head。回到上一个问题，由于终端节点是由尾指针rear指示的，所以查找终端节点是O(1)，起始节点是rear-next-next，当然是O(1) 。
1.2.3 带环单链表
循环的定义是链表的尾节点指向链表中的某个节点。
所以判断单链表是否存在环路，主要有两种方法：
方法一：使用两个指针p和q。 P总是向前移动，但q每次都从头开始。对于每个节点，检查p 所采取的步数是否与q 相同。如图所示，当p从6到3时，需要6步。此时如果q从head开始，只需要两步就可以到达3，因此步数不相等，存在矛盾，存在循环。
方法2：使用两个指针p和q。 p每次前进一步，q每次前进两步。如果在某个时刻p==q，则存在循环。
1.2.4 双向链表
众所周知，一切在早期阶段都显得不完美。举个例子，我们的火车刚发明的时候，它只有一个“头”，所以如果它所走的路线是这样的：
A-B-C-D-E-F-G-H-I-J-K-L-A
假设此时火车停在K处，要求将一批货物发往J处，则其行驶路线为：
K-L-A-B-C-D-E-F-G-H-I-J
嗯，所以后来我们的火车都是两个头的。看完这个例子，大家就会明白双向链表的必要性了。
1.2.4.1 建立双向链表
1.2.4.2 插入
1.2.4.3 删除
1.2.4 双向循环链表
2.堆栈
官方定义：栈是一个后进先出（LIFO）线性表，只需要在表尾进行删除和插入操作。
小乌龟定义：所谓栈其实是一种特殊的线性表（顺序表、链表），但它在操作上有一些特殊的要求和限制：栈中的元素必须是“后进先出”。堆栈操作只能在该线性列表的末尾执行。
注：对于栈来说，表尾称为栈顶，对应的表头称为栈底。
栈的插入操作（Push）称为入栈，也称入栈或入栈。类似于将子弹装入弹匣的动作。
栈的删除操作（Pop）称为出栈，也称为出栈。就像杂志上的子弹弹出夹一样。
2.1 栈的顺序存储结构
因为栈的本质是一个线性表，而线性表有两种存储形式，所以栈也分为栈的顺序存储结构和栈的链式存储结构。初始栈不包含任何数据，称为空栈。此时，栈顶就是栈底。然后数据从栈顶进入，栈顶和栈底分离，整个栈当前容量变大。当数据从栈中弹出时，栈顶向下移动，整个栈的当前容量变小。
压入操作： 压入操作也称为入栈操作，是将数据存储到堆栈上。
入栈操作必须在栈顶进行。每压入一条数据，栈顶指针就会+1，直到栈满。
出栈操作： 出栈操作是从栈顶取出数据并使栈顶指针相应下移的操作。
每当从堆栈中弹出一条数据时，堆栈的当前容量为-1。
2.1.1 清空栈
所谓清栈，是指栈中的所有元素都失效，但栈本身的物理空间不改变（不被破坏）。因此，我们只需要将s-top的内容赋值给s-base，使s-base等于s-top，即表示栈为空。这个原理和高级格式化一样，只是简单的清除了文件列表，并没有覆盖硬盘。
2.1.2 销毁栈
销毁堆栈与清除堆栈不同。销毁堆栈就是释放堆栈占用的物理内存空间。因此，不要混淆销毁堆栈和清除堆栈这两个操作。
2.1.3 计算栈的当前容量
计算栈当前容量也就是计算栈中元素的个数，所以直接返回s.top-s.base即可。
注意，栈的最大容量是指栈占用的内存空间的大小。它的值是s.stackSize，和栈的当前容量不是一个概念。
2.2 栈链式存储结构
现在我们来看看栈的链式存储结构，简称栈链。 （通常我们使用栈的顺序存储结构来存储，我们把链式存储当作一个知识点，所以大家都知道！）
因为栈只是进行插入和删除操作的栈顶，所以更好的方法是将栈顶放在单向链表的头部，栈顶指针和单向链表的头指针链表合并为一个。
2.2.1 建立栈
2.2.2 进栈
2.2.3 出栈
3. 队列
队列是一种线性表，只能在一端进行插入操作，在另一端进行删除操作。
与堆栈相反，队列是先进先出(FIFO) 线性列表。
和栈一样，队列也是一种重要的线性结构。实现队列还需要序列表或链表作为基础。
3.1 队列的链式存储结构
队列可以使用链表或序列表来实现。与栈相反，栈一般使用序列表来实现，而队列则常常使用链表来实现，简称链表。
3.1.1 建立队列
我们将队列的头指针指向链队列的头节点，队列的尾指针指向终端节点。 （注：头节点不是必须的，但我们为了方便操作而添加了它。）
当队列为空时，front和rear都指向头节点。
3.1.2 入队列
3.1.3 出队列
出队操作是移除队列中的第一个元素。队列的头指针不变。只需更改头节点的next指针即可。出队操作流程如下：
如果原来的队列只有一个元素，那么我们应该处理队列的尾指针。
3.1.4 销毁队列
由于链式队列是建立在内存动态区域的，当某个队列不再有用时，应该及时销毁，避免占用过多的内存空间。
3.2 队列的顺序存储结构
我们先考虑如何按照合适的思路来构造队列的顺序存储结构，然后再发现我们遇到了哪些麻烦。
我们假设队列有n 个元素。顺序存储队列需要创建一个大于n的存储单元，并将队列的所有元素存储在数组的前n个单元中。索引为0 的数组末尾是队列的头部。
队列操作实际上就是将一个元素追加到队列尾部，不做任何移动，时间复杂度为O(1)。
出队则不同，因为我们将索引为0的位置设置为队列的头部，因此每次出队操作所有元素都必须向前移动。
现实中也是如此。一群人正在排队买火车票。前面的人已经买好票离开了，后面的人也得上前填补空位。然而，我们研究数据结构和算法的根本目的之一是找到提高程序效率的方法。按照刚才的方法，出队的时间复杂度是O(n)，大大降低了效率！
如果我们不限制队列头位于下标0的位置，那么出队操作不需要移动所有元素。
但是，也会出现一些问题。例如，如果继续如下所示排队，就会出现数组越界错误。
3.2.1 循环队列
解决假溢出的方法是如果后面满了就重新从头开始，即头尾循环。
循环队列的容量是固定的，它的头指针和尾指针可以随着元素进入和退出队列而改变。这样，循环队列在逻辑上就相当于一个循环存储空间。但需要注意的是，在实际内存中，并不存在真正的循环存储区域。我们只是用一个序列表来模拟一个逻辑循环。
于是我们发现，循环队列的实现似乎只需要灵活改变front和rear指针即可。
也就是说前或后指针连续加1，即使超出地址范围也会自动从头开始。我们可以使用取模运算来处理：
(后+1) % 队列大小
(前面+1) % 队列大小
OK，本文到此结束，希望对大家有所帮助。
【深入探讨：数据结构中的线性结构原理与应用】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
数据结构学起来真有趣！线性结构是基础啊。
有13位网友表示赞同！
我要学习一下线性结构的应用场景在哪儿？
有14位网友表示赞同！
这篇文章写的挺清楚的，帮我理解了线性结构的基本概念。
有16位网友表示赞同！
栈和队列这两个数据结构听起来很有趣，好像经常在现实生活中用到。
有6位网友表示赞同！
想把学习的数据结构知识运用到编程中去，线性结构是个好起点哦！
有18位网友表示赞同！
线性结构的比较效率也是很重要的一点吧？
有20位网友表示赞同！
感觉线性结构应用场景还挺宽泛的，比如排序算法就需要用到。
有14位网友表示赞同！
学习了线性结构之后，是不是就能更好地理解其他数据结构了？
有17位网友表示赞同！
对线性结构的概念还是挺感兴趣的，不过实际编程中怎么实现呢？
有15位网友表示赞同！
这篇文章提到了一些常见的数据结构类型，比如数组、链表和栈等等。
有18位网友表示赞同！
感觉学习数据结构需要打好基础，线性结构是最基本的概念了。
有7位网友表示赞同！
以前没接触过数据结构，现在看到这些内容感觉很有意思。
有18位网友表示赞同！
这个标题很吸引人耶！我想看看这篇文章里具体介绍哪些线性结构。
有20位网友表示赞同！
数据结构之线性结构，听起来像大学要学的课呀！
有8位网友表示赞同！
看来学习数据结构可不是一天两天能搞定的啊，需要慢慢积累
有8位网友表示赞同！
学习数据结构可以提升编程能力？那我一定要好好看看这篇关于线性结构的文章！
有11位网友表示赞同！
数据结构学习起来还是挺挑战的，不过很有趣！
有19位网友表示赞同！