Điểm của lớp SplDoublyLinkedList của PHP là gì và quan trọng hơn là các Danh sách Liên kết nói chung là gì?

Question

Trên một nhiệm vụ để mở rộng khả năng lập trình của tôi, tôi đã từng xóa một chút vào The Standard PHP Library. Điều này dẫn đến khám phá của tôi về lớp học SplDoublyLinkedList. Từ đó tôi đọc phần mô tả của Linked Lists và Doubly Linked Lists trên Wikipedia.

Tôi hiểu cách thức hoạt động ... Nhưng tôi không thể quan niệm lý do TẠI SAO chúng tôi cần nó — hoặc tốt hơn là ví dụ thực tế của SplDoublyLinkedList vì chúng tôi đã lập chỉ mục và mảng liên kết trong PHP.

Danh sách được liên kết thường được sử dụng trong và ngoài PHP như thế nào?

Answer 1

Cấu trúc dữ liệu SPL giảm mức tiêu thụ bộ nhớ và cải thiện hiệu suất. Giải thích tốt:

Cấu trúc dữ liệu vốn vốn không độc lập về ngôn ngữ và tồn tại dưới dạng tập hợp các khái niệm logic dựa trên toán học. Các thùng chứa này sử dụng các thuật toán khác nhau phù hợp để tối đa hóa hiệu quả.

Ví dụ, nếu bạn không cần khả năng bản đồ băm của một mảng kết hợp - nghĩa là, nếu bạn không sử dụng khóa mảng cho một mục đích cụ thể và chỉ cần một mảng được liệt kê - SplFixedArray (trước đây SplFastArray, hiện không có giấy tờ) có thể là một sự thay thế phù hợp. Thông báo trước duy nhất là kích thước của mảng được cố định, nghĩa là bạn phải chỉ định kích thước khi bạn khởi tạo lớp và một lỗi sẽ xảy ra nếu bạn cố gắng lưu trữ nhiều hơn số lượng phần tử đó. Đây là lý do, trung bình, nó hoạt động tốt hơn so với các mảng PHP chuẩn.

http://web.archive.org/web/20130805120049/http://blueparabola.com/blog/spl-deserves-some-reiteration

Trong đoạn code C tạo nên các thông dịch viên PHP, mảng được thực hiện như một cấu trúc dữ liệu gọi là một bảng băm hoặc bản đồ băm. Khi một giá trị chứa trong một mảng được tham chiếu bởi chỉ mục của nó, PHP sử dụng hàm băm để chuyển đổi chỉ mục đó thành một băm duy nhất biểu diễn vị trí của giá trị tương ứng trong mảng đó.

Việc triển khai bản đồ băm này cho phép các mảng lưu trữ một số phần tử tùy ý và cung cấp quyền truy cập vào tất cả các phần tử đó cùng một lúc bằng cách sử dụng các phím số hoặc chuỗi. Mảng rất nhanh cho các khả năng mà chúng cung cấp và là một cấu trúc dữ liệu mục đích chung tuyệt vời.

Trong khoa học máy tính, danh sách được định nghĩa là tập hợp các giá trị được sắp xếp. Danh sách được liên kết là một cấu trúc dữ liệu trong đó mỗi phần tử trong danh sách bao gồm một tham chiếu đến một hoặc cả hai phần tử ở hai bên của nó trong danh sách. Thuật ngữ "danh sách liên kết kép" được sử dụng để chỉ trường hợp sau. Trong SPL, điều này có dạng của lớp SplDoublyLinkedList .... Nó có ý nghĩa khi sử dụng các danh sách khi số lượng các phần tử được lưu trữ không được biết trước và các phần tử chỉ cần được truy cập theo vị trí tuần tự.

http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/

Answer 2

Theo Để Wikipedia,

Lợi ích chủ yếu của một danh sách liên kết trên một mảng thông thường là thứ tự các mặt hàng liên quan có thể khác với thứ tự mà các dữ liệu mục được lưu trữ trong bộ nhớ hoặc trên đĩa. Vì lý do đó, danh sách được liên kết cho phép chèn và xóa các nút tại bất kỳ số nào trong danh sách, với số hoạt động không đổi.

Mặt khác, danh sách được liên kết theo số không cho phép truy cập ngẫu nhiên vào dữ liệu hoặc bất kỳ hình thức lập chỉ mục hiệu quả nào. Do đó, nhiều thao tác cơ bản - chẳng hạn như lấy nút cuối cùng của danh sách hoặc tìm một nút mà chứa một mốc cụ thể hoặc định vị nơi một nút mới cần được chèn vào - có thể yêu cầu quét nhiều nhất của danh sách các yếu tố.

Vì vậy, để trả lời câu hỏi của bạn, tôi không biết. :)

Answer 3

