Tìm hiểu Cấu trúc dữ liệu #2: Bên trong danh sách liên kết

Bài trước chúng ta có nói tới LinkedList (danh sách liên kết hay “danh sách móc nối”) được tổ chức đặc biệt, không giống như cấu trúc mảng. Vậy nó được tổ chức như thế nào? Bài này sẽ đi sâu vào tìm hiểu cấu trúc bên trong của danh sách liên kết, đồng thời rút ra một số kết luận cho việc sử dụng cấu trúc dữ liệu này trong xây dựng các chương trình.

Danh sách là cấu trúc dữ liệu đơn giản, nhưng cũng có nhiều cách thức tổ chức khác nhau cho từng mục đích sử dụng. Có thể kể đến: dùng mảng tĩnh (Array), mảng động với interface dạng danh sách (ArrayList, Vector) và danh sách liên kết (LinkedList).

Cách đơn giản nhất để tổ chức một danh sách các phần tử là dùng mảng. Đây là CTDL đơn giản nhất có sẵn trong hầu hết các ngôn ngữ lập trình hiện đại, có khả năng lưu trữ một dãy cố định các phần tử (có thể là các giá trị primitive hoặc object).

Tuy có sẵn và dễ dùng nhưng mảng bị giới hạn số lượng phần tử chứa trong danh sách. Khi bạn khởi tạo với boundary là 20 thì Array chỉ có khả năng chứa được 20 phần tử trong mảng, không hơn. Hơn nữa, trong trường hợp muốn chèn một phần tử vào giữa mảng, có thể ta sẽ phải dịch chuyển một số lượng lớn các phần tử đứng sau. Chuyện tương tự cũng xảy ra với thao tác xoá một phần tử nào đó trong danh sách. Ưu điểm cơ bản của danh sách dạng Array (bao gồm kiểu dữ liệu mảng, và các lớp wrapper kiểu mảng là ArrayList và Vector) là nhanh, và tiện. Bạn có thể truy xuất ngẫu nhiên các phần tử để thao tác trên đối tượng đó. Tuy vậy, kiểu tổ chức này có một nhược điểm cố hữu là không cho phép bạn kéo dài danh sách ra (boundary phụ thuộc vào lần khởi tạo đầu tiên). Trong trường hợp cần đưa thêm một phần tử, cần copy Array sang một vùng nhớ mới rộng hơn, gây lãng phí bộ nhớ và CPU.

Vì các lí do đó, LinkedList (DSLK) được dùng như là một sự lựa chọn nữa để khắc phục các nhược điểm trên của Array.

Ta có thể mường tượng DSLK như là một chuỗi (chain) các nút (node) được móc nối (link) với nhau:

Trong đó, DSLK có một nút đặc biệt là đầu (head) – đánh dấu điểm bắt đầu; và một nút đuôi (tail)-đánh dấu điểm kết thúc của danh sách. Chúng cũng được gọi là nút đầu tiên (First), và nút cuối cùng (Last).

Nút (node) – thành phần hạt nhân của mỗi danh sách

Tổ chức của mỗi nút bao gồm hai thành phần cơ bản: phần dữ liệu (data) và phần tham chiếu tới phần tử tiếp theo (next):

Phần data có thể đơn giản là số nguyên, có thể là một string hoặc cũng có thể là một object bất kì. Phần next chính là chìa khoá để tạo lập sự liên kết giữa các phần tử trong mảng (các nút – Node). Biến next sẽ trỏ tới một nút khác (là một đối tượng kiểu Node) và xác lập sự liên kết giữa hai nút. Dưới đây là một số ví dụ về các nút:

Cấu trúc đầu tiên có thể được dùng để lưu trữ mã số các quốc gia tạo thành một danh sách các mã số điện thoại quốc gia; cấu trúc thứ hai là một nút trong danh sách các tên của sinh viên; còn cái thứ ba có thể chứa thông tin chi tiết về một người (person). Đây chính là phần dữ liệu (data) như trong mô tả ở trên. Điểm chung của cả ba cấu trúc này là có phần next có kiểu chính là Node. Với cấu trúc như vậy, đối tượng Node này có thể móc nối vào một đối tượng Node khác

