循环链表结构

在单链表结构上，在第1个节点插入和删除，只不过是第i个节点的插入和删除的特殊情况。这些情况只所以特殊，是因为head指针必须重置。可以使用一个带有哑头节点循环链表结构来简化这些操作。循环链表结构包含了从结构中的最后一个节点返回到第一个节点的链接。在这个实现中，至少总是有一个节点。这个节点也就是哑头节点（dummy header node），它不包含数据，但是充当了链表结构的开头和结尾的一个标记。一开始的时候，在空的链表结构中，head指针指向了哑头节点，且哑头节点的next指针指回到了哑头节点自身，结构如下图所示：

第一个包含了数据的节点。位于哑头节点之后。这个节点的next指针以循环的方式，指回了哑头节点，如下图所示：

对第i个节点的搜索，从哑头节点之后的节点开始。假设这个空的链表的最初结构如下所示：

# coding: utf-8
class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

head = Node(None, None)
head.next = head

如下是第i个位置插入节点的代码，它使用了这个链表结构的新的表示：

# coding: utf-8
class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


head = Node(None, None)
head.next = head

for i in range(1,10):
    head = Node(i, head)


probe = head
index =5
newItem = 100
while index > 0 and probe.next != head:
    probe = probe.next
    print probe.next,probe.data
    index -= 1
probe.next = Node(newItem, probe.next)
print probe.next.next,probe.next.data

这种实现的优点在于，插入和删除操作只需要考虑一种情况，即第i个节点位于当前的第i个节点和它的前一个节点之间的这种情况。当第i个节点是第1个节点的时候，它之前的节点就是头节点。当i>=n，之前的节点就是最后一个节点，并且头节点是其下一个节点。

结束！