Làm thế nào để triển khai một danh sách được liên kết trong Python?

Ngôn ngữ lập trình Python là một ngôn ngữ mã nguồn mở với nhiều cách triển khai khác nhau giúp nó trở nên độc đáo và dễ học hơn. Mặc du không hỗ trợ khái niệm về danh sách được liên kết, có một cách xung quanh nó thông qua một triển khai khác để có được danh sách được liên kết. Trong bài viết này, chúng ta sẽ tìm hiểu cách tạo danh sách liên kết trong Python. Sau đây là các chủ đề được đề cập trong blog này:

• Danh sách liên kết là gì?
• Triển khai danh sách được liên kết
• Phương thức của danh sách liên kết

Hãy bắt đầu nào!!

Danh sách liên kết là gì?

Danh sách liên kết là một chuỗi các nút có kiểu dữ liệu giống nhau, mỗi nút chứa một đối tượng dữ liệu và con trỏ đến nút tiếp theo.

Danh sách liên kết là một cấu trúc dữ liệu tuyến tính với sự tập hợp của nhiều nút. Đâu ePhần tử ach lưu trữ dữ liệu của chính nó và một con trỏ đến vị trí của phần tử tiếp theo. Liên kết cuối cùng trong danh sách được liên kết trỏ đến null, cho biết phần cuối của chuỗi. Một phần tử trong danh sách liên kết được gọi là nút . Nút đầu tiên được gọi là cái đầu .Nút cuối cùng được gọi làcác đuôi .
Thư viện python chuẩn không có danh sách liên kết. Chúng ta có thể triển khai khái niệm cấu trúc dữ liệu danh sách liên kết bằng cách sử dụng khái niệm các nút.

Bây giờ chúng ta đã tìm hiểu về những gì được Liên kết. Vì vậy, hãy chuyển sang triển khai Danh sách được liên kết.

Triển khai danh sách được liên kết

Để tạo Danh sách liên kết, chúng ta tạo một đối tượng nút và tạo một lớp khác để sử dụng đối tượng nút này.
Mã tạo lớp Node.
Chương trình trên tạo một danh sách liên kết với ba phần tử dữ liệu.

class Node (object): # Constructor để khởi tạo các biến lớp def __init __ (self, data = None, next_node = None): self.data = data self.next_node = next_node #get data def get_data (self): return self.data # nhận giá trị tiếp theo def get_next (self): return self.next_node # set dữ liệu tiếp theo def set_next (self, new_next): self.next_node = new_next

Triển khai danh sách liên kết bao gồm chức năng sau trong danh sách liên kết
một. Chèn : Phương thức này sẽ chèn một nút mới trong danh sách liên kết.
2. Kích thước : Phương thức này sẽ trả về kích thước của danh sách liên kết.
3. Tìm kiếm : Phương thức này sẽ trả về một nút chứa dữ liệu, nút khác sẽ phát sinh lỗi
Bốn. Xóa bỏ : Phương thức này sẽ xóa một nút chứa dữ liệu, nếu không sẽ phát sinh lỗi

Cho phép xem danh sách Phương thức được liên kết

triển khai hàng đợi ưu tiên trong java

Init phương thức trong danh sách liên kết

class LinkedList (đối tượng): def __init __ (self, head = None): self.head = head

Phương thức Init được sử dụng để khởi tạo một lớp học nếu danh sách không có nút, nó được đặt thành không.

Chèn:

def insert (self, data): new_node = Node (data) new_node.set_next (self.head) self.head = new_node

Phương thức chèn này lấy dữ liệu, khởi tạo một nút mới với dữ liệu đã cho và thêm nó vào danh sách. Về mặt kỹ thuật, bạn có thể chèn một nút vào bất cứ đâu trong danh sách, nhưng cách đơn giản nhất để làm điều đó là đặt nó ở đầu danh sách và trỏ nút mới vào đầu cũ (kiểu đẩy các nút khác xuống dòng).

Kích thước

# Trả về tổng số nút trong kích thước định dạng danh sách (self): current = self.head count = 0 while current: count + = 1 current = current.get_next () return count

