Sử Dụng Danh Sách Liên Kết Kép Trong C - E-News

Trong môn học cấu trúc dữ liệu, chúng ta đã biết đến danh sách liên kết kép. Nó là một danh sách có nhiều nút và các nút là có thứ tự. Mỗi nút là một cấu trúc gồm trường data – chứa dữ liệu của một nút và trường next – là con trỏ chỉ đến nút kế tiếp, cuối cùng là trường prev trỏ đến nút trước nó. Việc cài đặt và sử dụng danh sách này trên ngôn ngữ lập trình C/C++ là hơi khó khăn vì phải sử dụng con trỏ. Tuy nhiên nếu bạn muốn tạo danh sách liên kết kép trong C# thì bạn khỏi phải lo các thao tác cài đặt cấu trúc, khai báo các hàm vì những cái này đã được C# xây dựng sẵn thông qua class LinkedList. Cái bạn cần biết để cài đặt dạng danh sách này là hãy đọc bài giới thiệu và hướng dẫn sử dụng class này thông qua nội dung bài viết sau đây.

Như chúng ta đa biết có hai dạng danh sách liên kết kép bao gồm :

Danh sách liên kết kép bình thường

Đây là dạng danh sách liên kết kép mà nút cuối cùng của danh sách có trường next là NULL và nút đầu có trường prev cũng là NULL. (xem hình).

Danh sách liên kết kép vòng (circular doubly linked list)

Đây là dạng danh sách liên kết kép mà nút cuối có trường next chỉ về nút đầu và nút đầu có trường prev chỉ về nút cuối. (xem hình)

Tuy nhiên trong class LinkedList chỉ hỗ trợ cho bạn danh sách liên kết kép dạng bình thường mà thôi. LinkedList (danh sách liên kết kép) generic là một danh sách liên kết kép nơi mà mỗi nút trỏ sang nút kế tiếp và nút trước nó. Các nút của LinkedList có kiểu là LinkedListNode. Mỗi phần tử của LinkedListNode chứa giá trị dữ liệu của một nút và một tham chiếu đến danh sách liên kết LinkedList chứa nút đó. Bên cạnh đó mỗi phần tử LinkedListNode cũng chứa một tham chiếu dẫn đến nút kế tiếp và đến nút trước nó.

Tập hợp LinkedList thực thi các giao diện ICollection, hỗ trợ các bộ liệt kê (Enumerator) và các lớp Collection khác trong .NET Framework.

Để sử dụng tập hợp LinkedList trong chương trình, bạn hãy làm theo các bước sau đây :

1. Thêm dòng lệnh sau đây vào phần đầu chương trình

          using System.Collections.Generic;

2. Khởi tạo một tập hợp LinkedList rỗng bằng câu lệnh

LinkedList listname = new LinkedList();

Trong đó typevar là kiểu dữ liệu của một nút chẳng hạn như kiểu int hay một kiểu giá trị như string, bool,… nào đó. Trong trường hợp bạn cần sử dụng những dữ liệu phức tạp như kiểu dữ liệu thông tin sinh viên (chứa họ tên, MSSV, năm sinh, lớp),… thì bạn hãy tạo một Struct chứa các biến dữ liệu đó, sau đó sử dụng như một kiểu biến bình thường khác. Tham số listname là tên danh sách mà bạn cần đặt cho LinkedList.

Ví dụ :

LinkedList mylist = new LinkedList();

3. Để thêm các nút vào danh sách, bạn có thể sử dụng các phương thức như AddBefore, AddAfter, AddFirst, AddLast. Bạn có thể sử dụng các phương thức như Remove, RemoveFirst hay RemoveLast để loại bỏ các nút ra khỏi tập hợp.

4. Để hiển thị các giá trị của các nút trong một tập hợp, bạn có thể sử dụng vòng lặp foreach.

Ví dụ :

foreach (int element in mylist)

{

          Console.WriteLine(element);

}

