赞
踩
链表是由一系列节点组成的元素集合。每个节点包含两部分,数据域item和指向下一个节点的指针next。通过节点之间的相互连接,最终串联成一个链表。
单链表如下图所示:
单链表中的结点类型描述如下:
class Node:
def __init__(self, item):
self.item = item
self.next = None
头插法从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的头部,即头结点之后。
如下图所示:
代码如下:
def create_linklist_head(li):
head = Node(li[0])
for element in li[1:]:
node = Node(element)
node.next = head
head = node
return head
头插法建立单链表的算法虽然简单,但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致,可采用尾插法。尾插法将新结点插入到当前链表的表尾,为此必须增加一个尾指针,使其始终指向当前链表的尾结点。
如下图所示:
代码如下:
def create_linklist_tail(li):
head = Node(li[0])
tail = head
for element in li[1:]:
node = Node(element)
tail.next = node
tail = node
return head
插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性,然后找到待插入位置的前驱结点,即第 i - 1 个结点,再在其后插入新结点。
如下图所示:
代码如下:
p.next = curNode.next
curNode.next = p
删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性,后查找表中第i-1 个结点,即被删除结点的前驱结点,再将其删除。
如下图所示:
代码如下:
p = curNode.next
curNode.next = curNode.next.next
del p
单链表中只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点时,只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。
为了克服单链表的上述缺点,引入了双链表,双链表结点中有两个指针 prior 和 next,分别指向其前驱结点和后继结点。
双链表中的结点类型描述如下:
class Node(object):
def __init__(self,item=None):
self.item = item
self.next = None
self.prior = None
在双链表当前结点后插入结点p,如下图所示:
代码如下:
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p
删除双链表中当前结点的后继结点p,如下图所示:
代码如下:
p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。