8

[DataStructure] Linked List

Linked list ( danh sách liên kết ) là một cấu trúc dữ liệu tuyến tính. Giống như tên của nó, danh sách liên kết ( DSLK ) là tập hợp các Node được liên kết với nhau bằng con trỏ. Mỗi Node sẽ chứa data và các biến để chứa địa chỉ trỏ tới Node tiếp theo (Single Linked List) hoặc sẽ có thêm biến để lưu vị trí con trỏ có Node trỏ tới trước đó ( Double Linked List)

Linked List ví dụ đơn giản nhất của cấu trúc dữ liệu cây, hiểu và implement được DSLK để các bạn có thể dễ dàng tìm hiểu thêm các kiểu dữ liệu cây sau này.

Single Linked List:

 Linked list ( danh sách liên kết đơn) Linked list ( danh sách liên kết đơn)
✧ ✧ ✧

Double Linked List:

danh sách liên kết đôidanh sách liên kết đôi

Như vậy đối với DSLK bạn chỉ cần nhớ vị địa chỉ của phần tử đầu tiên của nó ( Head ) là bạn có thể truy cập được tất cả các phần tử trong danh sách. Đối với Double Linked list thì chỉ cần địa chỉ của một phần tử bất kì trong danh sách.

✧ ✧ ✧

Khi bạn cài đặt một array ở ngôn ngữ hướng hệ thống như C/C++, array phải có chiều dài cố định và chiếm một vùng nhớ stack hoặc heap ( sẽ là heap nếu khởi tạo với keyword new ), các phần tử trong array sẽ nằm liền kề nhau.

Array location in memory (source : beginner book)Array location in memory (source : beginner book)

Đối với  DSLK sẽ không có chiều dài cố định ( nếu có chỉ là việc bạn giới hạn việc thêm các Node vào Linked List) và các phần tử trong DSLK cũng sẽ không nằm liền kề nhau. Các phần tử trong Linked List nằm rải rác ở bộ nhớ trong RAM, và chúng được truy cập nhờ vào việc lưu lại địa chỉ của nhau.

Linked list in memory Linked list in memory
✧ ✧ ✧

Đâu là giới hạn của một Linked List

Có thể nói chiều dài của DSLK là không giới hạn, nếu như bạn không cài đặt chiều dài tối đa cho một DSLK, vậy giới hạn ở đây là gì?

Giới hạn ở đây là khi chương trình không cho bạn tạo một Node mới mà thôi. Còn việc thêm Node vào DSLK chỉ là việc link Node đó với các Node có trong DSLK.

Ưu điểm:

Dynamic array: chiều dài của array thường bị cố định trong lúc khởi tạo, qua đó dẫn đến những hạn chế trong quá trình sử dụng. Có những trường hợp khởi tạo một array cố định mà không sử dụng hết tại thời điểm khởi tạo sẽ gây lãng phí bộ nhớ.

Insert/Delete performace: chi phí để thêm/xoá 1 Node trên Linked List chỉ là O(1)

Nhược điểm:

Không thể random access tới một vị trí bất kì trên danh sách liên kết.  Làm sao để  QuickSort trên DSLK ?

Bộ nhớ phát sinh để lưu lại địa chỉ trên mỗi Node.

Không thân thiện cho việc caching trên CPU. Đối với array các phần tử được lưu liên tục thành một block trên RAM. CPU dễ dàng thực hiện việc tính toán và caching dựa vào việc thay đổi offset giữa các phần tử.

Ứng dụng:

Dựa vào tính chất của danh sách liên kết, thì một số dứng dụng của DSLK như:

  • Danh sách nghe nhạc (next/back)
  • Image View (next/back)
  • Browser (next/back)
  • Undo/Redo
  • Xử lý đụng độ trong Hash Table
  • Implement  Stack ( add Head && pop Head)
  • Implement Queue ( add Head && pop Tail)
  • ........
✧ ✧ ✧

Implement Linked List

Khởi tạo:

  Thêm phần tử vào DSLK:

Pop/Shift:

Tìm kiếm phần tử:

Tạo một DSLK và thêm các phần tử vào:

Full code:

✧ ✧ ✧

Mình xin dừng bài viết ở đây. Ngoài ưu và nhược, bạn đã sử dụng DSLK cho những trường hợp hay ho nào ngoài những case trên thì shared mình với nha.

Tham khảo:

Updated:

Nếu các bạn React Developer đang sử dụng Redux cho ứng dụng của mình, update lên version react-redux@7.2 sẽ có một improve đó là sử dụng linked list để quản lý component connect 

This algorithm has been replaced with tracking subscribers via a linked list, which drastically improves the runtime of this section of the code even with large numbers of subscribers.

#programming#linkedlist#data structure#datastructure
8
0
...