Tại sao phải triển khai danh sách không thể thay đổi dưới dạng danh sách được liên kết?

Question

Theo F # 's listdocumentation:

• "Một danh sách trong F # là một lệnh, bất biến loạt các yếu tố cùng loại"

• "Lists trong F # được thực hiện như các danh sách được liên kết đơn lẻ "

Tại sao không thực hiện nó liên tục trong bộ nhớ vì nó không thay đổi và do đó có kích thước cố định? Tại sao lại sử dụng F # list thay vì F # array?

Answer 1

Họ phục vụ các mục đích khác nhau, ví dụ:

Bạn sử dụng một mảng trong F # để lưu trữ một lượng lớn dữ liệu cần phải được truy cập một cách ngẫu nhiên với chi phí tương đối thấp.

Danh sách trong F # rất hữu ích khi bạn cần tích luỹ thứ gì đó qua các lần lặp lại của hàm đệ quy. Mảng không chơi tốt ở đây, vì chúng có kích thước cố định.

Với list, bạn có thể thêm tất cả các phần tử của ListM (cỡ M) vào ListN (cỡ N) trong thời gian O (M). Tương tự, bạn có thể thêm một phần tử đơn vào danh sách bất kỳ trong thời gian O (1).