Python中的顺序表
Python中的list和tuple两种类型采⽤了顺序表的实现技术，具有前⾯讨论的顺 序表的所有性质。
tuple是不可变类型，即不变的顺序表，因此不⽀持改变其内部状态的任何操 作，⽽其他⽅⾯，则与list的性质类似。
list的基本实现技术
Python标准类型list就是⼀种元素个数可变的线性表，可以加⼊和删除元素， 并在各种操作中维持已有元素的顺序（即保序），⽽且还具有以下⾏为特 征：
基于下标（位置）的⾼效元素访问和更新，时间复杂度应该是O(1)；
为满⾜该特征，应该采⽤顺序表技术，表中元素保存在⼀块连续的存储 区中。
允许任意加⼊元素，⽽且在不断加⼊元素的过程中，表对象的标识（函 数id得到的值）不变。
为满⾜该特征，就必须能更换元素存储区，并且为保证更换存储区时list 对象的标识id不变，只能采⽤分离式实现技术。
在Python的官⽅实现中，list就是⼀种采⽤分离式技术实现的动态顺序表。这 就是为什么⽤list.append(x)        （或        list.insert(len(list),        x)，即尾部插⼊）⽐在指 定位置插⼊元素效率⾼的原因。
在Python的官⽅实现中，list实现采⽤了如下的策略：
       

[AppleScript] 纯文本查看 复制代码

/*	This	over-allocates	proportional	to	the	list	size,	mak ing	room					*	for	additional	growth.		The	over-allocation	is	mild,	b ut	is					*	enough	to	give	linear-time	amortized	behavior	over	a	l ong					*	sequence	of	appends()	in	the	presence	of	a	poorly-perf orming					*	system	realloc().					*	The	growth	pattern	is:		0,	4,	8,	16,	25,	35,	46,	58,	7 2,	88,	...					*/				new_allocated	=	(newsize	>>	3)	+	(newsize	<	9	?	3	:	6);[/size][/font]
[font=微软雅黑][size=3]				/*	check	for	integer	overflow	*/				if	(new_allocated	>	PY_SIZE_MAX	-	newsize)	{								PyErr_NoMemory();								return	-1;				}	else	{								new_allocated	+=	newsize;				}

链表
为什么需要链表
顺序表的构建需要预先知道数据⼤⼩来申请连续的存储空间，⽽在进⾏扩充 时⼜需要进⾏数据的搬迁，所以使⽤起来并不是很灵活。
链表结构可以充分利⽤计算机内存空间，实现灵活的内存动态管理。
链表的定义
链表（Linked        list）是⼀种常⻅的基础数据结构，是⼀种线性表，但是不像顺 序表⼀样连续存储数据，⽽是在每⼀个节点（数据存储单元）⾥存放下⼀个 节点的位置信息（即地址）。


单向链表
单向链表也叫单链表，是链表中最简单的⼀种形式，它的每个节点包含两个 域，⼀个信息域（元素域）和⼀个链接域。这个链接指向链表中的下⼀个节 点，⽽最后⼀个节点的链接域则指向⼀个空值。


表元素域elem⽤来存放具体的数据。 链接域next⽤来存放下⼀个节点的位置（python中的标识） 变量p指向链表的头节点（⾸节点）的位置，从p出发能找到表中的任意 节点。
节点实现

[AppleScript] 纯文本查看 复制代码

class	SingleNode(object):				"""单链表的结点"""				def	__init__(self,item):								#	item存放数据元素								self.item	=	item								#	next是下⼀个节点的标识								self.next	=	None

Python中的顺序表
Python中的list和tuple两种类型采⽤了顺序表的实现技术，具有前⾯讨论的顺 序表的所有性质。
tuple是不可变类型，即不变的顺序表，因此不⽀持改变其内部状态的任何操 作，⽽其他⽅⾯，则与list的性质类似。
list的基本实现技术
Python标准类型list就是⼀种元素个数可变的线性表，可以加⼊和删除元素， 并在各种操作中维持已有元素的顺序（即保序），⽽且还具有以下⾏为特 征：
基于下标（位置）的⾼效元素访问和更新，时间复杂度应该是O(1)；
为满⾜该特征，应该采⽤顺序表技术，表中元素保存在⼀块连续的存储 区中。
允许任意加⼊元素，⽽且在不断加⼊元素的过程中，表对象的标识（函 数id得到的值）不变。
为满⾜该特征，就必须能更换元素存储区，并且为保证更换存储区时list 对象的标识id不变，只能采⽤分离式实现技术。
在Python的官⽅实现中，list就是⼀种采⽤分离式技术实现的动态顺序表。这 就是为什么⽤list.append(x)        （或        list.insert(len(list),        x)，即尾部插⼊）⽐在指 定位置插⼊元素效率⾼的原因。
在Python的官⽅实现中，list实现采⽤了如下的策略：
       

[AppleScript] 纯文本查看 复制代码

/*	This	over-allocates	proportional	to	the	list	size,	mak ing	room					*	for	additional	growth.		The	over-allocation	is	mild,	b ut	is					*	enough	to	give	linear-time	amortized	behavior	over	a	l ong					*	sequence	of	appends()	in	the	presence	of	a	poorly-perf orming					*	system	realloc().					*	The	growth	pattern	is:		0,	4,	8,	16,	25,	35,	46,	58,	7 2,	88,	...					*/				new_allocated	=	(newsize	>>	3)	+	(newsize	<	9	?	3	:	6);[/size][/font]
[font=微软雅黑][size=3]				/*	check	for	integer	overflow	*/				if	(new_allocated	>	PY_SIZE_MAX	-	newsize)	{								PyErr_NoMemory();								return	-1;				}	else	{								new_allocated	+=	newsize;				}

链表
为什么需要链表
顺序表的构建需要预先知道数据⼤⼩来申请连续的存储空间，⽽在进⾏扩充 时⼜需要进⾏数据的搬迁，所以使⽤起来并不是很灵活。
链表结构可以充分利⽤计算机内存空间，实现灵活的内存动态管理。
链表的定义
链表（Linked        list）是⼀种常⻅的基础数据结构，是⼀种线性表，但是不像顺 序表⼀样连续存储数据，⽽是在每⼀个节点（数据存储单元）⾥存放下⼀个 节点的位置信息（即地址）。


单向链表
单向链表也叫单链表，是链表中最简单的⼀种形式，它的每个节点包含两个 域，⼀个信息域（元素域）和⼀个链接域。这个链接指向链表中的下⼀个节 点，⽽最后⼀个节点的链接域则指向⼀个空值。


表元素域elem⽤来存放具体的数据。 链接域next⽤来存放下⼀个节点的位置（python中的标识） 变量p指向链表的头节点（⾸节点）的位置，从p出发能找到表中的任意 节点。
节点实现

[AppleScript] 纯文本查看 复制代码

class	SingleNode(object):				"""单链表的结点"""				def	__init__(self,item):								#	item存放数据元素								self.item	=	item								#	next是下⼀个节点的标识								self.next	=	None