Làm thế nào để tạo một LinkedList tròn

Question

Tôi biết cách tạo các lớp Link và LinearLinkedList, nhưng tôi không thể cho cuộc sống của tôi tìm ra cách sửa đổi chúng thành một danh sách tạo liên kết tròn. Tôi đã đọc câu trả lời cho câu hỏi này: Help with Circular Linked List in Python. Tuy nhiên, tôi không hiểu làm thế nào nếu người đứng đầu là Không, sau đó làm thế nào một đối tượng Không có loại có một thuộc tính "tiếp theo"? Tôi dường như không thể hiểu được khái niệm. Nếu ai đó có thể chỉ cho tôi hàm init của một mẫu CircularLinkedList và giải thích đơn giản về cách hoạt động, tôi nghĩ tôi có thể hiểu được nó. Cảm ơn bạn vì bất kỳ và tất cả sự giúp đỡ

Chỉnh sửa: Tôi chỉ cần danh sách được chuyển tiếp. Nếu đúng như vậy, liệu logic đằng sau nó có cần phải thay đổi đáng kể không?

Answer 1

Thường trong danh sách được liên kết vòng tròn, bạn có liên kết đặc biệt không chứa dữ liệu có ý nghĩa. Thay vào đó, đó là một "sentinel" cho bạn biết nơi bắt đầu (và kết thúc) của danh sách là. Liên kết này sẽ tồn tại ngay cả khi danh sách trống, vì vậy các thuật toán của bạn sẽ hoạt động trên tất cả các danh sách, mà không cần nhiều trường hợp đặc biệt cần mã đặc biệt.

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 
     return False 

Answer 2

Bước quan trọng ở đây là đầu không phải là None. Chỉ có dữ liệu của nút Link của đầu là None và nó trỏ đến chính nó thông qua thuộc tính next của nó. Như đã đề cập trong câu trả lời bạn đã liên kết, trông giống như sau:

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

Answer 3

Thật vậy; nếu không có các nút, sau đó không thể có con trỏ tiếp theo/trước:

root 
| 
v 
None 

Nếu có một nút, nó liên kết ngược trở lại và chuyển tiếp đến bản thân:

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

Nếu có hai nút:

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