Thực sự thì next sẽ đóng vai trò quan trọng như thế nào?

Cấu tạo danh sách

Quan sát danh sách được tạo từ các nút được mô tả ở trên trong hình dưới đây:

Bằng cách móc nối các nút lại với nhau thông qua next, xác lập được một chuỗi các đối tượng “có liên quan” được “dính” lại với nhau . Nhờ next, ta biết rằng có sinh viên ‘Mạnh’ đứng sau ‘An’ trong danh sách, và ‘Bush’ đứng cuối cùng. Đó là cách một danh sách được hình thành.

Trong Java, next chính là một biến tham chiếu (reference variable). Việc next trỏ tới object nào sẽ quy định object đó có mặt tiếp theo trong danh sách. Nhờ yếu tố này, danh sách mà chúng ta nhìn thấy ở trên được gọi là danh sách liên kết. Người ta còn gọi danh sách như trên là danh sách tự tham chiếu, vì mỗi phần tử của nó tự xác định phần tử tiếp theo.

Để dễ theo dõi ta sẽ xem một danh sách sinh viên được tạo thành như thế nào từ các cấu trúc Node thứ hai ở trên. Quan sát hình dưới đây:

Như vậy, với đối tượng node1, node2, node3 ta đã có thể tạo lập được một danh sách liên kết. Chìa khoá ở đây chính là dùng next để trỏ đến phần tử đứng sau trong danh sách.

Song, vấn đề cơ bản của cấu trúc dữ liệu còn bao gồm một việc quan trọng khác: cho phép thao tác (operate) những gì trên cấu trúc dữ liệu đó. Để cài đặt một danh sách liên kết, ta cần một lớp đóng vai trò người quản lý các thành phần của nó bao gồm các chức năng cơ bản như thêmsửaxóa phần tử vàokhỏi danh sách, chèn vào giữa, tìm phần tử trong danh sách, duyệt các phần tử, v.v.. Đó chính là lớp LinkedList mà bạn thường nhìn thấy trong các Collection Framework. Sau đây ta sẽ khảo sát chi tiết các thao tác cơ bản của DSLK.

Thao tác trên danh sách liên kết

Như thấy ở trên, việc tạo lập một danh sách như trên là tương đối nhiêu khê. Tuy nhiên, như sẽ thấy dưới đây, sự phức tạp đó sẽ mang lại nhiều lợi ích rõ rệt.

Tôi muốn thêm một sinh viên vào danh sách thì sao?

Chuyện đó hết sức đơn giản. Chỉ cần khởi tạo một node mới, đặt vào vị trí cần thiết. Ta sẽ không gặp phải vấn đề giới hạn kích thước như trong Array, cũng không lo tới việc phải dịch chuyển các phần tử trong danh sách. Việc thêm thắt chưa bao giờ dễ hơn thế!

Chỉ cần trỏ next đến nơi cần đến (ví dụ đưa next của ‘An’ vào ‘Đông’, rồi trỏ next của ‘Đông’ đến ‘Mạnh’), thế là xếp được một sinh viên mới vào danh sách:

Tương tự, việc xoá một phần tử khỏi danh sách cũng đơn giản không kém:

Di chuyển các liên kết, ta sẽ đạt được mục đích. Bằng cách gán next của phần tử cần xoá tới null, gắn lại mối kết nối vừa bị đứt (như hình trên, móc ‘An’ vào ‘Mạnh’).

Chỉ mỗi việc duyệt DSLK là hơi khó chịu một chút:

Để tìm một nút trong danh sách, ta thực hiện việc duyệt các nút trong danh sách. Từ nút đầu tiên, ta lần theo các nút tiếp theo nhờ liên kết next- chính next sẽ chỉ cho ta người tiếp theo trong danh sách. Cho tới khi next trỏ tới null, hoặc khi tìm thấy nút cần tìm, ta sẽ kết thúc việc tìm kiếm. Đây là đặc trưng cơ bản của việt duyệt tuần tự (sequential), bạn không thể truy xuất ngẫu nhiên (ngay lập tức) được, mà phải rất từ từ: bạn muốn tìm thấy “Mạnh”, thì phải đi qua nhà “An”, “Đông” trước đã. Và cứ lần nào tìm kiếm như thế, bạn cũng phải bắt đầu từ “head”, nếu không có cách gì khác.

