Danh sách được liên kết là gì và cách thực hiện chúng trong Python
Ảnh của JJ Ying trên unplashMột danh sách được liên kết trong các thuật ngữ lập trình là một loại dữ liệu trừu tượng hoạt động như một tập hợp các yếu tố dữ liệu tuyến tính được tổ chức như một tập hợp các nút chứa thông tin về những gì nút đó chứa và sau đó là một liên kết đến một nút khác. Điều này có thể có hai hình thức chính của một danh sách liên kết đơn, chỉ có một hướng liên kết giữa các nút hoặc danh sách liên kết gấp đôi, có thể được liên kết với cả mục tiếp theo và cuối cùng trong danh sách. Lợi ích của việc này đối với một mảng hoặc danh sách thông thường là các yếu tố có thể dễ dàng chèn và loại bỏ mà không cần phải thay đổi chỉ số của tất cả các mục khác và bộ nhớ được sử dụng để lưu trữ danh sách được liên kết không cần phải được tổ chức lại vì dữ liệu không phải được lưu trữ tiếp giáp. Tuy nhiên, chúng ta có thể truy cập các mục trong thời gian không đổi [O [1]] vì chúng ta có thể trong một mảng khi tìm kiếm một mục trong danh sách có độ phức tạp thời gian tuyến tính [O [n]].
Cấu trúc dữ liệu này có thể hữu ích khi:
- Bạn muốn chèn các mục một cách dễ dàng ở giữa các mục khác
- Kích thước của tổng số bộ sưu tập chưa được biết
- Bạn không cần truy cập ngẫu nhiên khi tìm kiếm các mục
- Không có mối quan tâm nào về việc sử dụng bộ nhớ để lưu trữ dữ liệu
Với suy nghĩ này, biết những gì chúng tôi muốn lấy dữ liệu sẽ làm và cách chúng tôi muốn tương tác với nó, sau đó chúng tôi có thể bắt đầu suy nghĩ về cách thực hiện điều này trong một cấu trúc dữ liệu thực tế trong Python. Các phương pháp chính thường được liên kết với điều này bao gồm:
- Chèn []: Thêm một mục vào danh sách được liên kết ở đầu danh sách
- Tìm []: Tìm một mục trong danh sách được liên kết
- Xóa []: Xóa một mục đã cho với một giá trị đã cho
- is_empty []: Trả về liệu danh sách được liên kết có trống hay không
- get_count []: Trả về số lượng mục trong danh sách được liên kết
Tuy nhiên, điều thú vị với điều này là không có cấu trúc dữ liệu tự nhiên trong Python mà chúng ta có thể xây dựng để xây dựng danh sách được liên kết này. Trong khi đối với hàng đợi và một ngăn xếp, chúng tôi đã có thể sử dụng cấu trúc dữ liệu danh sách đã được tích hợp trong Python, chúng tôi cần xây dựng một lớp nút trước khi chúng tôi có thể triển khai LinkedList.
Điều này là do mỗi mục trong danh sách được liên kết tự nó là một đối tượng riêng biệt có thể chứa bất kỳ thông tin nào mà nó muốn, cùng với việc xác định mục tiếp theo trong danh sách được liên kết. Điều này có nghĩa là nó phải có một thuộc tính trỏ đến hoặc xác định thông tin mà nó chứa và cũng là một thuộc tính trỏ đến nút tiếp theo trong danh sách được liên kết. Đối với điều này, chúng ta cũng phải thêm các hành vi cho phép chúng ta cả hai trích xuất dữ liệu mà nút chứa và nút tiếp theo cùng với việc có thể đặt hoặc điều chỉnh các thuộc tính này. Vì vậy, điều này có thể được thực hiện như:
Class Node[object]: def __init__[self, val]:
self.val = val
self.next = None def get_data[self]:
return self.val def set_data[self, val]:
self.val = valdef get_next[self]:
return self.nextdef set_next[self, next]:
self.next = next
Chúng ta có thể thấy ở đây chúng ta có các thuộc tính val và next tương ứng với dữ liệu mà nút giữ và sau đó cũng trỏ đến nút tiếp theo trong danh sách được liên kết. Thực tế là chúng tôi đã đặt ban đầu next thành
Class LinkedList[object]: def __init__[self, head = None]:0 cho thấy chúng tôi tạo một cái ngay từ đầu mà không có nút
self.head = head
self.count = 0
next nào. Sau đó, chúng tôi cũng thêm các phương thức cho phép chúng tôi in nút val và next hiện tại, cùng với khả năng thay đổi val và cũng đặt nút next.Với suy nghĩ này, sau đó chúng ta có thể tạo danh sách được liên kết. Chúng tôi sẽ tập trung vào danh sách được liên kết đơn lẻ, điều đó có nghĩa là mỗi nút chỉ có một liên kết đến tiếp theo trong danh sách được liên kết như chúng ta có thể thấy trong việc triển khai nút ở trên.
Điều đầu tiên cần làm sau đó là tạo hàm tạo sẽ được gọi bất cứ khi nào một danh sách được liên kết được tạo. Trong trường hợp này, chúng tôi bắt đầu với hai thuộc tính:
- Đầu: nút đầu tiên trong danh sách được liên kết
- Đếm: Số lượng nút trong danh sách được liên kết
Trước hết chúng ta tạo ra đầu trống để chúng ta bắt đầu với một danh sách liên kết trống. Điều này cũng có nghĩa là chúng tôi không phải kiểm tra xem chúng tôi có đầu khi lần đầu tiên thêm một mục hay không. Chúng tôi cũng thêm một thuộc tính đếm để khi thêm hoặc loại bỏ các mục, chúng tôi có thể thêm hoặc trừ một thuộc tính này. Điều này có nghĩa là khi chúng tôi muốn kiểm tra số lượng mục chúng tôi có trong danh sách được liên kết, chúng tôi có thể gọi đơn giản là thuộc tính này thay vì lặp qua toàn bộ danh sách. Đây là một sự đánh đổi bằng cách thêm độ phức tạp để thêm và loại bỏ các chức năng trong khi loại bỏ độ phức tạp về thời gian khi cố gắng tìm độ dài.
Điều này có thể được thực hiện như sau:
Class LinkedList[object]: def __init__[self, head = None]:
self.head = head
self.count = 0
Với danh sách được liên kết, một phương pháp quan trọng là có thể thêm các mục hoặc nút vào danh sách. Hiện tại, chúng tôi sẽ chỉ tập trung vào việc thêm các mục vào đầu danh sách được liên kết, tuy nhiên điều này có thể được mở rộng để thêm các mục ở bất cứ đâu trong danh sách tùy thuộc vào việc này là chỉ bằng chỉ mục hay trước hoặc sau một mục khác. Cách chúng tôi làm điều này ở đầu tuy nhiên khá đơn giản và là một điểm khởi đầu tốt.
Chúng tôi thực hiện điều này bằng cách khởi tạo một nút mới, gán dữ liệu cho nút mới, đặt next của nút mới cho đầu hiện tại của danh sách và sau đó chỉ cần đặt đầu của danh sách được liên kết vào nút mới. Đẹp và đơn giản phải! Điều này chỉ làm cho nó tốt đẹp và dễ dàng với độ phức tạp thời gian thấp so với việc thực hiện điều tương tự với một danh sách tiêu chuẩn trong Python. Điều này có thể được thực hiện như sau:
def insert[self, data]:
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
Bây giờ chúng tôi có thể thêm các mục vào danh sách được liên kết của chúng tôi, điều tiếp theo cần thực hiện là tìm kiếm danh sách được liên kết đó để xem liệu dữ liệu có phải là một phần của danh sách được liên kết hay không. Một lần nữa, có nhiều cách để thực hiện việc này cho dù tìm kiếm theo giá trị hay theo chỉ mục, nhưng vì sự đơn giản, chúng tôi sẽ tập trung vào việc tìm kiếm theo giá trị.
Chúng tôi có thể làm điều này khá đơn giản bằng cách lặp lại danh sách được liên kết để xem liệu có bất kỳ dữ liệu nào của nút có phù hợp với giá trị mà chúng tôi đang tìm kiếm hay không. Điều này có nghĩa là trong trường hợp xấu nhất, chúng tôi phải lặp lại tất cả các mục trong danh sách được liên kết và do đó độ phức tạp thời gian diễn ra trên O [n]. Khi chúng ta tìm thấy mục này, sau đó chúng ta có thể trả lại một số nút đó hoặc trong trường hợp giá trị đó không tồn tại thì chúng ta có thể trả về
Class LinkedList[object]: def __init__[self, head = None]:0 để tránh bất kỳ lỗi nào bị ném.
self.head = head
self.count = 0
def find[self, val]:
"""
Search for item in Linked List with data = valTime complexity is O[n] as in worst case scenario
#start with the first item in the Linked List
have to iterate over whole Linked List
"""
item = self.head #then iterate over the next nodes
#but if item = None then end search
while item != None:#if the data in item matched val
#then return item
if item.get_data[] == val:
return item#otherwise we get the next item in the list
else:
item = item.get_next[]#if while loop breaks with None then nothing found
#so we return None
return None
Nếu chúng ta có thể tìm thấy các mục, thì việc xóa chúng khỏi danh sách được liên kết thì sao? Bạn có thể tưởng tượng rằng bạn không chỉ muốn có thể thêm và tìm các mục mà còn có thể xóa các mục trong danh sách được liên kết. Đây là một chức năng khác có thể được xây dựng theo những cách khác nhau nhưng trong trường hợp này, chúng tôi tập trung vào việc loại bỏ các mục có giá trị nhất định thay vì chỉ mục. Điều này sau đó tuân theo một logic tương tự với hàm tìm ở trên.
Sự khác biệt chính giữa việc loại bỏ một mục khỏi danh sách được liên kết và danh sách thông thường là trong danh sách được liên kết, nút vẫn có thể tồn tại ở đâu đó, chúng tôi chỉ cần thay đổi con trỏ từ nút trước đó từ nút đó sang nút tiếp theo. Điều này làm cho việc loại bỏ các mục khỏi danh sách được liên kết tương đối dễ dàng so với danh sách thông thường vì không phải tất cả các mục sau khi nút bị xóa phải thay đổi chỉ mục của chúng, chỉ cần kết nối giữa các nút. Điều này có thể được thực hiện như sau:
def remove[self, item]:
"""
Remove Node with value equal to item Time complexity is O[n] as in the worst case we have to
iterate over the whole linked list
""" #set the current node starting with the head
current = self.head
#create a previous node to hold the one before
#the node we want to remove
previous = None #while current is note None then we can search for it
while current is not None: #if current equals to item then we can break
if current.data == item:
break #otherwise we set previous to current and
#current to the next item in list
previous = current
current = current.get_next[] #if the current is None then item, not in the list
if current is None:
raise ValueError[f"{item} is not in the list"] #if previous None then the item is at the head
if previous is None:
self.head = current.next
self.count -= 1 #otherwise then we remove that node from the list
else:
previous.set_next[current.get_next[]]
self.count -= 1
Với chức năng chính của danh sách được liên kết được tạo thì chúng ta có thể bắt đầu bằng cách thêm các phương thức khác sẽ làm cho việc sử dụng danh sách được liên kết đơn giản hơn một chút. Trong trường hợp này, hai phương pháp bổ sung mà chúng ta có thể thêm bao gồm nhận được độ dài của danh sách được liên kết và xem danh sách có trống không.
Phương pháp đầu tiên để trả về độ dài của liên kết là tương đối dễ dàng. Điều này là do cách mà chúng tôi đã thực hiện phương pháp cấu trúc cùng với các phương thức
Class LinkedList[object]: def __init__[self, head = None]:8 và
self.head = head
self.count = 0
Class LinkedList[object]: def __init__[self, head = None]:9. Khi làm như vậy, chúng tôi đã tạo thuộc tính
self.head = head
self.count = 0
def insert[self, data]:0 được thêm vào khi chúng tôi thêm các nút mới vào danh sách được liên kết và sau đó giảm khi chúng tôi lấy đi các nút bằng phương thức
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
Class LinkedList[object]: def __init__[self, head = None]:9. Do đó, đơn giản là chúng ta có thể trả về giá trị được lưu trữ trong thuộc tính
self.head = head
self.count = 0
def insert[self, data]:0 như sau:
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
def get_count[self]:
"""
Return the length of the Linked List Time complexity O[1] as only returning a single value
""" return self.count
Điều gì về việc xem danh sách được liên kết trống? Chúng ta có thể làm điều này theo cách tương tự như nhận thuộc tính
def insert[self, data]:0 và kiểm tra xem điều này có bằng không hay không. Tuy nhiên, vì lợi ích đơn giản, chúng ta có thể dễ dàng kiểm tra xem danh sách được liên kết có trống hay không bằng cách xem liệu thuộc tính
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
def insert[self, data]:4 có không. Điều này là để đảm bảo nếu một số lý do, thuộc tính
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
def insert[self, data]:0 không được triển khai đúng cách, chúng tôi có thể dễ dàng kiểm tra xem
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
def insert[self, data]:4 có trống không vì điều này sẽ chỉ ra rằng chúng tôi không có nút nào không!
"""
Create a new node at the Head of the Linked List This has a time complexity of O[1] as we are simply changing
the current head of the Linked List and no indices have to
change
""" #create a new node to hold the data
new_node = Node[data]#set the next of the new node to the current head
#set the head of the Linked List to the new head
new_node.set_next[self.head]
self.head = new_node #add 1 to the count
self.count += 1
def is_empty[self]:
"""
Returns whether the Linked List is empty or not Time complexity O[1] as only returns True or False
""" #we only have to check the head if is None or not
return self.head == None
Do đó, chúng tôi đã thực hiện chức năng chính của một danh sách được liên kết đơn lẻ trong Python. Tất cả những gì còn lại là kết hợp tất cả những điều này có thể được thực hiện như sau:
Sau đó, bạn có thể thêm các chức năng khác một cách riêng biệt như:
- Xóa [INDEX]: Xóa một mục tại một chỉ mục đã cho
- findat [index]: Tìm mục tại chỉ mục đã cho
- Chèn [chỉ mục]: Chèn một mục tại một chỉ mục đã cho
Điều này cũng có thể được mở rộng thành một danh sách liên kết gấp đôi, theo đó mỗi nút có một liên kết đến nút tiếp theo và cũng với nút trước đó trong danh sách được liên kết. Điều này có thể được thực hiện đơn giản với một vài điều chỉnh nhưng tôi sẽ cho phép bạn tìm ra điều đó.
Vì vậy, bạn đi, bạn chỉ cần tạo một danh sách được liên kết có lợi ích của việc chèn và loại bỏ các mục dễ dàng vì bộ nhớ không cần được tổ chức lại và thực tế là các mục không cần được lưu trữ trong bộ nhớ. Tất nhiên, bạn phải nhận thức được những hạn chế của quyền truy cập không ngẫu nhiên và khó khăn trong việc tìm kiếm các mục, nhưng điều này sẽ phụ thuộc vào ứng dụng của bạn trong danh sách được liên kết.
Đây là bài viết thứ sáu trong một loạt các cấu trúc dữ liệu khám phá và việc sử dụng và triển khai của chúng trong Python. Nếu bạn bỏ lỡ ba cái trước trên ngăn xếp, từ điển và bộ dữ liệu trong Python, bạn có thể tìm thấy chúng tại các liên kết sau:
Các bài viết trong tương lai trong sê -ri sẽ bao gồm các danh sách, hàng đợi và đồ thị được liên kết. Để đảm bảo rằng bạn không bỏ lỡ bất kỳ điều gì sau đó đăng ký để nhận thông báo email khi chúng được xuất bản:
Và nếu bạn thích những gì bạn đọc nhưng chưa phải là thành viên trung bình, thì hãy xem xét hỗ trợ cả bản thân và các tác giả tuyệt vời khác trên nền tảng này bằng cách đăng ký bằng mã giới thiệu của tôi dưới đây:
Cảm ơn bạn đã đọc!