线性表是由n≥0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。
线性表上定义的基本运算：·构造空表：Initlist(L)
·求表长：Listlength(L)
·取结点：GetNode(L,i)
·查找：LocateNode(L,x)·插入：InsertList(L,x,i)
·删除：Delete(L,i)
顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算：LOCa(i)=LOCa(1)+(i-1)*d；（首地址为1）
在顺序表中实现的基本运算： ·插入：平均移动结点次数为n/2；平均时间复杂度均为O(n)。
·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O(n)。
线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。 一个单链表由头指针的名字来命名。
单链表运算：·建立单链表·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。
·尾插法：head=rear=null；if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n)
·加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。
·查找·按序号：与查找位置有关，平均时间复杂度均为O(n)。
·按值：与输入实例有关，平均时间复杂度均为O(n)。
·插入运算：p=GetNode(L,i-1)；s->next=p->next；p->next=s；平均时间复杂度均为O(n)
·删除运算：p=GetNode(L,i-1)；r=p->next；p->next=r->next；free(r)；平均时间复杂度均为O(n)
单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表。
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针head惟一确定。
双链表也可以头尾相链接构成双(向)循环链表。
双链表上的插入和删除时间复杂度均为O (1)。
顺序表和链表的比较：·基于空间： ·顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。
·链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用。
·基于时间： ·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储结构。
·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。
⊙小编提示：添加【山东自考网】招生老师微信，即可了解2023年山东自考政策资讯、自考报名流程、准考证打印方法、成绩查询时间以及领取历年真题资料、个人专属备考方案等相关信息！
（添加“山东自考网”招生老师微信，在线咨询报名报考等相关问题）
《山东自考网》免责声明：
（一）由于考试政策等各方面情况的不断调整与变化，本网站所提供的考试信息仅供参考，请以省考试院及院校官方发布公布的正式信息为准。
（二）本站文章内容信息来源出处标注为其他平台的稿件均为转载稿，免费转载出于非商业性学习目的，版权归原作者所有。如您对内容、版权等问题存在异议请与本站联系，我们会及时进行处理解决，联系邮箱：812379481@qq.com。
