如何创建一个循环链表

Question

我知道如何创建 Link 和 LinearLinkedList 类，但我就是无法将它们修改为创建 circularlinkedlist 。

我已经阅读了此问题的答案。然而，如果 head 是 None ，那么一个 None 类型的对象怎么可能有一个 next 属性呢？我似乎无法理解这个概念。

如果有人能向我展示一个样例 CircularLinkedList 的 __init__ 函数以及简单的解释它如何工作，我认为我就能理解它了。

感谢任何和所有的帮助

编辑：我只需要正向遍历列表。如果是这种情况，逻辑是否需要发生 drastical 变化？

- Colosus__

---

你能为这样一个包含零个、一个、两个等元素的列表画一个图吗？这应该有助于你弄清如何组织事物。此外，问问自己这个列表是否只包含单向链接还是双向链接也包括在内。 - Ulrich Eckhardt

我只需要它们单向连接向前。如果我需要反向遍历，这会产生很大的差异吗？ - Colosus__

对于绘图来说很容易，但是在单向链表上进行一些操作比双向链表更加复杂。 - Ulrich Eckhardt

Answer 1

在循环链表中，通常会有一个不包含实际数据的特殊链接。相反，它是一个“哨兵”，让您知道列表的开始（和结束）位置。即使列表为空，该链接也将存在，因此您的算法将适用于所有列表，而无需大量特殊代码。

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

class CircularLinkedList:
    def __init__(self):
        self.head = Link(None, None) # this is the sentinel node!
        self.head.next = self.head   # link it to itself

    def add(self, data):             # no special case code needed for an empty list
        self.head.next = Link(data, self.head.next)

    def __contains__(self, data):    # example algorithm, implements the "in" operator
        current = self.head.next
        while current != self.head:
            if current.data == data: # element found
                return True
            current = current.next
        return False

- Blckknght

---

假设我删除了最后一个链接，它会自动调整为循环到第一个链接，还是我需要在我的删除函数中手动处理它？*通过试验弄清楚了。感谢您的帮助！ - Colosus__

Answer 2

确实，如果没有节点，那么就不可能有下一个/上一个指针:

root
 |
 v
None

如果只有一个节点，它将向前和向后链接到自身：

    root
     |
     v
+-> Node <-+
|   next---+
+---prev

如果有两个节点：

      root
       |
       v
  +-> Node   +-> Node <--+
  |   next---+   next--+ |
+-|---prev <-----prev  | |
| +--------------------+ |
+------------------------+

- Aasmund Eldhuset

---

你对于“无节点”的情况并不完全符合OP所描述的情况（尽管这是一种可能的方法）。相反，更接近于你所描述的“一个”节点的情况。然而，你的方法可能更方便表示，因为它允许更容易地进行“None”测试。 - Joost

感谢您提供的可视化表达，非常感谢您的帮助！ - Colosus__

Answer 3

            class Node:
                def __init__(self, d=None, n=None, p=None):
                    self.data = d
                    self.next_node = n
                    self.p_node = p
            
                def __str__(self):
                    return '(' + str(self.data) + ')'
            
            
            class CircularlinkedList:
                def __init__(self, r=None):
                    self.root = r
                    self.size = 0
            
                def add(self, d):
                    if self.size == 0:
                        self.root = Node(d)
                        self.root.next_node = self.root
                    else:
                        new_node = Node(d, self.root.next_node)
                        self.root.next_node = new_node
                    self.size += 1
            
                def find(self, d):
                    this_node = self.root
                    while True:
                        if this_node.data == d:
                            return d
                        elif this_node.next_node == self.root:
                            return False
                        this_node = this_node.next_node
            
                def remove(self, d):
                    this_node = self.root
                    prev_node = None
                    while True:
                        if this_node.data == d:
                            if prev_node is not None:
                                prev_node.next_node = this_node.next_node
                            else:
                                while this_node.next_node != self.root:
                                    this_node = this_node.next_node
                                this_node.next_node = self.root.next_node
                                self.root = self.root.next_node
                            self.size -= 1
                            return True
                        elif this_node.next_node == self.root:
                            return False
                        prev_node = this_node
                        this_node = this_node.next_node
            
                def print_list(self):
                    if self.root is None:
                        return
                    this_node = self.root
                    print(this_node, end='->')
                    while this_node.next_node != self.root:
                        this_node = this_node.next_node
                        print(this_node, end='->')
                    print()
            

           

cll = 循环链表()

for i in [5, 7, 3, 8, 9]:

    cll.add(i)

print('Size='+str(cll.size))

print(cll.find(8))

print(cll.find(12))

我的节点 = cll.根

 for i in range(8):

    my_node = my_node.next_node

    print(my_node,end='->')

打印()

cll.print_list()

cll.remove(8)

print(cll.remove(15))

print('Size='+str(cll.size))

