[Imperative Programming + C] Bài 18 - Simplicity DSA List (tiếp theo)

Trở lại với những lý do đã khiến chúng ta đã khởi đầu tìm hiểu về List, dung lượng lưu trữ thiếu linh động của các mảng Array chỉ là một phần nhỏ bởi trong phần nhiều trường hợp sử dụng lưu trữ tập hợp dữ liệu thì chúng ta đều có thể tiên đoán được khoảng số lượng giá trị cần lưu trữ. Trường hợp mà Array thực sự thể hiện giới hạn đó là khi chúng ta cần xóa đi hoặc thêm một phần tử mới vào vị trí bất kỳ trong mảng.

Lúc này nếu như chúng ta đang có mảng dữ liệu chứa 1001 bản ghi thì có thể sẽ xuất hiện những trường hợp thao tác mà chúng ta sẽ phải di chuyển 1000 bản ghi bằng thao tác copy để lấp khoảng trống cho bản ghi đã xóa hoặc tạo khoảng trống cho bản ghi mới được chèn vào giữa mảng. Ở điểm này thì List lại có thể giúp chúng ta lược bỏ thao tác copy để dịch chuyển dữ liệu giữa các ô nhớ void*, và giảm thiểu rủi ro tạo ra logic hoạt động không đúng mong muốn.

Insert

Giả sử chúng ta có một List chứa 10,000 bản ghi dữ liệu, và cần chèn thêm một bản ghi mới vào vị trí sau bản ghi thứ 1,000. Việc chúng ta cần làm là truy xuất Item thứ 1,000, sau đó chỉ định ra các yếu tố:

• Item $item là phần tử mới sẽ được chèn vào List.
• Item $prev là phần tử thứ 1,000 vừa truy xuất.
• Item $next là phần từ thứ 1,001 ở thời điểm trước khi chèn thêm phần tử mới vào List.

Sau đó gỡ bỏ liên kết giữa $prev và $next để thiết lập lại các liên kết mới với $item được gắn vào giữa. Như vậy chúng ta sẽ có các liên kết gắn $prev với $item là:

• $prev->next = $item
• $item->prev = $prev

Và các liên kết gắn $item với $next:

• $item->next = $next
• $next->prev = $item

Tất cả các phần tử khác đang có mặt trong List đều không phải nhận thao tác ảnh hưởng nào và vì vậy số lượng thao tác xử lý trên tập dữ liệu rất ít, đồng thời có logic rất dễ kiểm soát.

Delete

Thao tác xóa đi một phần tử đang có mặt trong List cũng được thực hiện với các thao tác định vị các yếu tố và thiết lập lại các liên kết như vậy:

• Item $item là phần tử đã định vị được trong List để xóa đi
• Item $prev là phần tử đứng ngay trước $item và chúng ta có $prev = $item->prev
• Item $next là phần tử đứng ngay sau $item và chúng ta có $next = $item->next

Đối với các phần tử $prev và $next chúng ta cần gỡ bỏ các liên kết cũ với $item và thiết lập lại các liên kết mới để gắn $prev và $next với nhau:

• $prev->next = $next
• $next->prev = $prev

Oh.. tuy nhiên lúc này có một câu hỏi mới là các thao tác chèn bản ghi mới và xóa bản ghi đang có trong List vừa rồi lại thường xuất hiện khi chúng ta cần làm việc với các trị số chỉ vị trí của một bản ghi nào đó trong List. Như vậy là sẽ có những thời điểm nhất định, chúng ta sẽ cần sử dụng tới một cấu trúc dữ liệu có sự linh động của List về mặt cấu trúc lưu trữ và đồng thời cần được hỗ trợ bởi tính năng làm việc với các phần tử bằng trị số chỉ vị trí index của Array. Và khi kết hợp các yếu tố này thì chúng ta có một cấu trúc dữ liệu mới được gọi là Vector, hay ArrayList.

Vector (ArrayList)

Trong một số ngôn ngữ lập trình khác, điển hình là Java thì người ta sử dụng cả tên Vector và ArrayList để phân biệt tính năng quản lý tài nguyên đối với lập trình đa nhiệm. Mặc dù có bản chất lưu trữ và logic xử lý tương đồng nhưng ArrayList có thể được truy xuất bởi tất cả các tiến trình chạy code thread tại một thời điểm và không đảm bảo rằng kết quả hoạt động được đồng bộ giữa các thread, và cái tên Vector được sử dụng để lấp vào khoảng trống đó.

Ở đây chúng ta sẽ chưa phải quan tâm tới vấn đề xử lý đa nhiệm trên một tập dữ liệu và vì vậy Vector và ArrayList có ý nghĩa giống nhau như đã nói. Và có lẽ tới thời điểm hiện tại thì chúng ta có thể phỏng đoán thiết kế mảng Array của JavaScript thực ra là Vector bởi khả năng lưu trữ với dung lượng linh động của List và giao diện lập trình tương tác qua các trị số chỉ vị trí của Array.

Tuy nhiên, để triển khai kiến trúc lưu trữ của Vector thì chúng ta cũng sẽ cần phải thực hiện qua một vài bài viết và điều đó cũng không hẳn cần thiết. Ở đây chúng ta đã có thể nhìn thấy logic lưu trữ sau khi đã hiểu về việc phân bổ bộ nhớ cấp thấp của Array và List. Điểm đáng quan tâm hơn đối với mình lúc này là: Tại sao các ngôn ngữ Functional lại sử dụng List làm cấu trúc lưu trữ tập hợp chủ đạo thay vì Array như các ngôn ngữ Procedural phổ biến?

[Imperative Programming + C] Bài 19 - Simplicity DSA List (tiếp theo)