幫助Python中的循環鏈表使用

Question

我正在嘗試製作一個單獨的鏈表。我希望能夠修改我單獨的列表的代碼，但我遇到了一些麻煩。

對於我的聯繫名單上有：

class Link (object): 
    def __init__ (self, data, next = None): 
    self.data = data 
    self.next = next 


class LinkedList(object): 
    def __init__(self): 
    self.first = None 

    def __str__(self): 
    a = "[" 
    current = self.first 
    while current != None: 
     a += str(current.data) + ', ' 
     current = current.next 
    a = a[:-2] + ']' 
    return a 

    def __iter__(self): 
    current = self.first 
    a = [] 
    while current != None: 
     a += [current.data] 
     current = current.next 
    return iter(a) 

    def __len__ (self): 
    current = self.first 
    a = [] 
    while current != None: 
     a += [current.data] 
     current = current.next 
    return len(a) 

    def InsertFirst(self, item): 
    NewLink = Link(item, self.first) 
    self.first = NewLink 

    def InsertLast(self, item): 
    NewLink = Link(item) 
    current = self.first 

    if current == None: 
     self.first = NewLink 
     return 

    while current.next != None: 
     current = current.next 
    current.next = NewLink 

    def Search(self, item): 
    count = 0 
    current = self.first 
    while current != None: 
     count += 1 
     if current.data == item: 
     return count 
     else: 
     pass 
     current = current.next 
    return -1 

    def Delete(self, item): 
    current = self.first 
    previous = self.first 

    if (current == None): 
     return None 

    while (current.data != item): 
     if (current.next == None): 
     return None 
     else: 
     previous = current 
     current = current.next 

    if (current == self.first): 
     self.first = self.first.next 
    else: 
     previous.next = current.next 

    return current 

到目前爲止我圓名單上有：

class Link (object): 
    def __init__ (self, data, next = None): 
    self.data = data 
    self.next = next 


class CircularList(object): 
    def __init__(self): 
    self.first = Link(None, None) 
    self.head = Link(None, self.first) 

    def __str__(self): 
    a = "[" 
    current = self.first 
    while current != None: 
     a += str(current.data) + ', ' 
     current = current.next 
    a = a[:-2] + ']' 
    return a 

    def InsertLast(self, item): 
    NewLink = Link(item) 
    current = self.first 

    if current == None: 
     self.first = NewLink 
     return 

    while current.next != None: 
     current = current.next 
    current.next = Link(item) 

我的問題是如何鏈接的最後一個元素返回到第一，所以我可以橫向嗎？

Answer 1

圓形鏈表的要點是跳過所有的「if next is not None」邏輯。頭一開始，頭指向自己，表明列表是空的。沒有必要創建一個空的「第一次」 - 在最開始做的：

self.head = Link(None, None) 
self.head.next = self.head 

然後到其他節點後插入一個節點，你只是做：

def insert_after(insert_node, after_node): 
    insert_node.next = after_node.next 
    after_node.next = insert_node 

要插入的列表中的開始，做：

insert_after(node, head) 

插入需要迭代節點「之前」找到之前，由於該表僅是單向鏈接：

def insert_before(node, before_node): 
    loc = head 
    while loc.next != before_node: 
     loc = loc.next 
    insert_after(insert_node, loc) 

要插入在列表的末尾，這樣做：

insert_before(node, head) 

以獲取列表中的所有元素做：

current = self.head.next 
while current != self.head: 
    # do something with current.data 

    # advance to next element 
    current = current.next 

但是，在一個圓形的列表中真正的力量是使它雙重鏈接，所以你可以插入之前沒有迭代。

Answer 2

last.next =創建時第一個？

class Link (object): 
    def __init__ (self, data, next = None): 
    self.data = data 
    self.next = self.first 

可能不是有效的代碼。但是由於你保證在創建時位於列表的最後部分，所以你也可以。

Answer 3

class cirlist(list): 
    def __init__(self,*arg): 
     super(cirlist,self).__init__(*arg) 
     self.m=super(cirlist,self).__getitem__(0) 
     self.Index=0 
    def next(self): 
     if self.Index>=super(cirlist,self).__len__()-1: 
      self.m=super(cirlist,self).__getitem__(0) 
     else: 
      self.m=super(cirlist,self).__getitem__(self.Index+1) 
     if self.Index>super(cirlist,self).__len__()-1:  
      self.Index=super(cirlist,self).index(self.m)+1 
     else: 
      self.Index=super(cirlist,self).index(self.m) 
     return self.m 

Answer 4

class Link (object): 

def __init__(self, first=None, rest=None): 
    self.first = first 
    self.rest = rest 
def get_data(self): 
    return self.first 
def get_next(self): 
    return self.rest 
def __getitem__(self, i): 
    if i == 0: 
     return self.first 
    get = self 
    while i > 0: 
     get = get.rest 
     i -= 1 
    if get == None: 
     raise IndexError('The Sentence Index is Out of Range.') 
    return get.first 

類Circular_Link（對象）：

def __init__(self, things): 
    assert len(things) > 2 
    last = Link(things[len(things)-1]) 
    first = Link(things[len(things)-2], last) 
    index = len(things)-2 
    while index > 0: 
     index -= 1 
     first = Link(things[index], first) 
    last.rest = first 
    self.circle = first 
def __getitem__(self, i): 
    return self.circle[i] 

此示例初始化從正常列表中循環鏈表。