Danh sách liên kết có phải là ADT hay là cấu trúc dữ liệu hay cả hai?

Question

Nếu tôi sử dụng định nghĩa chuẩn của Kiểu dữ liệu trừu tượng làm hộp đen cung cấp một số chức năng để quản lý tập hợp dữ liệu, Danh sách được liên kết phù hợp với mô tả đó:

Vùng chứa cung cấp chức năng thêm (x) và nhận (i) (trong số những người khác) có thể được sử dụng để duy trì một danh sách các đối tượng.

Nhưng khi bạn đặt câu hỏi, mức độ phức tạp thời gian của các hoạt động này là gì, sau đó bạn nhận ra điều đó phụ thuộc vào cách thùng chứa này được thực hiện:

Nếu bạn chỉ trong nội bộ duy trì một liên kết đến nút đầu, ở trên hai thao tác sẽ thực hiện trong thời gian O (n). Nếu bạn duy trì thêm một liên kết đến nút đuôi, bạn sẽ nhận được O (1) thời gian trên cả hai.

Vì vậy, câu hỏi của tôi là, vì mục đích học tập, bạn có xem Danh sách liên kết là ADT hay Cấu trúc dữ liệu không?

Câu hỏi này xuất hiện khi tôi cố gắng triển khai Stack ADT từ Hướng dẫn thiết kế thuật toán của Skiena và đọc về hiệu suất của phương thức (x) và get() tùy thuộc vào cấu trúc dữ liệu nào được chọn thực hiện nó. Cuốn sách nói trong trường hợp này nó không quan trọng quá nhiều nếu bạn chọn một mảng hoặc một cấu trúc dữ liệu danh sách liên kết để thực hiện ADT này, cả hai đều cung cấp hiệu năng tương tự.

Nhưng phải không? Nó không phụ thuộc vào cách danh sách liên kết đó được thực hiện? Có rất nhiều cách để tự thực hiện danh sách liên kết, vì vậy thực tế đó không chỉ làm cho nó trở thành một ADT khác?

Answer 1

Từ Wikipedia trên ADT: In computing, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior như vậy, danh sách liên kết là một ADT, và mỗi ADT cũng là một cấu trúc dữ liệu, danh sách để liên kết là cả hai.

EDIT:
Tuy nhiên, thông báo rằng đơn lẻ-danh sách liên kết, và gấp đôi-linked-list, cả hai đều có các hoạt động tương tự và mức độ phức tạp tương tự cho các hoạt động này, vì vậy họ là cả một danh sách ADT liên kết, và chúng tôi không phân biệt giữa chúng như ADT có liên quan. Nhưng chúng là những cấu trúc dữ liệu khác nhau!

Answer 2

Bản thân danh sách được liên kết không phải là trừu tượng, nó cụ thể. Nó được coi là một cấu trúc dữ liệu. Thời gian phức tạp của việc truy cập dữ liệu trong một danh sách liên kết sẽ phụ thuộc vào yếu tố truy cập của bạn và có bao nhiêu phần tử trong danh sách, vì bạn phải lặp qua chúng để đến phần tử mong muốn của bạn.

http://en.wikipedia.org/wiki/Linked_list

Answer 3

Danh sách liên kết là ADT.

Khi bạn nói về cấu trúc dữ liệu, bạn có cơ bản - Ngăn xếp, Hàng đợi và Danh sách (Đừng gọi danh sách liên kết này), Cây vv

Khi bạn đang đặt câu hỏi về danh sách liên kết, nó là một ADT. Một kiểu dữ liệu trừu tượng. Vì vậy, độc lập nó không có giá trị. Nhưng khi bạn muốn một danh sách hoặc một ngăn xếp hoặc một hàng đợi được thực hiện, bạn cần phải sử dụng một danh sách liên kết hoặc mảng.

Tóm tắt vì nó có nhiều thao tác có thể được liên kết với nó khi cần thiết và tùy thuộc vào loại triển khai.

Danh sách trong Thư viện mẫu chuẩn của C và C++ triển khai Danh sách được liên kết đôi. Danh sách liên kết đã luôn được sử dụng trong việc triển khai Danh sách và đó là lý do tại sao nó trở nên đồng nghĩa với cấu trúc dữ liệu Danh sách.