Phương pháp kích thước rất đơn giản, về cơ bản nó đếm các nút cho đến khi nó không thể tìm thấy nữa và trả về số lượng nút đã tìm thấy. Phương thức bắt đầu từ nút đầu, đi xuống dòng của các nút cho đến khi nó đến cuối (dòng điện sẽ là Không có khi nó đến cuối) trong khi vẫn theo dõi bao nhiêu nút mà nó đã thấy.

Tìm kiếm

sự suy nghĩ trong python là gì

# Trả về nút trong danh sách có nodeData, lỗi xảy ra nếu nút không hiện diện tìm kiếm def (self, nodeData): current = self.head isPresent = Sai khi hiện tại và isPresent là Sai: if current.get_data () == nodeData: isPresent = Đúng khác: current = current.get_next () nếu hiện tại là Không: nâng ValueError ('Dữ liệu không có trong danh sách') trả về hiện tại

Tìm kiếm thực sự rất giống với kích thước, nhưng thay vì duyệt qua toàn bộ danh sách các nút, nó sẽ kiểm tra tại mỗi điểm dừng để xem liệu nút hiện tại có dữ liệu được yêu cầu hay không. Nếu vậy, trả về nút đang giữ dữ liệu đó. Nếu phương pháp xem qua toàn bộ danh sách nhưng vẫn không tìm thấy dữ liệu, thì phương pháp này sẽ gây ra lỗi giá trị và thông báo cho người dùng rằng dữ liệu không có trong danh sách.

Xóa bỏ

# Xóa nút khỏi danh sách được liên kết trả về lỗi nếu nút không hiện diện def xóa (self, nodeData): current = self.head before = None isPresent = False khi hiện tại và isPresent là False: if current.get_data () == nodeData: isPresent = True else: before = current current = current.get_next () nếu hiện tại là Không: nâng ValueError ('Dữ liệu không có trong danh sách') nếu trước đó là Không: self.head = current.get_next () else: before.set_next ( current.get_next ())

Phương thức xóa duyệt qua danh sách theo cách tương tự như cách tìm kiếm, nhưng ngoài việc theo dõi nút hiện tại, phương thức xóa cũng ghi nhớ nút cuối cùng được truy cập. Khi xóa cuối cùng đến nút nó muốn xóa. Nó chỉ đơn giản là loại bỏ nút đó khỏi chuỗi bằng cách 'nhảy cóc' nó.

Ý tôi là khi phương thức xóa đến nút mà nó muốn xóa, nó sẽ nhìn vào nút cuối cùng mà nó đã truy cập (nút ‘trước đó’) và đặt lại con trỏ của nút trước đó. Thay vì trỏ đến nút sắp bị xóa.

kiểu dữ liệu ngày tháng trong ví dụ sql

Nó sẽ trỏ đến nút tiếp theo trong dòng. Vì không có nút nào trỏ đến nút kém đang bị xóa, nên nó sẽ bị xóa khỏi danh sách!

Điều này đưa chúng ta đến phần cuối của bài viết này, nơi chúng ta đã học cách tạo danh sách liên kết trong python với cách triển khai tương tự mặc dù python không thực sự hỗ trợ khái niệm danh sách liên kết. Tôi hy vọng bạn rõ ràng với tất cả những gì đã được chia sẻ với bạn trong hướng dẫn này.

Nếu bạn thấy bài viết này về “Danh sách được liên kết trong Python” có liên quan, hãy xem Một công ty học trực tuyến đáng tin cậy với mạng lưới hơn 250.000 người học hài lòng trải dài trên toàn cầu.

Chúng tôi ở đây để giúp bạn từng bước trong hành trình của mình và đưa ra chương trình giảng dạy được thiết kế cho sinh viên và các chuyên gia muốn trở thành . Khóa học được thiết kế để cung cấp cho bạn khởi đầu về lập trình Python và đào tạo bạn về cả khái niệm Python cốt lõi và nâng cao cùng với nhiều giống

Nếu bạn gặp bất kỳ câu hỏi nào, vui lòng đặt tất cả câu hỏi của bạn trong phần nhận xét của “Danh sách được liên kết bằng Python” và nhóm của chúng tôi sẽ sẵn lòng trả lời.