单链表操作之删除
- 格式：pdf
- 大小：130.60 KB
- 文档页数：3
单链表操作之删除
⼀、从开始处删除
从开始处删除，通常可以假设结构中⾄少有⼀个节点。这个操作返回删除项。其形式如下：
# coding: utf-8
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
head = None
for count in range(1,4):
head = Node(count, head)
print head.data, head.next,head
removeItem = head.data
head = head.next
print removeItem
下图记录了删除第1个节点的情况：
该操作使⽤的时间和内存都是常数的，这和数组上相同的操作有所不同。
⼆、从末尾删除
从⼀个数组的末尾删除⼀项（python的pop操作）需要的时间和内存都是常数的，除⾮必须调整数组的⼤⼩。对于单链表来说，从末尾删除的操作假设结构中⾄少有⼀个节点。需要考虑如下的两种情况：
只有⼀个节点。head指针设置为None。
在最后⼀个节点之前没有节点。代码搜索倒数第2个节点并将其next指针设置为None。
在这两种情况下，代码都返回了所删除的节点所包含的数据项。形式如下：
# coding: utf-8
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
head = None
for count in range(1,4):
head = Node(count, head)
print head.data, head.next,head
removeItem = head.data
if head.next is None:
head = Node
else:
probe = head
while probe.next.next != None:
probe = probe.next
removeItem = probe.next.data
probe.next = None
print removeItem
下图展⽰了从拥有3个节点的链表结构中删除最后⼀项的过程。
该操作在时间上和内存上都是线性的。
三、从任意位置删除
从⼀个链表结构中删除第i个项，具有以下三种情况：
i<=0，使⽤删除第1项的代码。
0 i<=n，删除最后⼀个节点。 假设链表结构⾄少有⼀项。这个模式类似插⼊节点所使⽤的模式，因为你必须保证不会超过链表结构的末尾。也就是说，必须允许probe指 针不会超过链表结构的倒数第2个节点。形式如下： # coding: utf-8 class Node(object): def __init__(self, data, next=None): self.data = data self.next = next head = None for count in range(1,4): head = Node(count, head) print head.data, head.next,head index = 2 newItem = 100 if index <= 0 or head.next is None: removeItem = head.data head = head.next print removeItem else: probe = head while index > 1 and probe.next.next != None: probe = probe.next index -= 1 removeItem = probe.next.data probe.next = probe.next.next print removeItem 下图展⽰了包含4项的链表结构中删除位置2的项的过程。 结束！
