Hướng dẫn linked list vs python list - danh sách liên kết so với danh sách python
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:
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:
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): Chúng ta có thể thấy ở đây chúng ta có các thuộc tí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 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:
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): 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 def insert(self, data): 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. def find(self, val): 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): 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à 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 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 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 def insert(self, data):0 như sau: def get_count(self): Đ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 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 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 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! def is_empty(self): 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ư:
Đ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! Danh sách được liên kết có nhanh hơn danh sách Python không?Danh sách mảng nhanh hơn (danh sách Python) hầu hết thời gian, trong khi danh sách được liên kết sẽ gần hơn (và nhanh hơn) chỉ trong phạm vi 1% để bắt đầu danh sách (A = vòng (I / 99)). Vì vậy, mặc dù danh sách Python cần thay đổi tất cả các mục theo mục đã xóa, nhưng nó vẫn nhanh hơn.linked list gets closer (and faster further) only within 1% length to the list start ( a = round(i / 99) ). So even though Python list needs to shift all the items following the deleted item, it's still faster.
Danh sách nào tốt hơn hoặc danh sách được liên kết?Trong hầu hết các trường hợp, danh sách hữu ích hơn. LinkedList sẽ có ít chi phí hơn khi thêm/xóa các mục ở giữa danh sách, trong khi danh sách chỉ có thể thêm/xóa giá rẻ ở cuối danh sách.List
Tại sao Python không có danh sách liên kết?Python không xuất xưởng với loại dữ liệu danh sách được liên kết tích hợp theo nghĩa cổ điển của người Hồi giáo. Loại danh sách của Python được triển khai như một mảng động, điều đó có nghĩa là nó không phù hợp với các kịch bản điển hình mà bạn muốn sử dụng cấu trúc dữ liệu danh sách liên kết phù hợp với các lý do hiệu suất.. Python's list type is implemented as a dynamic array—which means it doesn't suit the typical scenarios where you'd want to use a “proper” linked list data structure for performance reasons.
Tại sao bạn sẽ sử dụng một danh sách được liên kết trong Python?Bạn nên sử dụng danh sách được liên kết qua một mảng khi: Bạn không biết có bao nhiêu mục trong danh sách (đó là một trong những lợi thế - dễ dàng thêm các mục).Bạn không cần truy cập ngẫu nhiên vào bất kỳ phần tử nào (không giống như một mảng, bạn không thể truy cập một phần tử ở một chỉ mục cụ thể trong danh sách được liên kết).You don't know how many items will be in the list (that is one of the advantages - ease of adding items). You don't need random access to any elements (unlike an array, you cannot access an element at a particular index in a linked list).
Danh sách được liên kết có nhanh hơn danh sách không?Nó phụ thuộc vào những gì bạn đang cố gắng thực hiện.Nếu bạn muốn tìm kiếm hoặc truy cập một phần tử cụ thể, các mảng sẽ nhanh hơn, nhưng nếu bạn muốn chèn hoặc xóa một phần tử, một danh sách được liên kết sẽ nhanh hơn.if you want to insert or delete an element, a linked list is faster.
Sự khác biệt giữa mảng và danh sách được liên kết trong Python là gì?Trong trường hợp của một mảng, kích thước bộ nhớ được cố định và không thể thay đổi nó trong thời gian chạy. Trong danh sách được liên kết, vị trí của các phần tử được phân bổ trong thời gian chạy. In the linked list, the placement of elements is allocated during the run time. |