线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示 也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequent ial List
)_{\circ}其特点是, 逻辑上相邻的数据元素，其物理次序也是相邻的。假设线性表的每个元素需占用
l个存储单元，并以所占的第一个单元的存储地址作为数据元 素的存储起始位置。则线性表中第
i+1个数据元素的存储位置
\operatorname{LOC}\left(a_{i+1}\right)和第
i个数据元素的存 储位置 LOC
\left(a_{i}\right)之间满足下列关系：
\operatorname{LOC}\left(a_{i+1}\right)=\operatorname{LOC}(a_{i})+l一般来说，线性表的第
i个数据元素
a_{i}的存储位置为：
\operatorname{LOC}(q)=\operatorname{LOC}(q)+(i-1) \times la = [1,2,3,4,4,5]id(a[1])-id(a[0])32id(a[2])-id(a[1])32id(a[0]) + 32*3 == id(a[3])TruePython顺序表中基本操作的实现Python的 list 和 tuple采用了顺序表的实现技术,具有顺序表的所有性质
初始化顺序表的初始化操作就是构造一个空的顺序表。
alist = []取值取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到,elem[i-1]单元存储第i个数据元素。
时间复杂度为\mathrm{O}(1)a[2]3查找查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号;若查找失败，则返回0。
平均时间复杂度为\mathrm{O}(n)a.index(4)3插入线性表的插入操作是指在表的第
i个位置插人一个新的数据元素
e, 使长度为
n的线性表
\left(a_{1}, \cdots, a_{i-1}, a_{i}, \cdots, a_{n}\right)变成长度为
n+1的线性表
\left(a_{1}, \cdots, a_{i-1}, e, a_{i} ;, q\right)一般情况下，在第
i(1 \leqslant i \leqslant n)个位置插入一个 元素时，需从最后一个元素即第
n个元素开始，依次向后移动一个位置，直至第
i个元素（共
n-i+1个元素 )。
顺序表插入算法的平均时间复杂度为
\mathrm{O}(n)_{\circ}Python中有多种方法向表中插入某一元素
a[1, 2, 3, 4, 4, 5]# 在列表尾部添加一个对象# 官方：same as s[len(s):len(s)] = [x]a.append(0)a[1, 2, 3, 4, 4, 5, 0]# 在列表尾部添加一个序列# 官方：same as s[len(s):len(s)] = ta.extend([9])a[1, 2, 3, 4, 4, 5, 0, 9]# 在指定位置插入元素a.insert(2,8)a[1, 2, 8, 3, 4, 4, 5, 0, 9]a.pop(2)8删除线性表的删除操作是指将表的第
\mathrm{i}个元素删去，将长度为
n的线性表
\left(a_{1}, \cdots, a_{i-1}, a_{i}, a_{i+1}, \cdots, a_{n}\right)变成长度为
n-1的线性表
\left(a_{1}, \cdots, a_{i-1}, a_{i+1}, \cdots, a_{n}\right)一般情况下, 删除第
i(1 \leqslant i \leqslant n)个元素时需将第
i+1个至第
n个元素（共
n-i个元素 ) 依次向前移动一个位置
(i=n \text { 时无需移动 })_{\circ}顺序表删除算法的平均时间复杂度为\mathrm{O}(n)# 从a中删除a[i]等于x的第一项a.remove(4)a[1, 2, 8, 3, 4, 5, 0, 9]# 返回i处的元素值，并将其从a中删除a.pop(-1)a[1, 2, 8, 3, 4, 5, 0]list其他操作b = [1,2,3,4,4]len(b)5min(b)1max(b)4b.count(4)25 in bFalse2 in bTrue# 反转b.reverse()b[4, 4, 3, 2, 1]# 删除某几项del b[1:3]b[4, 2, 1]# 清空b.clear()b[]list内置操作的时间复杂度单链表线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单 元可以是连续的，也可以是不连续的
)_{\circ}因此，为了表示每个数据元素
a_{i}与其直接后继数据元素
a_{i+1}之间的逻辑关系，对数据元素
a_{i}来说，除了存储其本身的信息之外，还需存储一个指示其直 接后继的信息（即直接后继的存储位置
)_{\circ}这两部分信息组成数据元素
a_{i}的存储映像，称为结点( node )。它包括两个域：其中存储数据元素信息的域称为数据域; 存储直接后继存储位置的域称 为指针域。指针域中存储的信息称作指针或链。
n个结点（
a_{i}(1 \leqslant i \leqslant n)的存储映像 ) 链结成一 个链表，即为线性表
\left(a_{1}, a_{2}, \cdots, a_{n}\right)示意图
python单链表基本操作的实现单个节点实现class LNode(object):def __init__(self,elem,next = None):self.elem = elemself.next = next单链表的实现单链表的初始化class SingleLinkList(object):def __init__(self):self.__head = None# 头结点的指针域置空判断链表是否为空def is_empty(self):return self.__head == None链表长度def length(self):# p初始时指向头节点p = self.__headcount = 0# 尾节点指向None，当未到达尾部时while p != None:count += 1# 将cur后移一个节点p = p.nextreturn count取值和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样 ，根据给定的 结点位置序号i'在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结 点出发，顺着链域 next 逐个结点向下访问。
单链表取值算法的平均时间复杂度为\mathrm{O}(n)def get_elem(self,i):# p为扫描指针p = self.__headwhile p != None and 0n e x t->n e x t时间复杂度为\mathrm{O}(n)# 按值删除def remove_1(self, elem):cur = self.__headpre = Nonewhile cur != None:if cur.elem == elem:# 先判断此结点是否是头节点# 头节点if cur == self.__head:self.__head = cur.nextelse:pre.next = cur.nextbreakelse:pre = curcur = cur.next# 按位置删除def remove_2(self,i):p = self.__headcount = 0while p != None:if count != i-1:p = p.next count += 1else:p.next = p.next.nextbreak创建单链表头插法(1) 创建一个只有头结点的空链表。
(2) 根据待创建链表包括的元素个数
n, 循环
n次执行以下操作:
生成一个新结点*p;输入元素值赋给新结点*p 的数据域;将新结点*p 插人到头结点之后。尾插法(1) 创建一个只有头结点的空链表。
(2) 尾指针 r 初始化，指向头结点。
(3) 根据创建链表包括的元素个数
n, 循环
n次执行以下操作:
生成一个新结点*p;输入元素值赋给新结点*p 的数据域;将新结点p 插入到尾结点r之后;尾指针 r 指向新的尾结点*p。。# 头插法def add(self, elem):# 先创建一个保存item值的节点node = LNode(elem)# 将新节点的链接域next指向头节点，即__head指向的位置node.next = self.__head# 将链表的头_head指向新节点self.__head = node# 尾插法def append(self, elem):node = LNode(elem)# 先判断链表是否为空，若是空链表，则将_head指向新节点if self.is_empty():self.__head = node# 若不为空，则找到尾部，将尾节点的next指向新节点else:p = self.__headwhile p.next != None:p = p.nextp.next = node顺序表与单链表的对比本文分享自微信公众号 - 数据科学CLUB（jiji8215），作者：少年吉
原文出处及转载信息见文内详细说明，如有侵权，请联系 yunjia_community@tencent.com 删除。
原始发表时间：2021-01-24
本文参与腾讯云自媒体分享计划，欢迎正在阅读的你也加入，一起分享。
https://www.shan-machinery.com