Một danh sách được liên kết là một trong những cấu trúc dữ liệu phổ biến nhất được sử dụng trong khoa học máy tính. Nó cũng là một trong những thứ đơn giản nhất, và cũng như cơ bản cho các cấu trúc cấp cao hơn như ngăn xếp, bộ đệm tròn và hàng đợi.
Nội phân chính
- Bước 1: Node dưới dạng cấu trúc dữ liệu
- Bước 2: Tạo một lớp cho một danh sách liên kết đơn
- Bước 3: Thêm nút
- Bước 4: Tìm kiếm danh sách
- Bước 5: Loại bỏ một mục khỏi danh sách
- Bước 6: Tạo danh sách liên kết kép
- Bước 7: Tạo danh sách liên kết kép với Deque
- Sự nhìn nhận
Nội phân chính
- Bước 1: Node dưới dạng cấu trúc dữ liệu
- Bước 2: Tạo một lớp cho một danh sách liên kết đơn
- Bước 3: Thêm nút
- Bước 4: Tìm kiếm danh sách
- Bước 5: Loại bỏ một mục khỏi danh sách
- Bước 6: Tạo danh sách liên kết kép
- Bước 7: Tạo danh sách liên kết kép với Deque
- Sự nhìn nhận
Sự nhìn nhận
Nói chung, một danh sách là một tập hợp các yếu tố dữ liệu đơn được kết nối thông qua các tài liệu tham khảo. C Lập trình viên biết điều này như con trỏ. Ví dụ, một yếu tố dữ liệu có thể bao gồm dữ liệu địa chỉ, dữ liệu địa lý, dữ liệu hình học, thông tin định tuyến hoặc chi tiết giao dịch. Thông thường, mỗi yếu tố của danh sách được liên kết có cùng loại dữ liệu dành riêng cho danh sách.
Một phần tử danh sách duy nhất được gọi là một nút. Các nút không giống như các mảng được lưu trữ tuần tự trong bộ nhớ. Thay vào đó, nó có khả năng tìm thấy chúng ở các phân đoạn bộ nhớ khác nhau mà bạn có thể tìm thấy bằng cách theo các con trỏ từ nút này sang nút khác. Người ta thường đánh dấu phần cuối của danh sách với phần tử NIL, được biểu thị bằng Python tương đương
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
9.Hình 1: Danh sách liên kết đơn
Có tồn tại hai loại danh sách - danh sách đơn và liên kết kép. Một nút trong danh sách liên kết đơn chỉ chỉ vào phần tử tiếp theo trong danh sách, trong khi một nút trong danh sách liên kết kép cũng chỉ vào nút trước đó. Cấu trúc dữ liệu chiếm nhiều không gian hơn vì bạn sẽ cần một biến bổ sung để lưu trữ tham chiếu thêm.
Hình 2: Danh sách liên kết kép
Một danh sách liên kết đơn có thể được chuyển từ đầu đến đuôi trong khi đi qua phía sau không dễ dàng như vậy. Ngược lại, một danh sách liên kết kép cho phép đi qua các nút theo cả hai hướng với cùng một chi phí, bất kể bạn bắt đầu nút nào. Ngoài ra, việc thêm và xóa các nút cũng như phân tách các danh sách liên kết đơn được thực hiện trong không quá hai bước. Trong một danh sách liên kết kép, bốn gợi ý phải được thay đổi.
Ngôn ngữ Python không chứa kiểu dữ liệu được xác định trước cho các danh sách được liên kết. Để đối phó với tình huống này, chúng tôi phải tạo loại dữ liệu của riêng mình hoặc phải sử dụng các mô -đun Python bổ sung cung cấp triển khai loại dữ liệu như vậy.
Bước 1: Node dưới dạng cấu trúc dữ liệu
Trong bài viết này, chúng tôi sẽ trải qua các bước để tạo cấu trúc dữ liệu danh sách được liên kết của riêng chúng tôi. Đầu tiên chúng tôi tạo một cấu trúc dữ liệu tương ứng cho nút. Thứ hai, bạn sẽ học cách thực hiện và sử dụng cả danh sách liên kết đơn và cuối cùng là danh sách liên kết kép.
- Để có cấu trúc dữ liệu chúng tôi có thể làm việc, chúng tôi xác định một nút. Một nút được triển khai dưới dạng một lớp có tên
0. Lớp chứa định nghĩa để tạo một thể hiện đối tượng, trong trường hợp này, với hai biến -class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
1 để giữ giá trị nút vàclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
2 để lưu trữ tham chiếu đến nút tiếp theo trong danh sách. Hơn nữa, một nút có các phương thức và thuộc tính sau:class SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
3: Khởi tạo nút với dữ liệuclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
4: Giá trị được lưu trữ trong nútclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
5: Con trỏ tham chiếu đến nút tiếp theoclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
6: So sánh giá trị với giá trị nútCác phương pháp này đảm bảo rằng chúng tôi có thể khởi tạo một nút đúng với dữ liệu của chúng tôi [
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
7] và bao gồm cả trích xuất và lưu trữ dữ liệu [thông qua thuộc tính class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
4] cũng như nhận được tham chiếu đến nút được kết nối [thông qua thuộc tính class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
5]. Phương pháp class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
6 cho phép chúng ta so sánh giá trị nút với giá trị của một nút khác.class ListNode:
def __init__[self, data]:
"constructor to initiate this object"
# store data
self.data = data
# store reference [next item]
self.next = None
return
def has_value[self, value]:
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
Liệt kê 1: Lớp ListNode
Tạo một nút đơn giản như vậy và khởi tạo một đối tượng của lớp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
0:node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
Liệt kê 2: khởi tạo các nút
Bước 2: Tạo một lớp cho một danh sách liên kết đơn
Đã thực hiện rằng chúng tôi có sẵn ba trường hợp của lớp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
0. Các trường hợp này biểu thị ba nút độc lập có chứa các giá trị 15 [số nguyên], 8.2 [float] và "berlin" [chuỗi].- Là bước thứ hai, chúng tôi xác định một lớp có tên
3 bao gồm các phương thức cần thiết để quản lý các nút danh sách của chúng tôi. Nó chứa các phương pháp sau:def add_list_item[self, item]: "add an item at the end of the list" if not isinstance[item, ListNode]: item = ListNode[item] if self.head is None: self.head = item else: self.tail.next = item self.tail = item return
7: Bắt đầu một đối tượngclass SingleLinkedList: def __init__[self]: "constructor to initiate this object" self.head = None self.tail = None return
5: Trả lại số lượng nútdef add_list_item[self, item]: "add an item at the end of the list" if not isinstance[item, ListNode]: item = ListNode[item] if self.head is None: self.head = item else: self.tail.next = item self.tail = item return
6: Đầu ra các giá trị nútdef add_list_item[self, item]: "add an item at the end of the list" if not isinstance[item, ListNode]: item = ListNode[item] if self.head is None: self.head = item else: self.tail.next = item self.tail = item return
7: Thêm một nút ở cuối danh sáchdef add_list_item[self, item]: "add an item at the end of the list" if not isinstance[item, ListNode]: item = ListNode[item] if self.head is None: self.head = item else: self.tail.next = item self.tail = item return
9: Xóa nút theo ID của nódef add_list_item[self, item]: "add an item at the end of the list" if not isinstance[item, ListNode]: item = ListNode[item] if self.head is None: self.head = item else: self.tail.next = item self.tail = item return
Chúng tôi sẽ trải qua từng phương pháp này từng bước.
Phương pháp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
7 xác định hai biến lớp bên trong có tên def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
1 và def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
2. Chúng đại diện cho các nút bắt đầu và kết thúc của danh sách. Ban đầu, cả def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
1 và def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
2 đều có giá trị node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
9 miễn là danh sách trống.Liệt kê 3: Lớp SinglelinkedList [Phần một]
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
Bước 3: Thêm nút
Thêm các mục vào danh sách được thực hiện thông qua
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
7. Phương pháp này yêu cầu một nút như một tham số bổ sung. Để đảm bảo rằng đó là một nút thích hợp [một thể hiện của lớp class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
0], tham số trước tiên được xác minh bằng cách sử dụng hàm Python tích hợp def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
8. Nếu thành công, nút sẽ được thêm vào cuối danh sách. Nếu def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
9 không phải là class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
0, thì một cái được tạo ra.Trong trường hợp danh sách là [vẫn] trống, nút mới trở thành người đứng đầu danh sách. Nếu một nút đã có trong danh sách, thì giá trị của đuôi được điều chỉnh cho phù hợp.
Liệt kê 4: Lớp SinglelinkedList [Phần hai]
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
Phương pháp
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
5 đếm các nút và trả về độ dài của danh sách. Để nhận từ một nút này sang nút tiếp theo trong danh sách thuộc tính nút class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
5 phát huy tác dụng và trả lại liên kết đến nút tiếp theo. Đếm các nút được thực hiện trong một vòng lặp trong một thời gian miễn là chúng ta không đạt đến cuối danh sách, được biểu thị bằng liên kết node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
9 đến nút tiếp theo.Liệt kê 5: Lớp SinglelinkedList [Phần ba]
def list_length[self]:
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
Phương thức
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
6 xuất các giá trị nút bằng cách sử dụng thuộc tính nút class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
1. Một lần nữa, để lấy từ một nút này sang nút tiếp theo, liên kết được sử dụng được cung cấp thông qua thuộc tính class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
2.Liệt kê 6: Lớp SinglelinkedList [Phần bốn]
def output_list[self]:
"outputs the list [the value of the node, actually]"
current_node = self.head
while current_node is not None:
print[current_node.data]
# jump to the linked node
current_node = current_node.next
return
Dựa trên lớp
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
3, chúng tôi có thể tạo một danh sách thích hợp có tên def output_list[self]:
"outputs the list [the value of the node, actually]"
current_node = self.head
while current_node is not None:
print[current_node.data]
# jump to the linked node
current_node = current_node.next
return
8 và chơi với các phương thức của nó như đã được mô tả ở trên trong Danh sách 3-6. Do đó, chúng tôi tạo bốn nút danh sách, đánh giá chúng trong vòng lặp def output_list[self]:
"outputs the list [the value of the node, actually]"
current_node = self.head
while current_node is not None:
print[current_node.data]
# jump to the linked node
current_node = current_node.next
return
9 và xuất nội dung danh sách. Liệt kê 7 chỉ cho bạn cách lập trình và liệt kê 8 cho thấy đầu ra.Liệt kê 7: Tạo các nút và đầu ra danh sách
# create four single nodes
node1 = ListNode[15]
node2 = ListNode[8.2]
item3 = "Berlin"
node4 = ListNode[15]
track = SingleLinkedList[]
print["track length: %i" % track.list_length[]]
for current_item in [node1, node2, item3, node4]:
track.add_list_item[current_item]
print["track length: %i" % track.list_length[]]
track.output_list[]
Đầu ra như sau và cho thấy danh sách phát triển như thế nào:
Kiểm tra hướng dẫn thực hành của chúng tôi, thực tế để học Git, với các thực hành tốt nhất, các tiêu chuẩn được công nghiệp chấp nhận và bao gồm bảng gian lận. Ngừng các lệnh git googling và thực sự tìm hiểu nó!
Liệt kê 8: Thêm nút vào danh sách
$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15
Bước 4: Tìm kiếm danh sách
Tìm kiếm toàn bộ danh sách được thực hiện bằng phương pháp
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
8. Nó yêu cầu một tham số bổ sung cho giá trị được tìm kiếm. Người đứng đầu của danh sách là điểm khởi đầu.Trong khi tìm kiếm, chúng tôi đếm các nút. Để chỉ ra một trận đấu, chúng tôi sử dụng số nút tương ứng. Phương thức
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
8 trả về một danh sách các số nút đại diện cho các trận đấu. Ví dụ, cả nút thứ nhất và thứ tư đều chứa giá trị 15. Tìm kiếm cho 15 kết quả trong danh sách với hai phần tử: # create four single nodes
node1 = ListNode[15]
node2 = ListNode[8.2]
item3 = "Berlin"
node4 = ListNode[15]
track = SingleLinkedList[]
print["track length: %i" % track.list_length[]]
for current_item in [node1, node2, item3, node4]:
track.add_list_item[current_item]
print["track length: %i" % track.list_length[]]
track.output_list[]
2.
Liệt kê 9: Phương thức tìm kiếm unetered_search []
def unordered_search [self, value]:
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value[value]:
results.append[node_id]
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
Bước 5: Loại bỏ một mục khỏi danh sách
Loại bỏ một nút khỏi danh sách yêu cầu điều chỉnh chỉ một tham chiếu - cái trỏ vào nút để được xóa bây giờ phải trỏ đến cái tiếp theo. Tham chiếu này được giữ bởi nút để được gỡ bỏ và phải được thay thế. Trong nền, người thu gom rác Python chăm sóc các vật thể không được giới thiệu và dọn dẹp.
Phương pháp sau đây được đặt tên là
def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
9. Là một tham số, nó đề cập đến số lượng của nút tương tự như giá trị được trả về bởi def add_list_item[self, item]:
"add an item at the end of the list"
if not isinstance[item, ListNode]:
item = ListNode[item]
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
8.Liệt kê 10: Xóa một nút theo số nút
def remove_list_item_by_id[self, item_id]:
"remove the list item with the item id"
current_id = 1
current_node = self.head
previous_node = None
while current_node is not None:
if current_id == item_id:
# if this is the first node [head]
if previous_node is not None:
previous_node.next = current_node.next
else:
self.head = current_node.next
# we don't have to look any further
return
# needed for the next iteration
previous_node = current_node
current_node = current_node.next
current_id = current_id + 1
return
Bước 6: Tạo danh sách liên kết kép
Để tạo một danh sách liên kết kép, cảm giác tự nhiên chỉ để mở rộng lớp
class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
0 bằng cách tạo một tham chiếu bổ sung cho nút trước đó. Điều này ảnh hưởng đến các phương pháp để thêm, loại bỏ và sắp xếp các nút. Như được hiển thị trong Danh sách 11, một thuộc tính mới có tên # create four single nodes
node1 = ListNode[15]
node2 = ListNode[8.2]
item3 = "Berlin"
node4 = ListNode[15]
track = SingleLinkedList[]
print["track length: %i" % track.list_length[]]
for current_item in [node1, node2, item3, node4]:
track.add_list_item[current_item]
print["track length: %i" % track.list_length[]]
track.output_list[]
6 đã được thêm vào để lưu trữ con trỏ tham chiếu đến nút trước đó trong danh sách. Chúng tôi sẽ thay đổi các phương thức của chúng tôi để sử dụng thuộc tính này để theo dõi và đi qua các nút.Danh sách 11: Lớp Node Danh sách mở rộng
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
0Bây giờ chúng tôi có thể xác định một danh sách liên kết kép như sau:
Liệt kê 12: Lớp DoubLelinkedList
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
1Như được mô tả trước đó, việc thêm các nút đòi hỏi thêm một chút hành động. Liệt kê 13 cho thấy cách thực hiện điều đó:
Liệt kê 13: Thêm các nút trong danh sách liên kết kép
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
2Loại bỏ một mục khỏi danh sách các chi phí tương tự phải được tính đến. Liệt kê 14 cho thấy cách làm điều đó:
Liệt kê 14: Xóa một mục khỏi danh sách liên kết kép
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
3Liệt kê 15 cho thấy cách sử dụng lớp trong chương trình Python.
Liệt kê 15: Xây dựng danh sách liên kết kép
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
4Như bạn có thể thấy, chúng ta có thể sử dụng lớp chính xác như trước đây khi nó chỉ là một danh sách liên kết đơn. Thay đổi duy nhất là cấu trúc dữ liệu nội bộ.
Bước 7: Tạo danh sách liên kết kép với Deque
Vì các kỹ sư khác đã phải đối mặt với cùng một vấn đề, chúng tôi có thể đơn giản hóa mọi thứ cho chính mình và sử dụng một trong số ít các triển khai hiện có có sẵn. Trong Python, chúng ta có thể sử dụng đối tượng deque từ mô -đun
# create four single nodes
node1 = ListNode[15]
node2 = ListNode[8.2]
item3 = "Berlin"
node4 = ListNode[15]
track = SingleLinkedList[]
print["track length: %i" % track.list_length[]]
for current_item in [node1, node2, item3, node4]:
track.add_list_item[current_item]
print["track length: %i" % track.list_length[]]
track.output_list[]
7. Theo tài liệu mô -đun:Deques là một khái quát của các ngăn xếp và hàng đợi [tên được phát âm là "boong" và viết tắt cho "hàng đợi kết thúc kép"]. Deques hỗ trợ chủ đề an toàn, bộ nhớ hiệu quả và bật lên từ hai bên của deque với hiệu suất x x xấp xỉ cùng một trong hai hướng.
Ví dụ: đối tượng này chứa các phương thức sau:
8: Thêm một mục vào bên phải của danh sách [kết thúc]# create four single nodes node1 = ListNode[15] node2 = ListNode[8.2] item3 = "Berlin" node4 = ListNode[15] track = SingleLinkedList[] print["track length: %i" % track.list_length[]] for current_item in [node1, node2, item3, node4]: track.add_list_item[current_item] print["track length: %i" % track.list_length[]] track.output_list[]
9: Thêm một mục vào phía bên trái của danh sách [đầu]# create four single nodes node1 = ListNode[15] node2 = ListNode[8.2] item3 = "Berlin" node4 = ListNode[15] track = SingleLinkedList[] print["track length: %i" % track.list_length[]] for current_item in [node1, node2, item3, node4]: track.add_list_item[current_item] print["track length: %i" % track.list_length[]] track.output_list[]
0: Xóa tất cả các mục khỏi danh sách$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
1: Đếm số lượng các mặt hàng có giá trị nhất định$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
2: Tìm lần xuất hiện đầu tiên của một giá trị trong danh sách$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
3: Chèn một mục trong danh sách$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
4: Xóa một mục khỏi phía bên phải của danh sách [kết thúc]$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
5: Xóa một mục khỏi phía bên trái của danh sách [đầu]$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
6: Xóa một mục khỏi danh sách$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
7: Đảo ngược danh sách$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
Cấu trúc dữ liệu cơ bản của
$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15
8 là một danh sách python được liên kết kép. Nút danh sách đầu tiên có chỉ số 0. Sử dụng $ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15
8 dẫn đến sự đơn giản hóa đáng kể của lớp class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
0. Điều duy nhất chúng tôi giữ là biến lớp class SingleLinkedList:
def __init__[self]:
"constructor to initiate this object"
self.head = None
self.tail = None
return
1 để lưu trữ giá trị nút. Liệt kê 16 như sau:Liệt kê 16: ListNode Class với deque [đơn giản hóa]
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
5Định nghĩa về các nút không thay đổi và tương tự như liệt kê 2. Với kiến thức này, chúng tôi tạo một danh sách các nút như sau:
Liệt kê 17: Tạo một danh sách với Deque
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
6Thêm một mục ở đầu danh sách hoạt động với phương thức
# create four single nodes
node1 = ListNode[15]
node2 = ListNode[8.2]
item3 = "Berlin"
node4 = ListNode[15]
track = SingleLinkedList[]
print["track length: %i" % track.list_length[]]
for current_item in [node1, node2, item3, node4]:
track.add_list_item[current_item]
print["track length: %i" % track.list_length[]]
track.output_list[]
9 như liệt kê 18 hiển thị:Danh sách 18: Thêm một phần tử ở đầu danh sách
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
7Tương tự,
# create four single nodes
node1 = ListNode[15]
node2 = ListNode[8.2]
item3 = "Berlin"
node4 = ListNode[15]
track = SingleLinkedList[]
print["track length: %i" % track.list_length[]]
for current_item in [node1, node2, item3, node4]:
track.add_list_item[current_item]
print["track length: %i" % track.list_length[]]
track.output_list[]
8 thêm một nút ở cuối danh sách như danh sách 19 cho thấy:Liệt kê 19: Thêm một phần tử ở cuối danh sách
node1 = ListNode[15]
node2 = ListNode[8.2]
node3 = ListNode["Berlin"]
8Sự kết luận
Danh sách được liên kết là cấu trúc dữ liệu dễ thực hiện và cung cấp tính linh hoạt sử dụng tuyệt vời. Nó được thực hiện với một vài dòng mã. Là một cải tiến, bạn có thể thêm một bộ đếm nút - một biến lớp chỉ đơn giản là giữ số lượng nút trong danh sách. Điều này làm giảm việc xác định độ dài danh sách thành một thao tác duy nhất với O [1] và bạn không phải đi qua toàn bộ danh sách.
Để đọc thêm và triển khai thay thế, bạn có thể có một cái nhìn ở đây:
4 - Danh sách được liên kết Các kiểu dữ liệu cho Python [//pythonhosted.org/llist/]def unordered_search [self, value]: "search the linked list for the node that has this value" # define current_node current_node = self.head # define position node_id = 1 # define list of results results = [] while current_node is not None: if current_node.has_value[value]: results.append[node_id] # jump to the linked node current_node = current_node.next node_id = node_id + 1 return results
7 - Kiểu dữ liệu container [//docs.python.org/3.6/l Library/collections.html]# create four single nodes node1 = ListNode[15] node2 = ListNode[8.2] item3 = "Berlin" node4 = ListNode[15] track = SingleLinkedList[] print["track length: %i" % track.list_length[]] for current_item in [node1, node2, item3, node4]: track.add_list_item[current_item] print["track length: %i" % track.list_length[]] track.output_list[]
Sự nhìn nhận
Tác giả xin cảm ơn Gerold Rupprecht và Mandy Neumey vì sự hỗ trợ của họ, và nhận xét trong khi chuẩn bị bài viết này.