Một số thuộc tính/phương thức/constructors và công dụng của nó trong class LinkedList

1. public LinkedList()

Khởi tạo một tập hợp danh sách LinkedList rỗng.

2. public LinkedList (IEnumerable collection)

Khởi tạo một tập dợp danh sách LinkedList rỗng với các phần tử thuộc một tập hợp xác định.

3. public LinkedListNode AddAfter(LinkedListNode node, T value)

Thêm một nút mới có giá trị T sau một nút xác định.

4. public LinkedListNode AddBefore(LinkedListNode node, T value)

Thêm một nút mới có giá trị T trước một nút xác định.

5. public LinkedListNode AddFirst(T value)

Thêm một nút mới có giá trị T ngay tại vị trí bắt đầu của LinkedList (phần tử đầu tiên).

6. public LinkedListNode AddLast(T value)

Thêm một nút mới có giá trị T ngay tại vị trí cuối cùng của LinkedList (phần tử cuối cùng).

7. public void Clear()

Xóa tất cả các nút ra khỏi một LinkedList

8. public bool Contains (T value)

Kiểm tra một giá trị T nào đó có nằm trong danh sách LinkedList hay không.

9. public void CopyTo (T[] array, int index)

Sao chép toàn bộ các phần tử của LinkedList sang mảng một chiều, bắt đầu tại vị trí index xác định.

10. public LinkedListNode Find (T value)

Trả về nút đầu tiên chứa giá trị T nào đó.

11. public LinkedListNode FindLast (T value)

Trả về nút cuối cùng chứa giá trị T nào đó.

12. public LinkedListNode First {get;}

Trả về nút đầu tiên trong LinkedList

13. public bool Remove (T value)

Loại bỏ nút đầu tiên có giá trị T ra khỏi LinkedList.

14. public void RemoveFirst ()

Loại bỏ nút đầu tiên ra khỏi LinkedList.

15. public void RemoveLast ()

Loại bỏ nút cuối cùng ra khỏi LinkedList.

Một số thuộc tính/constructors và công dụng của nó trong class LinkedListNode

1. public LinkedListNode (T value)

Khởi tạo một nút mới có một giá trị T nào đó.

2. public LinkedList List {get;}

Trả về đối tượng LinkedList mà nút LinkedListNode trỏ sang.

3. public LinkedListNode Next {get;}

Trả về nút kế tiếp so với nút hiện tại trong LinkedList. Trả về null nếu nút hiện tại là nút cuối cùng trong danh sách.

4. public LinkedListNode Previous {get;}

Trả về nút trước đó so với nút hiện tại trong LinkedList. Trả về null nếu nút hiện tại là nút đầu tiên trong danh sách.

5. public T Value {get; set;)

Trả về hoặc gán một giá trị được lưu trong một nút.

Ví dụ tổng quát cho hai class LinkedList và LinkedListNode

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace LinkedList

