链表与顺序表的对⽐
链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空 间开销⽐较⼤，但对存储空间的使⽤要相对灵活。
链表与顺序表的各种操作复杂度如下所示：

注意虽然表⾯看起来复杂度都是        O(n)，但是链表和顺序表在插⼊和删除时进 ⾏的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插⼊操作 本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷⻉覆盖。因为 除了⽬标元素在尾部的特殊情况，顺序表进⾏插⼊和删除时需要对操作点之 后的所有元素进⾏前后移位操作，只能通过拷⻉和覆盖的⽅法进⾏。

双向链表
⼀种更复杂的链表是“双向链表”或“双⾯链表”。每个节点有两个链接：⼀个指 向前⼀个节点，当此节点为第⼀个节点时，指向空值；⽽另⼀个指向下⼀个 节点，当此节点为最后⼀个节点时，指向空值。


操作
is_empty()        链表是否为空 length()        链表⻓度 travel()        遍历链表 add(item)        链表头部添加 append(item)        链表尾部添加 insert(pos,        item)        指定位置添加 remove(item)        删除节点 search(item)        查找节点是否存在

实现

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

class	Node(object):				"""双向链表节点"""				def	__init__(self,	item):								self.item	=	item								self.next	=	None								self.prev	=	None
class	DLinkList(object):				"""双向链表"""				def	__init__(self):								self.__head	=	None
				def	is_empty(self):								"""判断链表是否为空"""								return	self.__head	==	None
				def	length(self):								"""返回链表的⻓度"""								cur	=	self.__head								count	=	0								while	cur	!=	None:												count	+=	1												cur	=	cur.next								return	count
				def	travel(self):								"""遍历链表"""								cur	=	self.__head								while	cur	!=	None:												print	cur.item,												cur	=	cur.next								print	""
				def	add(self,	item):								"""头部插⼊元素"""								node	=	Node(item)								if	self.is_empty():												#	如果是空链表，将_head指向node												self.__head	=	node								else:												#	将node的next指向_head的头节点												node.next	=	self.__head												#	将_head的头节点的prev指向node
	self.__head.prev	=	node												#	将_head	指向node												self.__head	=	node
				def	append(self,	item):								"""尾部插⼊元素"""								node	=	Node(item)								if	self.is_empty():												#	如果是空链表，将_head指向node												self.__head	=	node								else:												#	移动到链表尾部												cur	=	self.__head												while	cur.next	!=	None:																cur	=	cur.next												#	将尾节点cur的next指向node												cur.next	=	node												#	将node的prev指向cur												node.prev	=	cur
				def	search(self,	item):								"""查找元素是否存在"""								cur	=	self.__head								while	cur	!=	None:												if	cur.item	==	item:																return	True												cur	=	cur.next								return	False

链表与顺序表的对⽐
链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空 间开销⽐较⼤，但对存储空间的使⽤要相对灵活。
链表与顺序表的各种操作复杂度如下所示：

注意虽然表⾯看起来复杂度都是        O(n)，但是链表和顺序表在插⼊和删除时进 ⾏的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插⼊操作 本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷⻉覆盖。因为 除了⽬标元素在尾部的特殊情况，顺序表进⾏插⼊和删除时需要对操作点之 后的所有元素进⾏前后移位操作，只能通过拷⻉和覆盖的⽅法进⾏。

双向链表
⼀种更复杂的链表是“双向链表”或“双⾯链表”。每个节点有两个链接：⼀个指 向前⼀个节点，当此节点为第⼀个节点时，指向空值；⽽另⼀个指向下⼀个 节点，当此节点为最后⼀个节点时，指向空值。


操作
is_empty()        链表是否为空 length()        链表⻓度 travel()        遍历链表 add(item)        链表头部添加 append(item)        链表尾部添加 insert(pos,        item)        指定位置添加 remove(item)        删除节点 search(item)        查找节点是否存在

实现

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

class	Node(object):				"""双向链表节点"""				def	__init__(self,	item):								self.item	=	item								self.next	=	None								self.prev	=	None
class	DLinkList(object):				"""双向链表"""				def	__init__(self):								self.__head	=	None
				def	is_empty(self):								"""判断链表是否为空"""								return	self.__head	==	None
				def	length(self):								"""返回链表的⻓度"""								cur	=	self.__head								count	=	0								while	cur	!=	None:												count	+=	1												cur	=	cur.next								return	count
				def	travel(self):								"""遍历链表"""								cur	=	self.__head								while	cur	!=	None:												print	cur.item,												cur	=	cur.next								print	""
				def	add(self,	item):								"""头部插⼊元素"""								node	=	Node(item)								if	self.is_empty():												#	如果是空链表，将_head指向node												self.__head	=	node								else:												#	将node的next指向_head的头节点												node.next	=	self.__head												#	将_head的头节点的prev指向node
	self.__head.prev	=	node												#	将_head	指向node												self.__head	=	node
				def	append(self,	item):								"""尾部插⼊元素"""								node	=	Node(item)								if	self.is_empty():												#	如果是空链表，将_head指向node												self.__head	=	node								else:												#	移动到链表尾部												cur	=	self.__head												while	cur.next	!=	None:																cur	=	cur.next												#	将尾节点cur的next指向node												cur.next	=	node												#	将node的prev指向cur												node.prev	=	cur
				def	search(self,	item):								"""查找元素是否存在"""								cur	=	self.__head								while	cur	!=	None:												if	cur.item	==	item:																return	True												cur	=	cur.next								return	False