So sánh danh sách liên kết và mảng năm 2024
Mảng và danh sách liên kết đều là cấu trúc dự liệu phổ biến trong ngôn ngữ lập trình. Dưới đây là các điểm khác nhau giữa mảng và danh sách liên kết Mảng Danh sách liên kết Vùng nhớ của các phần tử trong mảng được sắp xếp liên tục nhau Vùng nhớ của các phần tử trong danh sách liên kết được sắp xếp tùy ý (do hệ điều hành). Các phần tử lưu 1 con trỏ trỏ tới phần tử tiếp theo. Truy cập tới phần tử trong mảng là truy cập trực tiếp dựa vào chỉ số (ví dụ: a[0], a[1], a[2],…, a[n]) Cần phải duyệt tuần tự khi muốn truy cập tới phần tử trong danh sách liên kết.
Ở phần 1, bọn mình đã ôn lại một số khái niệm như Big-O Notation, Time và Space Complexity rồi. Bạn nào chưa đọc thì đọc lại mới hiểu được trong phần 2 này nha. Trong phần này, tụi mình sẽ ôn lại những cấu trúc dữ liệu rất cơ bản như Array, LinkedList, Stack and Queue nha! Mình sẽ giải thích sơ về độ phức tạp, ứng dụng của chúng, cũng như những bài toán các bạn hay gặp với các cấu trúc dữ liệu này nhé. Các bạn tham khảo độ phức tạp của các operation của các CTDL này trong ảnh dưới. Lâu lâu đang đọc mà quên cứ kéo lên xem lại nhé! Array (Mảng) – Người bạn thân thuộc của lập trình viênĐộ phức tạp Về bản chất, 1 array là 1 vùng nhớ, gồm nhiều phần tử nằm liền kề nhau. Dựa vào index i và địa chỉ của phần tử đầu tiên, ta có thể dễ dàng tính ra địa chỉ của phần thử thứ i. Do vậy, ta có thể truy xuất dữ liệu tại vị trí thứ (i) trong array với độ phức tạp (time complexity) là O(1). Khi array còn chỗ trống, ta cũng có thể dễ dàng thêm phần tử vào array. Thế nhưng, khi array đã đầy, ta không thể thêm phần tử mới. Muốn thêm, ta phải tìm 1 vùng nhớ lớn có thể chứa toàn bộ phần tử, copy toàn array cũ, cộng thêm phần tử mới qua vùng nhớ đó. Do vậy, thao tác thêm khi array đã đầy sẽ có time complexity và space complexity là O(n). Khi muốn xoá cũng vậy, ta phải bỏ phần tử đó, dồn các phần tử phía sau lên 1 vị trí nên cũng tốn O(n) luôn. Ứng dụng Array là một cấu trúc dữ liệu cực kì quen thuộc, học từ trước cả môn cấu trúc dữ liệu. Array được dùng hàng ngày trong công việc, khi ta muốn lưu trữ 1 danh sách nhiều phần tử. Các thuật toán cơ bản như tìm kiếm, sắp xếp đều sử dụng trên array cả. Note nhẹ: Trong C#, class List cũng sử dụng Array để lưu trữ. Khi array bị đầy, nó sẽ tạo 1 array khác có dung tích gấp đôi array hiện tại, để hạn chế số lần cần tạo array mới. Một số bài toán hay gặp:
Tham khảo việc làm NodeJS hấp dẫn trên TopDev Linked List (Danh sách liên kết)Độ phức tạp Như đã nói ở phần trên, nhược điểm của array là thêm phần tử mới khá lâu. Do vậy, người ta sáng tạo ra Linked List. Mỗi phần tử trong Linked List sẽ có 1 con trỏ, trỏ tới phần tử phía sau nó, khi muốn thêm phần tử ta chỉ việc cho phần tử cuối (tail) trỏ tới phần tử mới là được, khi muốn xoá cũng vậy. Do vậy độ phức tạp chỉ là O(1). Bù lại, việc truy cập sẽ tốn thời gian hơn. Do ta không biết phần tử thử (n) nằm ở đâu, ta phải duyệt qua n phần tử để tìm phần tử đó, time complexity là O(n). Ứng dụng LinkedList được dùng khi lưu trữ một danh sách có số lượng phần tử không cố định (dynamic), cần thêm và xoá phần tử. Nếu biết trước số lượng phần tử là cố định, không cần xoá thì cứ dùng array sẽ nhanh hơn. Linked List có 2 biến thể là Single-linked list và Double-linked list. Với Double-linked list thì 1 phần tử sẽ lưu 2 con trỏ, trỏ về phía trước và phía sau. Tuy tốn bộ nhớ hơn nhưng truy cập tiện hơn. Một số bài toán hay gặp:
Cặp bài trùng Stack (Ngăn xếp) và Queue (Hàng đợi)Độ phức tạp
Hai cấu trúc dữ liệu này cho phép ta thêm/xoá các phần tử dựa theo thứ tự đưa vào, mà không cần phải lưu trữ thời gian. Độ phức tạp của việc đưa vào/lấy ra đều là O(1). Ứng dụng
Một số bài toán hay gặp
Tạm kếtCác bạn thấy đấy, 4 cấu trúc dữ liệu trong bài này đều có độ phức tạp O(n) khi tìm kiếm. Để tìm 1 phần tử, ta sẽ phải duyệt qua toàn bộ các phần tử chứa trong mảng/linked-list/stack/queue. Ở phần sau, mình sẽ giới thiệu về 1 CTDL bá đạo có thể tìm kiếm với độ phức tạp O(1) mang tên HashTable; cùng 1 số những CTDL hay ho nhưng ít gặp như Tree hay Graph nhé! |