---

2-1 顺序表

---

目录

小节	位置
2.1.1	线性表的概念
2.1.2	顺序表
2.1.3	Python中的顺序表
2.1.4	Python中list内置操作的时间复杂度

2.1.1 线性表的概念

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素构成的有限序列，其中的元素的前驱和后置都最多只有一个。
线性表是最基本、最简单、也是最常用的一种数据结构。我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以常见的线性表包括：顺序表、栈和队列、链表。
线性表通常都具有：初始化、遍历、求长度和增删改查这些操作。

2.1.2 顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储区域，将数据元素顺序地存储在其中，就形成一个顺序表。
元素间的顺序关系由它们的存储顺序自然的表示。

顺序表的两种形式如图所示；
a) 是直接存储元素，这就要求元素的类型相同了，因为不同类型的元素占据的字节数是不一样的；
b) 是存储的地址，地址指向的是一些元素，由于地址本身这个类型（比如C++中的指针类型）占据的字节是固定的，所以可以存在顺序表中，这些地址指向的具体的位置，存放的元素又可以是不同的类型。

2.1.3 Python中的顺序表

Python标准类型list（列表，就是一种线性表。但是比较特殊，它是一种元素个数可变的线性表。这种顺序表被称为【动态顺序表】，因其容量可以在使用过程中动态变化。

'''执行以下code，你会发现list中相同的数:1, 竟然指向的是同一个地址
这就跟C/C++的传统印象有区别'''
nums = [1,1,0,1,2]
for i in range(len(nums)):
    print(id(nums[i]))

nums[0]=100
print('#'*14)
for i in range(len(nums)):
    print(id(nums[i]))
##### output ######
'''
1638490073392
1638490073392
1638490073360
1638490073392
1638490073424
##############
1638490265040
1638490073392
1638490073360
1638490073392
1638490073424
'''

Python 中的 list 的是一种 采用分离式技术实现的动态顺序表 ，在建立空列表的时候，系统分配一块能容纳8个元素的存储区；在执行插入操作时(insert/append)，如果元素存储区满了，就换一块4倍大的存储区。但是如果当list的规模已经较大时，（目前阈值为50000），就换一块2倍大的存储区，避免出现过多的空闲存储位置。
Python 中的另一个顺序表，就是 tuple（元组），元组就不可以改变值了。

2.1.4 Python中list内置操作的时间复杂度

操作	时间复杂度	举例
a[ ]	O(1)	a[1]
pop()	O(1)	a.pop()
pop(i)	O(N)	a.pop(0)
insert(i,item)	O(N)	a.insert(3,100)
del	O(N)	del a[3]
len	O(N)	len(a)
iteration	O(N)	for x in a: print x
contains(in)	O(N)	3 in a
get slice[x:y]	O(k)	a[3:7]
del slice	O(N)	del a[3:7]
set slice	O(k+N)	a[3:7]=[3,4,5,6]
reverse	O(N)	a.reverse()
concatenate	O(k)	[1, 2, 3] + [4, 5, 6]
sort	O(nlogN)	a.sort()
multiply	O(kN)	[‘Hi!’] * 4