单链表操作之插入
一、在开始处插入
链表结构存在优于线性操作的几种操作。再某些情况下,这些操作使得链表结构比数组更加合适。第一种情况就是在结构的开始处插入一项。如下:
# 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,6): head = Node(count, head) print head.data, head.next,head newItem = 100 head = Node(newItem, head)
下图记录了这个操作的两种情况。在第一种情况下,head指针是None,因此向结构中插入了第1项。第2种情况下,将第2项插入到了同一结构的开头处。
注意第2种情况,不需要复制数据并向下移动,并且不需要额外的内存。这意味着,在一个链表结构的开始处插入数据,时间和内存都是常数,这与数组的响应操作有所不同。
二、在行尾插入
在一个数组的行尾插入一项(python的oppend操作)需要的时间和内存都是常数,除非必须调整数组大小。对于单链表来说,在行尾插入一项必须考虑如下两种情况:
- head指针为None,此时,将head指针设置为新的节点。
- head指针不为None,此时,代码将搜索最后一个节点,并将其next指针指向新的节点。
第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): # 为了尽量减少下图的步骤,此处创建有3个节点的单链表 head = Node(count, head) print head.data, head.next,head newItem = 100 newNode = Node(newItem) if head is None: head = newNode else: probe = head while probe.next != None: probe = probe.next probe.next = newNode while head.next: head = head.next print head.data
这样就在head链表末尾插入一个新的链接。该操作在时间上是线性的,在空间是是常数的。
结束!