thực hiện danh sách liên kết bằng cách sử dụng mảng - ưu điểm và nhược điểm

Question

Tôi biết cách triển khai danh sách được liên kết bằng mảng. Ví dụ chúng ta định nghĩa một cấu trúc như sau:

struct Node{ 
    int data; 
    int link; 
} 

"dữ liệu" lưu trữ các thông tin và "liên kết" lưu trữ các chỉ số trong mảng của nút tiếp theo.

Ai có thể cho tôi biết lợi thế và bất lợi của việc triển khai danh sách liên kết bằng cách sử dụng mảng so với danh sách được liên kết "thông thường" là gì? Bất kỳ đề xuất nào cũng sẽ được đánh giá cao.

Answer 1

Nếu bạn quay trở lại danh sách được liên kết với một mảng, bạn sẽ kết thúc với những bất lợi của cả hai. Do đó, điều này có lẽ không phải là một cách rất tốt để thực hiện nó.

Một số nhược điểm ngay lập tức:

1. Bạn sẽ có không gian chết trong mảng (mục mà hiện không sử dụng cho các hạng mục) chiếm bộ nhớ
2. Bạn sẽ phải tiếp tục theo dõi những miễn phí mục nhập - sau một vài lần chèn và xóa, các mục nhập miễn phí này có thể ở bất kỳ đâu.
3. Sử dụng một mảng sẽ áp đặt giới hạn trên cho kích thước của danh sách được liên kết.

Tôi cho rằng một số lợi thế là:

1. Nếu bạn đang ở trên một hệ thống 64 bit, "gợi ý" của bạn sẽ chiếm ít không gian (mặc dù không gian thêm theo yêu cầu của mục miễn phí có thể giá trị hơn lợi thế này)
2. Bạn có thể nối tiếp mảng vào đĩa và đọc lại bằng một cuộc gọi mmap() dễ dàng. Mặc dù, bạn nên sử dụng một số loại bộ đệm giao thức cho tính di động.
3. Bạn có thể thực hiện một số đảm bảo về các yếu tố trong mảng đang ở gần nhau trong bộ nhớ.

Answer 2

Ai có thể cho tôi biết ưu điểm và nhược điểm của việc thực hiện các danh sách liên kết sử dụng mảng là gì so với danh sách liên kết "bình thường"?

danh sách liên kết có sự phức tạp sau:

• khuyết điểm x xs: O (1)
• append nm: O (n)
• chỉ số i xs: O (n)

nếu represe của bạn ntation sử dụng, mảng tiếp giáp nghiêm ngặt, bạn sẽ có độ phức tạp khác nhau:

• khuyết điểm sẽ yêu cầu sao chép các mảng cũ: O (n)
• append sẽ yêu cầu sao chép cả hai mảng vào một không gian tiếp giáp mới: O (n + m)
• chỉ số có thể được thực hiện như truy cập mảng: O (1)

Đó là, một danh sách API liên kết thực hiện trong nhiệm kỳ s của mảng sẽ hoạt động giống như một mảng.

Bạn có thể giảm nhẹ phần này bằng cách sử dụng danh sách được liên kết hoặc cây mảng chặt chẽ, dẫn đến dây thừng hoặc cây ngón tay hoặc chuỗi lười.

Answer 3

ngăn xếp thực hiện theo hai cách. đầu tiên trong việc sử dụng mảng và thứ hai là sử dụng danh sách liên kết.

một số disadvatages trong việc sử dụng mảng sau đó hầu hết các lập trình viên sử dụng danh sách liên kết trong triển khai ngăn xếp.

trước tiên là ngăn xếp bằng cách sử dụng danh sách được liên kết trước tiên không khai báo kích thước ngăn xếp và không giới hạn lưu trữ dữ liệu trong ngăn xếp. thứ hai là danh sách liên kết trong tiểu luận con trỏ để khai báo và sử dụng nó.

chỉ sử dụng một con trỏ trong danh sách được liên kết. nó được gọi là con trỏ trên cùng.

ngăn xếp là sử dụng phương pháp lifo. nhưng một số nhược điểm trong việc thực hiện chương trình danh sách liên kết.

Hầu hết việc triển khai chồng sử dụng lập trình viên đều sử dụng danh sách được yêu thích.

Answer 4

Sử dụng triển khai mảng, bạn có thể truy cập nhanh hơn vào các nút trong danh sách, Nếu bạn triển khai danh sách được liên kết bằng con trỏ, bạn có thể truy cập ngẫu nhiên vào các nút. Triển khai mảng là hữu ích khi bạn đang xử lý không cố định. Trong số các phần tử bởi vì việc thay đổi kích thước một mảng là tốn kém đến mức hiệu suất là có liên quan bởi vì nếu bạn được yêu cầu chèn/xóa các nút từ giữa danh sách, bạn phải thay đổi mọi nút sau đó. Trái ngược với điều này, Bạn nên sử dụng triển khai con trỏ khi bạn không biết không. của các nút bạn muốn, vì danh sách này có thể tăng/thu nhỏ hiệu quả & bạn không cần phải dịch chuyển bất kỳ nút nào, nó có thể được thực hiện bằng cách đơn giản chỉ dereferencing & tham chiếu con trỏ.