Để tiện lợi hơn cho việc duyệt qua danh sách, có hai cải tiến đáng kể: một là thêm một liên kết nữa cho mỗi nút: previous, khi đó danh sách sẽ là loại DSLK đôi (Doublely Linked List) – cách này cho phép bạn tiến-lùi thoải mái hơn; hai là đặt thêm vào cấu trúc LinkedList một lớp phụ trợ (utility class) có tên Iterator để giúp việc duyệt qua danh sách tiện lợi hơn, đỡ tránh sai sót (như đề cập ở bài trước), và hỗ trợ vòng lặp for-each. Iterator là một mẫu thiết kế được sử dụng phổ biến trong thiết kế các Collection Framework do tính ưu việt của nó: trừu tượng hóa cách thức  duyệt qua các phần tử trong kiểu tập hợp (collecion) mà vẫn cho phép tối ưu hóa cách duyệt đặc thù cho từng kiểu CTDL. Chúng ta sẽ bàn kĩ về mẫu thiết kế (design pattern) này sau. Trong LinkedList, iterator của mỗi danh sách sẽ đánh dấu phần tử đang duyệt (current), giống như một con trỏ (cursor) để tiếp tục việc duyệt mà không cần phải quay lại duyệt từ đầu trong các lần duyệt tiếp theo, nhờ đó tiết kiệm thời gian duyệt phần tử hơn.

Lưu ý: như bài trước có đề cập tới tình trạng dở khóc dở cười khi ta dùng hàm get(i) từ một đối tượng LinkedList. Thực ra đây là một lỗi thiết kế của JDK vì LinkedList thừa kế List nên nó thừa kế cả hàm get(i) của List (một số cấu trúc khác cũng vướng phải vấn đề này). Ta biết rằng việc truy xuất kiểu tuần tự như thế là không phù hợp trong một số trường hợp (như duyệt hết danh sách chẳng hạn). Vì thế, để cho ‘lành’, ta sử dụng for-each để tận dụng ưu việt của việc duyệt theo iterator mỗi khi gặp phải một collection mà không chắc nó được cấu trúc ra sao.

Mở rộng DSLK

LinkedList có thể được dùng làm Stack, Queue (như trong Java, LinkedList được cài đặt với một số hàm để phù hợp với cấu trúc hàng đợi và ngăn xếp), tuy nhiên, còn tùy sự lựa chọn cài đặt cho từng bài toán cụ thể. Ngoài ra, LinkedList cũng có thể được mở rộng để tạo ra các danh sách nhảy cóc (Skip List), và danh sách dạng vòng (Circular List) với nhiều ưu điểm phù hợp với một số bài toán đặc thù.

Cấu trúc Node có thể dùng để làm thành các phần tử của cây (Tree), đặc biệt với cây tìm kiếm nhị phân (Binary Search Tree). Ta sẽ xem xét các cấu trúc dữ liệu này sau.

Cuối cùng, vậy khi nào thì dùng LinkedList?

Căn cứ các hiểu biết về cấu trúc như trên, ta có thể rút ra một số kết luận mang tính lí thuyết về việc khi nào thì nên dùngkhông nên dùng danh sách liên kết.

Nên dùng DSLK:

1. Khi cần xóachèn liên tục (trong các ứng dụng real-time chẳng hạn)
2. Khi bạn không biết collection có bao nhiêu phần tử (boundary không rõ ràng), đặc biệt lại là khi bộ nhớ hữu hạn không cho phép bạn thực hiện các biện pháp clone dữ liệu trên mảng.
3. Khi bạn không có nhu cầu truy xuất ngẫu nhiên vào phần tử nào
4. Khi bạn rất hay muốn chèn một phần tử vào giữa danh sách (như trong cài đặt các hàng đợi ưu tiên – priority queue – chẳng hạn).

Trong các trường hợp khác, có thể bạn sẽ ưa thích dùng mảng (Array, ArrayList) hơn:

1. Khi cần (thường xuyên) truy xuất ngẫu nhiên
2. Số lượng phần tử trong collection là xác định
3. Khi bạn cần duyệt qua thật nhanh tất cả các phần tử trong danh sách
4. Muốn tiết kiệm bộ nhớ (vì dùng LinkedList bạn sẽ tốn một ít overhead cho việc tổ chức các liên kết next, previous và Iterator)

Chuyện về LinkedList đến đây đã có phần hơi dài, mặc dù còn nhiều cái hay để bàn tiếp. Nhưng như thế chắc cũng đủ để hiểu về cấu trúc của LinkedList rồi. Chúng ta tạm thời ngưng ở đây để cùng chuyển sang một cấu trúc dữ liệu cực kì căn bản: ngăn xếp (Stack). Hãy chú ý tới phần phụ lục dưới đây như là một bài tập để thử nghiệm, điều đó sẽ giúp bạn đào sâu hơn về LinkedList.

Phụ lục: Tự cài đặt LinkedList

Bạn có thể tự cài LinkedList để hiểu hơn về cấu trúc dữ liệu này. Dưới đây là đoạn code mẫu cài đặt hoàn chỉnh một danh sách liên kết đơn. Bạn thử mở rộng thành DoubleLinkedList và cài đặt Iterator cho nó (interface này có tại java.util) xem hiệu quả thế nào. Cũng đừng quên thí nghiệm với các thao tác tìmthêmsửaxóa trên các cấu trúc bạn cài đặt nhé. Thử so sánh với ArrayList(hay Vector) xem thế nào. Nếu bạn quan tâm đến performance, thì code cái giả định của bạn đi, và để Profiler cho bạn biết kết quả.

[sourcecode language=”java”]

/**
* Node in a generic singly linked list class
*/
public class Node<T> {
public T data;
public Node<T> next;
public Node() {
next = null;
}

public Node(T el) {
data = el; next = null;
}

public Node(T el, Node<T> ptr) {
data = el; next = ptr;
}
}

/**
* A singly linked list implementation with basic operations
*/
public class LinkedList<T> {
protected Node<T> head, tail;
public LinkedList () {
head = tail = null;
}

public boolean isEmpty() {
return head == null;
}

/**
* Other operational methods are listed in next slides
*/
public void printAll() {
for (Node <T> tmp = head; tmp != null; tmp = tmp.next)
System.out.print(tmp.data + " ");
}

public boolean isInList(T el) {
Node <T> tmp;
for (tmp = head; tmp != null &amp;&amp; tmp.data != el; tmp = tmp.next);
return tmp != null;
}

/**
* addXXX methods
*/

public void addToHead(T el) {
head = new Node <T>(el,head);
if (tail == null)
tail = head;
}

public void addToTail(T el) {
if (!isEmpty()) {
tail.next = new Node <T>(el);
tail = tail.next;
}
else head = tail = new Node<T>(el);
}
/**
*delete the head and return its info
*/
public T deleteFromHead() {
if (isEmpty())
return null;
T el = head.data;

if (head == tail) // if only one node on the list;
head = tail = null;
else head = head.next;
return el;
}
/**
* delete the tail and return its info
*/
public T deleteFromTail() {
if (isEmpty())
return null;
T el = tail.data;
if (head == tail) // if only one node in the list;
head = tail = null;
else { // if more than one node in the list,
Node <T> tmp; // find the predecessor of tail;
for (tmp = head; tmp.next != tail; tmp = tmp.next);
tail = tmp; // the predecessor of tail becomes tail;
tail.next = null;
}
return el;
}

/**
* delete the node with an element el
*/

public void delete(T el) {
if (!isEmpty())
if (head == tail &amp;&amp; el == head.data) // if only one
head = tail = null; // node on the list;
else if (el == head.data) // if more than one node on the list;
head = head.next; // and el is in the head node;
else { // if more than one node in the list
Node <T> pred, tmp;// and el is in a nonhead node;
for (pred = head, tmp = head.next; tmp != null &amp;&amp; tmp.data != el; pred = pred.next, tmp = tmp.next);
if (tmp != null) { // if el was found;
pred.next = tmp.next;
if (tmp == tail) // if el is in the last node;
tail = pred;
}
}
}
}
[/sourcecode]