{

    class LinkedList

    {

        static void Main(string[] args)

        {

            // Tao LinkedList

            string[] words = { "Vien", "Trinh", "Bao", "Yen", "Thanh", "Thien" };

            LinkedList mylist = new LinkedList(words);

            Hienthi(mylist, "Gia tri cac nut trong LinkedList");

            Console.WriteLine("Co tu Bao trong LinkedList hay khong ? => {0}",

                mylist.Contains("Bao"));

            // Them tu 'Huy' ngay tai vi tri dau cua danh sach

            mylist.AddFirst("Huy");

            Hienthi(mylist, "Tac vu 1 : Them 'Huy' ngay tai vi tri bat dau cua danh sach : ");

            // Di chuyen nut dau tien den vi tri nut cuoi cung trong danh sach

            LinkedListNode mark1 = mylist.First;

            mylist.RemoveFirst();

            mylist.AddLast(mark1);

            Hienthi(mylist, "Tac vu 2 : Di chuyen nut dau tien den vi tri nut cuoi cung:");

            // Doi nut cuoi cung co gia tri moi la "Thanh"

            mylist.RemoveLast();

            mylist.AddLast("Thanh");

            Hienthi(mylist, "Tac vu 3 : Doi nut cuoi cung co gia tri moi la 'Thanh':");

            // Di chuyen nut cuoi cung den vi tri nut dau tien

            mark1 = mylist.Last;

            mylist.RemoveLast();

            mylist.AddFirst(mark1);

            Hienthi(mylist, "Tac vu 4 : Di chuyen nut cuoi cung den vi tri nut dau tien :");

            // Go bo nut dau tien va cho biet vi tri xuat hien cuoi cung cua tu Vien.

            mylist.RemoveFirst();

            LinkedListNode current = mylist.FindLast("Vien");

            IndicateNode(current, "Tac vu 5 : Vi tri xuat hien cuoi cung cua tu 'Vien':");

            // Them tu 'Hue' va 'Loan' sau tu 'Vien'

            mylist.AddAfter(current, "Loan");

            mylist.AddAfter(current, "Hue");

            IndicateNode(current, "Tac vu 6 : Them tu 'Hue' va 'Loan' sau tu 'Vien' :");

            // Tim nut dau tien chua tu 'Trinh'

            current = mylist.Find("Trinh");

            IndicateNode(current, "Tac vu 7 : Tim nut dau tien chua tu 'Trinh' : ");

            // Them 'Tran' va 'Ngan' truoc 'Trinh':

            mylist.AddBefore(current, "Tran");

            mylist.AddBefore(current, "Ngan");

            IndicateNode(current, "Tac vu 8 : Them 'Tran' va 'Ngan' truoc 'Trinh':");

            Console.WriteLine("Tac vu 9: Sao chep danh sach den mot mang");

            // Sao chep danh sach den mot mang co cung so phan tu    

            string[] Array = new string[mylist.Count];

            mylist.CopyTo(Array, 0);

            foreach (string s in Array)

            {

                Console.Write(s + " - ");

            }

            // Xoa sach tat ca phan tu trong danh sach

            mylist.Clear();

            Console.WriteLine();

            Console.WriteLine("Tac vu 10 : Xoa danh sach. Trong danh sach hien gio co chua tu 'Trinh' khong ? => {0}",

                mylist.Contains("Trinh"));

            Console.ReadLine();

        }

        //Ham Hienthi dung de hien thi cac phan tu trong danh sach

        private static void Hienthi(LinkedList words, string test)

        {

            Console.WriteLine(test);

            foreach (string word in words)

            {

                Console.Write(word + " ");

            }

            Console.WriteLine();

            Console.WriteLine();

        }

        // Ham IndicateNode dung de hien thi vi tri cua mot nut trong danh sach

        // Vi tri se duoc nhan manh thong qua dau ()

        private static void IndicateNode(LinkedListNode node, string test)

        {

            Console.WriteLine(test);

            if (node.List == null)

            {

                Console.WriteLine("Nut '{0}' la khong nam trong danh sach. ",

                    node.Value);

                return;

            }

            StringBuilder result = new StringBuilder("(" + node.Value + ")");

            LinkedListNode nodeP = node.Previous;

            // Duyet cac nut truoc node va dat no vao vi tri 0 trong chuoi result

            while (nodeP != null)

            {

                result.Insert(0, nodeP.Value + " ");

                nodeP = nodeP.Previous;

            }

            node = node.Next;

            // Duyet cac nut nam sau node va gan no vao vi tri cuoi cua result

            while (node != null)

            {

                result.Append(" " + node.Value);

                node = node.Next;

            }

            Console.WriteLine(result);

            Console.WriteLine();

        }

    }

}   

Ngay sau khi chạy, kết quả sẽ như thế này

• Hình 001
• Hình 2
• Kết quả chương trình

Lê Viễn Trình DH10TH