nhập môn danh sách liên kết

Lâm Tùng viết ngày 21/09/2019

Cũng giống như mảng,danh sách liên kết là một cấu trúc dữ liệu tuyến tính.Không giống như mảng,các phần tử của danh sách liên kết không được lưu trữ tại các vị trí liên kề;các phần tử của danh sách liên kết được liên kết với nhau bằng con trỏ(pointers).

Tại sao cần DSLK

Mảng có thể lưu trữ tuyến tính các dữ liệu có cùng kiểu nhưng mảng có những hạn chế sau:

• Kích thước của mảng là cố định.do vậy chúng ta cần phải biết trước số phần tử tối đa của mảng.Nên bộ nhớ được dùng bằng số phần tử tối đa của mảng không phân biệt sử dụng hay không sử dụng
• Chèn phần tử mới vào trong mảng không rỗng là rất tốn kém bởi vì chúng ta cần phải tạo không gian cho phần tử mới và để tạo không gian cho phần tử mới thì không gian của các phần tử trước cũng phải thay dổi. Ví dụ, trong một hệ thống nếu chúng ta muốn duy trì một danh sách đã sắp xếp của ids trong một mảng có tên là id[]. id[] =[1000, 1010, 1050, 2000, 2040].