如何创建循环链表

Question

我知道如何创建 Link 和 LinearLinkedList 类，但我就是想不出如何将它们修改为创建 circularlinkedlist.

我已经阅读了 this question 的答案。但是，我不明白如果 head 是 None，那么 None 类型的对象怎么会有 next 属性？我似乎无法理解这个概念。

如果有人能向我展示示例 CircularLinkedList 的 __init__ 功能以及其工作原理的简单说明，我想我就能理解它。

感谢所有帮助

编辑：我只需要向前遍历列表。如果是这样，背后的逻辑是否需要彻底改变？

Answer 1

这里关键的一步是头部不是None。只有head的Link节点的数据是None，它通过它的next属性指向自己。正如您链接到的答案中提到的那样，它看起来像这样：

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

Answer 2

确实；如果没有节点，那么就没有 next/previous 个指针：

root
 |
 v
None

如果有一个节点，它向后链接并转发给自己：

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

如果有两个节点：

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

Answer 3

通常在循环 linked 列表中，您有一个不包含有意义数据的特殊 link。相反，它是一个 "sentinel" 让你知道列表的开始（和结束）在哪里。即使列表为空，此 link 也会存在，因此您的算法将适用于所有列表，没有很多特殊情况需要特殊代码。

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

Answer 4

#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()

Answer 5

            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 = CircularlinkedList()

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

    cll.add(i)

打印('Size='+str(cll.size))

打印(cll.find(8))

打印(cll.find(12))

my_node = cll.root

 for i in range(8):

    my_node = my_node.next_node

    print(my_node,end='->')

打印()

cll.print_list()

cll.remove(8)

打印(cll.remove(15))

打印('Size='+str(cll.size))

cll.remove(5)

cll.print_list()

如何创建循环链表

How to Create a Circular LinkedList

python

singly-linked-list

circular-list