cll.remove(5)

cll.print_list()

- Shah Vipul

Answer 4

关键步骤在于头部不是None。只有头部的Link节点的数据是None，并且通过其next属性指向自身。正如您链接到的答案中所提到的那样，它看起来应该像这样：

def __init__(self):
    self.head = Link(None, None)
    self.head.next = self.head

- Joost

---

我觉得我开始明白了。谢谢！ - Colosus__

Answer 5

#Linked List Program to Add and Delete Node Form Head, Tail, in Between Nodes.
class Node:
    """ Node Class having the data and pointer to the next Node"""
    def __init__(self,value):
        self.value=value
        self.nextnode=None
        
class CircularLinkedList(object):
    """ Linked List Class to point the value and the next nond"""
    def __init__(self):
        self.head=None

    def add_head_node(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
            
        crnt_node=node
        crnt_node.nextnode=self.head        
        first_node=self.head
        while first_node.nextnode is not self.head:
            first_node=first_node.nextnode          
        first_node.nextnode=crnt_node
        self.head=crnt_node

    #Adding elements in linked list to the tail.
    def add_tail_node(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
        crnt_node=node
        last_node=self.head
        while last_node.nextnode is not self.head:
            last_node=last_node.nextnode
        #pointing  head's last element to given node
        last_node.nextnode=crnt_node
        #pointing last node next to head nodes of element
        crnt_node.nextnode=self.head

    #Adding elements in linked after given Node.
    def add_after_node(self,after_value,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
        new_node=node
        after_node=Node(after_value)
        head_node=self.head
        while head_node.value !=after_node.value:
            head_node=head_node.nextnode
            last_node=head_node.nextnode
        head_node.nextnode=new_node
        new_node.nextnode=last_node
        head_node=head_node.nextnode

    #Adding elements in linked before given Node.
    def add_before_node(self,bfr_value,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
        new_node=node
        bfr_node=Node(bfr_value)
        head_node=self.head
        while head_node.nextnode.value!=bfr_node.value:
            head_node=head_node.nextnode
            last_node=head_node.nextnode
        head_node.nextnode=new_node
        new_node.nextnode=last_node
        head_node=head_node.nextnode
        #self.head=head_node.nextnode

    #deleting Head Node of Linked List
    def del_head_node(self):
        if self.head is None:
            print('Can not delete elements from Empty Linked List')
            return
        crnt_node=self.head.nextnode
        pointer_head=self.head.nextnode
        while pointer_head.nextnode.value!=self.head.value:
            pointer_head=pointer_head.nextnode
        pointer_head.nextnode=crnt_node
        self.head=crnt_node
        
    #deleting tail Node of Linked List
    def del_tail_node(self):
        if self.head is None:
            print('Can not delete elements from Empty Linked List')
            return
        crnt_node=self.head.nextnode
        #head_node=self.head
        while crnt_node.nextnode.nextnode.value!=self.head.value:
            crnt_node=crnt_node.nextnode
        crnt_node.nextnode=self.head

    #delete beteween node from Linked List
    def del_bw_node(self,value):
        node=Node(value)
        if self.head is None:
            print('Can not delete elements from Empty Linked List')
            return
        crnt_node=self.head
        while crnt_node.nextnode.value!=node.value:
            crnt_node=crnt_node.nextnode
            last_node=crnt_node.nextnode.nextnode
        crnt_node.nextnode=last_node

    #Function to print linked list node 
    def print_list(self):
        crnt_node=self.head
        while True:
            print(f'{crnt_node.value}->',end='')
            if crnt_node.nextnode is self.head:
                print(f'{self.head.value}',end='')
                break
            crnt_node = crnt_node.nextnode
        print()


cir_llist=CircularLinkedList()
cir_llist.add_head_node(1)
cir_llist.print_list()
cir_llist.add_head_node(2)
cir_llist.print_list()
cir_llist.add_head_node(3)
cir_llist.print_list()
cir_llist.add_head_node(4)
cir_llist.print_list()
cir_llist.add_head_node(5)
cir_llist.print_list()
cir_llist.add_tail_node(6)
cir_llist.print_list()
cir_llist.add_tail_node(8)
cir_llist.print_list()
cir_llist.add_after_node(6,7)
cir_llist.print_list()
cir_llist.add_before_node(6,0)
cir_llist.print_list()
cir_llist.add_before_node(0,10)
cir_llist.print_list()
cir_llist.del_head_node()
cir_llist.print_list()
cir_llist.del_head_node()
cir_llist.print_list()
cir_llist.del_tail_node()
cir_llist.print_list()
cir_llist.del_tail_node()
cir_llist.print_list()
cir_llist.del_bw_node(10)
cir_llist.print_list()
cir_llist.del_bw_node(0)
cir_llist.print_list()

- Mayank Awasthi