Phát triển một danh sách được liên kết duy nhất bằng Python
Thực hiện và Hiểu các Thao tác Chèn và Xóa
Hình ảnh của tác giả
Danh sách liên kết là một phần của cấu trúc dữ liệu. Nó là một trong những cấu trúc dữ liệu quan trọng nhất.
Nội dung chính
- Phát triển một danh sách được liên kết duy nhất bằng Python
- Thực hiện và Hiểu các Thao tác Chèn và Xóa
- Chèn vào một danh sách được liên kết duy nhất
- Cảm ơn vì đã đọc
- MÃ ĐẦY ĐỦ
- Video liên quan
Nói một cách đơn giản, chúng ta có thể nói rằng danh sách liên kết là một tập hợp các nút mà mỗi nút được kết nối với một số nút khác và nút cuối cùng được kết nối với một con trỏ Null. Mỗi nút Bao gồm hai trường một là dữ liệu và trường kia là tiếp theo. trường dữ liệu chứa giá trị của nút đó, liệu tiếp theo có chứa địa chỉ của nút tiếp theo hay không. Nút cuối cùng chứa địa chỉ của con trỏ null.
Có ba loại danh sách liên kết.
- Danh sách liên kết đơn
- Danh sách liên kết hình tròn
- Danh sách được liên kết gấp đôi
Danh sách liên kết đơn là một loại danh sách được liên kết trong cấu trúc dữ liệu là một hướng có nghĩa là nó chỉ có thể được duyệt theo một hướng duy nhất. Trong một danh sách đơn hàng có thể có nhiều nút kết nối với nhau. nút cuối cùng của một liên kết đơn được kết nối với một con trỏ NULL. Nút đầu tiên của danh sách liên kết đơn được kết nối với một con trỏ bắt đầu luôn trỏ đến vị trí bắt đầu. Phần tiếp theo của mỗi nút chứa địa chỉ của nút khác.
Danh sách liên kết đơn-hình ảnh của tác giả
Chúng ta có thể Thực hiện Hai loại hoạt động trong một Danh sách liên kết duy nhất.
1. Chèn
2. Xóa
Chèn vào một danh sách được liên kết duy nhất
Chèn nghĩa là thêm một nút mới vào danh sách liên kết. Trong một danh sách liên kết đơn, một nút có thể được thêm vào danh sách liên kết theo ba cách.
- Ở cuối [nối thêm]
- Lúc bắt đầu [thêm trước]
- Ở một vị trí cụ thể
NODE FIELD NODE FIELD OPERATION D NEXT NULL BREAK ##Break Connection D NEXT E DATA ADD ##ADD a new Connection E NEXT NULL ADD
Insertion At Last-Image By Author
NODE FIELD NODE FIELD OPERATION START A DATA BREAK ##Break Connection E NEXT A DATA ADD ##ADD a new Connection START E DATA ADD
Insertion At Start- Image By Author
NODE FIELD NODE FIELD OPERATION A NEXT E DATA ADD E NEXT B DATA ADD ##ADD a new Connection A NEXT B DATA BREAk ##Break Connection
Insertion After A Particular Node- Image By Author
Xóa nghĩa là xóa hoặc xóa một nút khỏi danh sách liên kết. Trong một danh sách liên kết đơn, chúng ta có thể xóa một nút theo ba cách.
- Từ cái kết
- Từ lúc bắt đầu
- Từ một vị trí cụ thể
"Xóa ở cuối hình ảnh của tác giả"
Xóa nút từ đầu cũng tương tự như xóa nút từ cuối ở đây chúng ta chỉ cần trỏ con trỏ bắt đầu đến nút thứ hai [B] và ngắt kết nối giữa A và B.
"Xóa khi bắt đầu-Hình ảnh bởi Tác giả"
Để xóa một nút khỏi một vị trí cụ thể, trước tiên chúng ta cần vị trí đó, sau đó chúng ta tạo kết nối giữa nút trước và nút tiếp theo đối với nút đó sau khi tạo kết nối, chúng ta ngắt kết nối nút từ nút trước và nút tiếp theo.
Cảm ơn vì đã đọc
Nếu bạn có bất kỳ câu hỏi nào liên quan đến mã và lời giải thích, hãy hỏi tôi trong phần bình luận.
Python cũng tuyệt vời như bạn. Hãy hạnh phúc và lan tỏa Hạnh phúc
MÃ ĐẦY ĐỦ
Đã đăng vào thg 4 18, 2019 1:57 SA 2 phút đọc
1. Linked List là cái gì?
Linked List là tập hợp các nodes được liên kết với nhau. Node sau chứa link đến node trước
2. Đặc điểm chính:
Ưu điểm:
- Tiết kiếm bộ nhớ và cấp phát động: Không như array cần 1 lượng chỉ định ô nhớ trên bộ nhớ ngay khi khỏi tạo. Linked list chỉ sử dụng bộ nhớ để lưu trữ khi dữ liệu thực sự được lưu vào linked list.
- Nó còn có thể lưu các phần tử ở bất cứ đâu được phép trên bộ nhớ mà không cần các ô nhớ liền kề nhau như array
- Quick insertion [Thêm rất nhanh với complexity chỉ là O[1]]
- Quick deletion [Xóa nhanh]
Nhược điểm
- Slow search [Tìm kiểm chậm do phải duyệt qua nhiều node để đến được node cần tìm]
3. Thực hiện tạo linked list trên python
Đầu tiên ta tạo 1 class nodes trên python:
class Node:
def __init__[self,data]:
self.data = data #Đây là dữ liệu mà ta sẽ lưu trữ trong mỗi node
self.next = None #Đây là con trỏ trỏ đến node tiếp theo trong linked list
Thử set dữ liệu cho các node bằng tay:
node1 = Node["Java"]
node2 = Node["Python"]
node3 = Node["C++"]
node1.next = node2
node2.next = node3
# Ta sẽ được linked list dạng như: Java -> Python -> C++
Hàm push để thêm dữ liệu cho linked list
def push[head, valuetoInsert]:
currentNode = head
while currentNode is not None:
if currentNode.nextNode is None:
currentNode.nextNode = linkedListNode[valuetoInsert]
return head
currentNode = currentNode.nextNode
Thử tạo hàm duyệt các phần tử của linked list:
class Node:
...
def traverse[self]:
node = self # Xác định node đầu tiên hay còn gọi là head node
while node != None:
print node.data # in ra dữ liệu
node = node.next # tiếp tực đến node tiếp theo
Ngoài ra ta còn có Double Linked List [Danh sách liên kết đôi]
class DoublyNode:
def __init__[self, data]:
self.data = data
self.next = None
self.prev = None
-> Điểm khác nhau của double linked list và linked list chính là mỗi node của DLL vừa có chứa con trỏ đến node tiếp theo vừa chứa con trỏ đến node trước nó.
4. Độ phức tạp thuật toán của linked list
Với n là số phần tử của linked: - Thêm một phần tử vào sau danh sách: O[n] do phải duyệt hết các ptử để lấy node ở đuôi - Thêm một phần tử ở đầu danh sách: O[1] - Duyệt qua tất cả các phần tử O[n] - Xóa 1 phần tử: Trường hợp xấu nhất là O[n] và tốt nhất là O[1] ## Tài liệu tham khảo: //medium.com/@kojinoshiba/data-structures-in-python-series-1-linked-lists-d9f848537b4d
All rights reserved