định nghĩa cấu trúc dữ liệu dạng danh sách(list)

Mảng và danh sách liên kết là hai cấu trúc dữ liệu lâu đời và được sử dụng phổ biến nhất hiện nay. Chúng đều hỗ trợ người dùng trong việc tổ chức dữ liệu, giúp việc tìm kiếm và lưu trữ trở nên dễ dàng hơn. Trong bài viết này chúng ta cùng tìm hiểu những điểm khác biệt giữa mảng và danh sách liên kết, từ đó có thể áp dụng chúng trong những tình huống thích hợp.

1. Khái niệm

Array là gì?

+ Mảng là một trong những cấu trúc dữ liệu cũ và quan trọng nhất, hầu hết các chương trình đều dùng nó. Các cấu trúc dữ liệu khác cũng được hiện thực dựa trên mảng, thí dụ nhưdanh sách hoặc chuỗi.

+ Cấu trúc dữu liệu mảng chứa các giá trị hay biến có cùng kiểu dữ liệu, ví dụ như integer hay string. Mỗi phần tử trong mảng đều được gán với một giá trị index riêng. Mảng thường được sử dụng trong các chương trình máy tính giúp tổ chức dữ liệu giúp việc lưu trữ và tìm kiếm dữ liệu dễ dàng hơn.

+ Mảng gồm có mảng một chiều và mảng đa chiều.

định nghĩa cấu trúc dữ liệu dạng danh sách(list)

LinkedList là gì?

+ Linked list hay danh sách liên kết là một dang cấu trúc dữ liệu tuyến tính trong đó các phần tử được liên kết với nhau nhờ các links, mỗi phần tử bao gồm phần chứa dữ liệu và phần liên kết đến phần tử kế tiếp. Phần tử cuối cùng của danh sách liên kết sẽ trỏ đến giá trị NULL để đánh dấu điểm cuối.

+ Tương tự như mảng, linkedlist được sử dụng phổ biến để tổ chức dữ liệu hỗ trợ cho việc lưu trử và tìm kiếm dữ liệu.

+ Có 3 loại là danh sách liên kết đơn, danh sách liên kết đôi và danh sách liên kết xoay vòng.

định nghĩa cấu trúc dữ liệu dạng danh sách(list)

2. Khác biệt giữa array và linkedlist

  • Cấu trúc:

Mảng được xây dựng dựa trên chỉ mục, ở đó mỗi phần tử trong mảng được gắn với một chỉ mục (index) cố định. Trước khi truy xuất 1 phần tử cần biết được index của nó. Index có thể bắt đầu từ 0 hoặc 1 tùy vào từng ngôn ngữ lập trình.

Trong khi đó các phần tử của danh sách liên kết được liên kết theo thứ tự, chúng liên kết với phần tử đứng trước và đứng sau nó, khi muốn truy xuất một phần tử trong danh sách liên kết ta cần truy xuất các phần tử liền kề nó trước.

  • Kích thước:

Mảng yêu cầu một kích thước cố định trong quá trình khai báo chúng, khi số lượng phần tử vượt quá kích thước đó mảng cần được resize.

Danh sách liên kết không gặp bất cứ vấn đề gì về kích thước, chúng linh hoạt trong việc thay đổi kích thước và việc này diễn ra ngay trong quá trình chương trình thực thi.

  • Bộ nhớ:

Danh sách liên kết yêu cầu lượng bộ nhớ nhiều hơn so với mảng bởi một phần lí do là chúng yêu cầu thêm một lượng bộ nhớ cho việc liên kết/tham chiếu đến phần tử liền kề.

Mảng yêu cầu bộ nhớ trong quá tình biên dịch còn danh sách liên kết yêu cầu bộ nhớ trong quá trình chạy chương trình.

Các phần tử của mảng được lưu trữ tại các vị trí kề nhau trong vùng nhớ Stack. Trong khi đó các phần tử trong linkedlist lưu trữ tại các vị trí ngẫu nhiên trong vùng nhớ Heap.

  • Thời gian truy xuất phần tử:

Đối với mảng, bạn có thể truy xuất trực tiếp hoặc truy xuất tuần tự từng phần tử, ví dụ khi truy xuất phần tử thứ 4 của một mảng trong ngôn ngữ C ta cần biết index của nó là 3 và viết theo dạng array[3].

Với danh sách liên kết ta bắt buộc phải truy xuất tuần tự và phải bắt đầu truy xuất từ phần tử đầu tiên.

Do đó có thể thấy rằng việc truy xuất phần tử trong mảng nhanh và đơn giản hơn so với danh sách liên kết.

  • Thêm và xóa phần tử:

Việc thêm hay xóa phần tử trong mảng phúc tạp hơn nhiều so với danh sách liên kết bởi vì khi thêm một phần tử vào giữa mảng ta cần dịch chuyển các phần tử đằng sau nó để tạo vị trí trống. Ví dụ thêm số 4 vào vị trí thứ 5 trong mảng {0,1,2,3,5,6,7, null, null, null} thì ta cần xê dịch 5,6,7 ra sau 1 index để tạo khoảng trống cho số 4 -> {0,1,2,3,4,5,6,7, null, null}.

Với danh sách liên kết muốn thêm hay xóa một phần tử ta chỉ cần thay đổi liên kết của phần tử đứng trước và đứng sau vị trí muốn thêm hay xóa.

  • Ưu điểm của linkedlist so với array: kích thước linh hoạt, dễ dàng thêm và xóa phần tử, không yêu cầu cấp phát trước bộ nhớ.
  • Ưu điểm của array so với linkedlist: truy xuất ngẫu nhiên, lượng bộ nhớ yêu cầu thấp, dễ thực thi và sử dụng.

Lời kết

Như vậy mình và các bạn đã tìm hiểu về 2 loại cấu trúc dữ liệu mảng và danh sách liên kết cũng như sự khác nhau của chúng. Mỗi cấu trúc đều mang những ưu và nhược điểm riêng, không có một cấu trúc dữ liệu nào có thể phục vụ đầy đủ tất cả các nhu cầu của người dùng, vì vậy việc nắm rõ sự khác biệt giữa chúng giúp lập trình viên biết sử dụng những cấu trúc dữ liệu thích hợp trong các tình huống khác nhau. Cảm ơn bạn đọc, chúc bạn thành công trên con đường học tập!