一、定义
二、线性表基本操作
1. 插入
2. 删除
3. 查找
4. 遍历
三、链式存储扩展
四、代码示例
第一章《数据结构与算法是什么？》说过数据结构有四种逻辑结构，线性结构是最基本和最常用的一种，它表示的是线性结构，元素之间存在一对一的关系，数据元素之间按照某种规定存在一个顺序关系。
一、定义
假设有
但很多时候无法知道预先分配多大的空间合适，如果数据量较大时，内存中不存在那么大的连续空间，所以会导致内存分配失败，此时就可以使用链式存储来实现。
链式存储可以使用任何地址的空间存放数据元素，可以空间不连续，它存放的数据结点，里面包含数据元素和指向另一个数据元素的引用（或指针）。
二、线性表基本操作
数据结构包含数据的基本操作，使用不同的存储结构来实现线性表的插入、删除、查找、遍历等基本操作。
1. 插入
初始化一组数据
顺序存储中，定位到
链式存储中，定位到
由此可得链表比顺序表插入的效率高。
顺序存储需要预先分配内存空间，在插入时初始化的空间不够会抛异常。
2. 删除
初始化一组数据
顺序存储中，定位到
链式存储中，定位到
由此可得链表比顺序表删除的效率高。
3. 查找
初始化一组数据
顺序存储中，数据在内存中是连续的，如果已知
在下标未知的情况下，也可以通过遍历来查找。
链式存储中，数据在内存中是无序的，不能通过下标查找，只能通过遍历来查找数据。
而链式存储在遍历的时候，会增加寻址的操作。
由此可得顺序表比链表查找的效率高。
4. 遍历
初始化一组数据
顺序存储中，遍历连续内存空间上的数据元素。
链式存储中，通过地址引用来找到下一个数据元素，来遍历所有数据。
链式存储增加了寻址的操作，所以遍历的效率低于顺序存储。
三、链式存储扩展
前面讲的链式结构实现的线性表都是单向链表，可以增加结点的引用来创建更多的链表结构，比如：双向链表、单向循环链表和双向循环链表等。
四、代码示例
具体的代码实现如下：
Gitee：https://gitee.com/code_artist/DataStructure
GitHub：https://github.com/AiJiangnan/DataStructure
原文始发于微信公众号（CodeArtist）：线性表的定义与实现
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/138035.html
