线性表是一种基础且重要的数据结构，它的定义和特点如下：
定义： 线性表（Linear List）是一种数据结构，它是由n（n≥0）个相同数据类型的元素按一定顺序排列组成的有限序列。换句话说，线性表是一个数据元素的集合，这些元素呈线性排列，彼此之间存在着一对一的线性关系。在线性表中，除了第一个元素（如果有）没有前驱，最后一个元素（如果有）没有后继之外，其余每个元素均有且仅有一个直接前驱和一个直接后继。
或许有人想知道，什么是“前驱”，什么是“后继”，这里解释一下：
线性表有如下特点：
举一个例子： 假设你正在整理一份购物清单，清单上的商品按照购买顺序排列：
这个购物清单就是一个线性表。在这个例子中：
进一步想象一下，如果你使用手机APP记录这个购物清单，那么在APP内部，这份清单可能会以数组的形式存储，使得你可以迅速定位到任何一个商品；也可能以链表的形式存储，这样在清单中间插入或删除某个商品时，只需修改相应元素的前后指针即可，无需整体移动其它元素的位置。
存储方式一：顺序表
顺序表（Sequential List）是一种线性数据结构，它在内存中以数组的形式实现，也就是说，它将元素存储在一块连续的内存空间中，元素之间的逻辑顺序与它们在内存中的物理顺序一致。顺序表支持随机访问，即通过下标可以直接访问表中的任一元素，而且在表的末尾插入或删除元素的代价相对较低，但如果在中间位置插入或删除元素，则可能需要移动大量的元素以保持连续性。
这一储存方式也分为两种：静态储存和动态储存。
静态存储： 静态顺序表是在程序编译阶段就确定了存储空间大小的顺序表，通常使用数组来实现。一旦声明了固定长度的数组，它的大小就不能在运行时改变。例如，在C++中，声明一个静态数组时会指定固定的大小：
动态存储： 动态顺序表则是在程序运行过程中动态分配和释放存储空间的顺序表，可以根据需要扩展或收缩存储空间。在C++中，可以使用动态内存分配（如操作符）来实现动态顺序表。例如，使用动态数组（实际上是动态分配的连续内存块）：
当动态顺序表需要增加元素，而现有空间不足时，可以通过重新申请更大的内存空间并将原有数据复制过来的方式来扩展存储空间。在C++标准库中，类模板就提供了动态顺序表的功能，它能够在必要时自动调整其容量。举一个实际的例子：我们需要输入一些二维坐标（事先不确定有多少个），并对这些二维坐标进一步操作，那么输入坐标的过程就可以用到vector：
顺序表的插入算法：
顺序表的删除算法：
以上是顺序表的基本内容。
接下来我们可以来看看链表
链表
链表（Linked List）是一种线性数据结构，其中的元素（节点）通过指针或引用相互连接起来。每个节点通常包含两部分：数据部分和指针部分。数据部分存储有效载荷（payload），即存储的元素值；指针部分则指向下一个节点的位置。链表可以分为多种类型，包括单链表、双链表和循环链表。
链表的特点：
链表与顺序表（数组）的主要区别：
总的来说，链表在需要频繁进行插入和删除操作且对访问速度要求不高时更为合适，而顺序表在需要快速访问元素且元素数量相对稳定时更有优势。
链表有多种类型。我们先来介绍单链表
单链表是一种基础且重要的链式数据结构，它由一系列节点（Node）组成，每个节点包含两部分：数据域（Data）和指针域（Next Pointer）。数据域存储实际数据，而指针域存储指向下一个节点的地址（也称为后继节点）。
单链表的特性：
单链表的操作：
这一行代码是将当前节点（）的后继节点赋值给新节点（）的后继节点指针。这样做是为了保持链表的连续性，即在插入新节点之后，新节点原本应该指向的位置不变，即应该链接到原本的后继节点。
这一行代码是将新节点（）的地址赋值给当前节点（）的后继节点指针。这样就完成了在链表中插入新节点的操作，新节点成为当前节点的后继节点，而原后继节点现在成为了新节点的后继节点。（举一个形象的例子，一群人手拉手从左往右站成一排，然后一个新的人要插进来，那么必须有一个人的左手和下一个人的右手断开，新人的右手（newnode->link）接替左边那个人的右手（current->link）的任务,拉住右边的人的左手；原本左边的人的右手拉着的现在是新人的左手（newnode），因此要把current->link赋值成newnode）
其实只要跳过一个节点，直接指向下一个节点就可以了。
由于本人并非计算机专业，且c++水平不佳，因此或许有所疏漏，请谅解。上面的代码也并非本人所写。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/53769.html