Họ đang ở đó vì nhiều người lập trình đến từ các ngôn ngữ khác được sử dụng cho họ nơi mảng có kích thước cố định và bạn phải quản lý bộ nhớ.
Vì vậy, đối với PHP, chúng chỉ là một công cụ khác. Chúng được triển khai bởi vì nhiều thuật toán & chuyển tiếp mẫu trên danh sách và do đó chúng không cần phải được thay đổi thành các mảng php.

Answer 4

Như những người khác đã đề cập, Danh sách là một thay thế cho mảng cố định mà được phổ biến trong các ngôn ngữ khác. Nhưng một khía cạnh quan trọng thường bị bỏ qua - bạn có thể chèn hoặc loại bỏ một phần tử từ bất kỳ vị trí nào trong danh sách rất hiệu quả.

Tại sao điều này lại quan trọng? Giả sử bạn có một số mục mà bạn muốn duy trì được sắp xếp trong một mảng, có lẽ vì vậy bạn không phải sắp xếp chúng sau này hoặc chỉ để giảm thiểu thời gian tìm kiếm. Trong trường hợp này một List có thể là một công cụ rất mạnh. Đặc biệt là cho bộ dữ liệu rất lớn.

Answer 5

Trước hết, SplDoublyLinkedList là các đối tượng, như vậy

• họ có thể được mở rộng, vì vậy bạn có thể ghi đè lên các phương pháp của họ (bạn có thể ví dụ như trả lại toàn bộ chuỗi uppercased, vv)
• các giao diện chúng triển khai có thể được kiểm tra như trong myfunc(SplDoublyLinkedList $var) ...
• chúng được chuyển làm tham chiếu theo mặc định
• v.v.

Thứ hai, SplDoublyLinkedList chấp nhận chế độ lặp, do đó bạn có thể xóa các mục của bạn trên đường đi, và hướng chuyển đổi mà không cần sắp xếp lại mảng hoặc làm phức tạp mã của bạn:

SplDoublyLinkedList :: IT_MODE_LIFO (Kiểu ngăn xếp)

SplDoublyLinkedList :: IT_MODE_FIFO (Kiểu xếp hàng) Hành vi của trình lặp vòng (một hoặc người kia)

SplDoublyLinkedList :: IT_MODE_DELETE (Elements được xóa bởi iterator)

SplDoublyLinkedList :: IT_MODE_KEEP (Elements nằm ngang iterator)

Báo giá trên là từ http://simpletechinfo.com/SplDoublyLinkedList có chứa một số mẫu mã.

Có đặc quyền khác (như foreach không phải làm một bản sao trong bộ nhớ của tất cả các dữ liệu, vv)

Answer 6

Bạn đang có lẽ đúng, và nó chỉ là không phải là rất hữu ích.

Có nhiều cách sử dụng danh sách được liên kết trong lý thuyết (đáng chú ý là các liên kết khiêu vũ). Nhưng hầu hết trong số họ liên quan đến việc lưu trữ và sao chép các trình lặp của nó ở nơi khác, truy cập nội dung theo nhiều hơn hai hướng, hoặc tách và hợp nhất các danh sách. SplDoublyLinkedList dường như không có.

Nếu không phải là thuật toán, một lần sử dụng là cho phép đối tượng xóa tham chiếu của chính nó trong một danh sách trong thời gian không đổi, giải phóng bộ nhớ và không xáo trộn danh sách (băm hoặc hoán đổi mục cuối cùng) sau khi chèn hoặc xóa. Nhưng điều này đòi hỏi phải lưu trữ một iterator của danh sách trong các đối tượng đó.

Nếu không có các chức năng đó, chúng sẽ hoạt động giống như hai lần bị khử. Nếu bạn chỉ cần truy cập các mục bằng cách sử dụng trình lặp, chúng giống như hai ngăn xếp. Một cách tốt hơn trong các trường hợp đơn giản luồng đơn, chặn không được gói trong một lớp, chỉ sử dụng hai ngăn xếp (có thể là mảng cố định hoặc cả hai đầu của cùng một mảng). Pop từ một ngăn xếp và đẩy nó đến một nơi khác bất cứ khi nào bạn muốn iterator để di chuyển, và trên cùng của một ngăn xếp là mục hiện tại. Nếu bạn cũng cần phải truy cập vào đầu và đuôi, bạn sẽ cần phải thay thế các ngăn xếp với deques. Tuy nhiên, nếu bạn muốn thực hiện các ngăn xếp hoặc tự xóa bản thân mà không biết kích thước tối đa hoặc thậm chí phân bổ các nút của danh sách được liên kết bình thường (bằng ngôn ngữ không có thư viện như trong PHP), cách tốt nhất là chuỗi một số mảng cố định cùng nhau, sử dụng danh sách được liên kết kép mà không có các tính năng đó. Bằng cách nào đó bạn vẫn sẽ cần nó.

Tài liệu PHP chính nó, giống như Java, cho thấy chúng được cho là chỉ là một deque hỗ trợ một số tính năng kỳ lạ, thậm chí không hai deques (tôi nghĩ). Không sử dụng chúng nếu bạn thực sự cần danh sách liên kết gấp đôi.