Một danh sách được tạo từ cons ô. Từ số R5RS list section:
Đối tượng trong các trường liên tiếp của danh sách là các thành phần của danh sách. Ví dụ: danh sách hai phần tử là một cặp có ô tô là phần tử đầu tiên và có cdr là cặp có ô tô là phần tử thứ hai và có cdr là danh sách trống. Độ dài của một danh sách là số lượng các phần tử, giống như số lượng các cặp.
Ví dụ, danh sách (a b c) là tương đương với các dòng sau đây của cặp: (a . (b . (c .())))
Và có thể được đại diện trong bộ nhớ bằng các "nút" như sau:
[p] --> [p] --> [p] --> null
| | |
|==> a |==> b |==> c
Với mỗi nút [] có chứa một con trỏ p với giá trị (đó là car) và một con trỏ khác đến phần tử tiếp theo (đó là cdr).
Điều này cho phép danh sách phát triển đến độ dài không giới hạn, nhưng yêu cầu hoạt động ref để bắt đầu ở đầu danh sách và đi qua các phần tử k để tìm danh sách được yêu cầu. Như bạn đã nói, đây là O (n).
Ngược lại, một vector về cơ bản là một mảng các giá trị có thể được biểu diễn như trong nội bộ một mảng của con trỏ. Ví dụ, các vector #(a b c) có thể được biểu diễn như:
[p p p]
| | |
| | |==> c
| |
| |==> b
|
|==> a
Trong trường hợp mảng [] chứa một loạt ba con trỏ, và mỗi con trỏ được gán cho một giá trị trong vector. Vì vậy, nội bộ bạn có thể tham khảo phần tử thứ ba của vectơ v bằng cách sử dụng ký hiệu v[3]. Vì bạn không cần phải đi qua các phần tử trước, vector-ref là một hoạt động O (1).
Điểm bất lợi chính là vectơ có kích thước cố định, vì vậy nếu bạn cần thêm nhiều phần tử hơn vectơ có thể giữ, bạn phải phân bổ một vectơ mới và sao chép các phần tử cũ vào vectơ mới này. Điều này có khả năng có thể là một hoạt động tốn kém nếu ứng dụng của bạn thực hiện điều này một cách thường xuyên.
Có rất nhiều tài nguyên trực tuyến - bài viết này trên Scheme Data Structures đi vào chi tiết hơn và đưa ra một số ví dụ, mặc dù nó là nhiều hơn nữa tập trung vào danh sách.
Tất cả những gì đã nói, nếu phím của bạn (hoặc có thể trở thành) số nguyên và bạn có thể có một số cố định của các yếu tố hoặc có thể quản lý với một số lượng hợp lý của tái phân bổ vector - ví dụ, bạn tải các vector lúc khởi động và sau đó thực hiện chủ yếu là đọc - một vector có thể là một thay thế hấp dẫn cho một danh sách liên kết.
Cảm ơn bạn đã cho tôi biết về bảng băm. –
Chấp nhận câu trả lời này muộn một chút, nhưng hey. –