Mảng và Danh sách liên kết

Mảng và danh sách liên kết là hai cách cơ bản để lưu trữ một chuỗi các phần tử có thứ tự: mảng đặt chúng trong bộ nhớ liền kề để truy cập theo chỉ mục với thời gian không đổi, trong khi danh sách liên kết xâu chuỗi chúng thông qua các con trỏ để chèn và xóa với chi phí thấp.

Definition

Một mảng lưu trữ các phần tử trong các vị trí bộ nhớ liền kề được lập chỉ mục theo vị trí, cho phép truy cập ngẫu nhiên với thời gian không đổi; một danh sách liên kết lưu trữ các phần tử trong các nút riêng biệt, mỗi nút giữ một tham chiếu đến nút tiếp theo (và có thể là nút trước đó), cho phép chèn hoặc xóa với thời gian không đổi khi có tham chiếu nút.

Scope

Chủ đề này bao gồm các cấu trúc tuyến tính, dựa trên chuỗi và các kiểu dữ liệu trừu tượng được xây dựng trên chúng — mảng tĩnh và động, danh sách liên kết đơn và đôi, và các ADT ngăn xếp và hàng đợi. Nó đối chiếu chi phí truy cập, chèn và xóa của chúng, đề cập đến việc thay đổi kích thước mảng động và phân tích khấu hao của nó, đồng thời giải thích các hậu quả về bố cục bộ nhớ như tính cục bộ của bộ nhớ đệm (cache locality). Nó không bao gồm các cấu trúc liên kết và phân cấp được đề cập trong bảng băm và cây tìm kiếm.

Core questions

• Khi nào lưu trữ liền kề (mảng) vượt trội hơn lưu trữ liên kết con trỏ (danh sách)?
• Làm thế nào một mảng động đạt được việc nối thêm với thời gian không đổi được khấu hao mặc dù thỉnh thoảng phải thay đổi kích thước?
• Những đánh đổi về chi phí của mảng so với danh sách liên kết đối với việc chèn, xóa và truy cập là gì?
• Ngăn xếp và hàng đợi được triển khai như thế nào trên các cấu trúc này?
• Bố cục bộ nhớ ảnh hưởng đến hiệu suất thực tế thông qua hành vi bộ nhớ đệm như thế nào?

Key concepts

• bộ nhớ liền kề
• truy cập theo chỉ mục
• thay đổi kích thước mảng động
• danh sách liên kết đơn và đôi
• ngăn xếp (LIFO)
• hàng đợi (FIFO)
• chi phí khấu hao
• tính cục bộ của bộ nhớ đệm

Key theories

Truy cập ngẫu nhiên so với liên kết tuần tự

Mảng hỗ trợ truy cập theo chỉ mục O(1) nhưng chèn hoặc xóa ở giữa là O(n), trong khi danh sách liên kết hỗ trợ nối O(1) khi có một nút nhưng truy cập theo vị trí là O(n); lựa chọn đúng phụ thuộc vào sự kết hợp các thao tác.

Tăng trưởng khấu hao của mảng động

Một mảng động tăng gấp đôi dung lượng khi đầy sẽ thực hiện các bản sao O(n) không thường xuyên nhưng khấu hao thành O(1) cho mỗi lần nối thêm trong bất kỳ chuỗi thao tác nào, bằng phương pháp tổng hợp hoặc tiềm năng.

Clinical relevance

Mảng và danh sách là nền tảng của gần như mọi chương trình: mảng động triển khai các kiểu danh sách/vector mặc định trong hầu hết các ngôn ngữ, hàng đợi là cơ sở của việc lập lịch và tìm kiếm theo chiều rộng, ngăn xếp là cơ sở của việc quản lý cuộc gọi hàm và đánh giá biểu thức, và sự đánh đổi giữa mảng và danh sách là một quyết định thiết kế thực tế thường xuyên ảnh hưởng đến hiệu suất.

History

Mảng là một trong những cấu trúc dữ liệu sớm nhất, có mặt trong các ngôn ngữ lập trình đầu tiên, và danh sách liên kết được giới thiệu để xử lý ký hiệu và danh sách (đáng chú ý trong IPL của Newell, Shaw và Simon và sau đó là Lisp) vào cuối những năm 1950. Cách xử lý có hệ thống của Knuth trong The Art of Computer Programming đã thiết lập phân tích chuẩn của chúng.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

Tại sao lại sử dụng danh sách liên kết nếu mảng hỗ trợ truy cập ngẫu nhiên nhanh?

Danh sách liên kết cho phép chèn hoặc xóa trong thời gian không đổi khi có tham chiếu đến một nút, mà không cần dịch chuyển các phần tử khác, điều mà mảng không thể làm ở giữa. Chúng hữu ích khi chuỗi thay đổi thường xuyên và không cần truy cập ngẫu nhiên theo vị trí.

Tại sao việc nối thêm mảng được coi là thời gian không đổi nếu việc thay đổi kích thước sao chép mọi thứ?

Việc thay đổi kích thước hiếm khi xảy ra vì dung lượng thường tăng gấp đôi, do đó tổng công việc sao chép trên n lần nối thêm tỷ lệ thuận với n. Chia đều cho tất cả các lần nối thêm, điều này mang lại chi phí không đổi được khấu hao cho mỗi lần nối thêm mặc dù các lần thay đổi kích thước riêng lẻ là O(n).