Danh sách liên kết trong CSharp

đăng lúc

Danh sách liên kết là một kiểu cấu trúc dữ liệu mà có lẽ ai học về Cấu trúc dữ liệu và giải thuật đều phải biết. Tuy vậy, hầu hết các phiên bản giải thích, code trên mạng hầu như là dành cho ngôn ngữ lập trình C/C++. Vì vậy mà hôm nay mình sẽ viết về một phiên bản khác, đó là cách tạo một danh sách liên kết đơn trong CSharp.

Danh sách liên kết là một  kiểu cấu trúc dữ liệu mà có lẽ ai học về Cấu trúc dữ liệu và giải thuật đều phải biết. Tuy vậy, hầu hết các phiên bản giải thích, code trên mạng hầu như là dành cho ngôn ngữ lập trình C/C++. Vì vậy mà hôm nay mình sẽ viết về một phiên bản khác, đó là cách tạo một danh sách liên kết đơn trong CSharp.



Về cách tạo danh sách liên kết đơn trong CSharp, các bạn có thể chuyển đổi code bên C/C++ sang CSharp, đồng nghĩa với việc chúng ta sẽ dùng tới toán tử con trỏ. Việc chuyển đổi code này không quá khó khăn nên mình sẽ không nói ở bài này. Ở bài này, mình sẽ viết về cách tạo một danh sách liên kết đơn trong CSharp sử dụng class. (Về bản chất thì cách này cũng tương tự như sử dụng toán tử con trỏ thôi.)

Chúng ta bắt đầu nào.

1. Khởi tạo kiểu dữ liệu danh sách liên kết đơn.

Mỗi nút trong danh sách liên kết đơn sẽ gồm 2 thành phần, đó là dữ liệu của nút đó chứa (info) và liên kết tới nút tiếp theo sau nó trong danh sách (next).

Để máy tính có thể hiểu được kiểu dữ liệu này, chúng ta sẽ khai báo một class gồm 2 thành phần là infonext. Ta đặt tên class này là sll (sll là viết tắt của Singer Linked List - danh sách liên kết đơn trong tiếng anh).

     class sll
    {
        public sll next;   // liên kết "con trỏ" tới nút kế nó
        public int info;   // dữ liệu mà nút chứa
    }

Ta dùng class để định nghĩa kiểu dữ liệu danh sách liên kết thay vì dùng struct vì class là kiểu dữ liệu tham biến (tương tự như con trỏ vậy) còn struct là kiểu dữ liệu tham trị.

2. Khai báo và khởi tạo danh sách liên kết rỗng.

Với danh sách liên kết đơn ta chỉ cần quản lý phần tử đầu danh sách là đã có thể duyệt, đi hết danh sách. Nút đầu chứa liên kết tới nút thứ hai, nút thứ hai chứa liên kết tới nút thứ ba,.... Nút cuối danh sách thì sẽ không liên kết với nút nào cả.

Chúng ta sẽ đặt tên phần tử đầu, phần tử quản lý danh sách của chúng ta là list.

Về khai báo và khởi tạo, chúng ta có thể khai báo vào khởi tạo phần tử đầu danh sách ngay trong hàm Main một cách đơn giản như sau :

    sll list = null;

Danh sách liên kết ban đầu đang rỗng nên ta để giá trị của của nút đầu danh sách là null. (Nút đầu bằng null thì đồng nghĩa với việc không có các nút sau, danh sách đang rỗng.)

3. Nhập danh sách.

Ta sẽ cho người dùng nhập vào dữ liệu sẽ chứa của từng nút một. Sau khi người dùng nhập xong dữ liệu mà một nút sẽ chứa, ta thêm nút đó vào danh sách và tiến hành cho người dùng nhập nút tiếp.

- Thêm nút vào trong danh sách :

Để thêm một nút vào danh sách, ta sẽ tạo một nút tạm có kiểu dữ liệu sll, lấy tên là node. Dữ liệu của node này (node.info) do người dùng nhập vào. Vì chúng ta đang nhập danh sách, nên khi ta nhập thêm vào danh sách một nút thì nút này sẽ luôn là nút cuối danh sách.

        // Khởi tạo nút tạm
        node = new sll();
        node.info = temp;    // temp là biến ta tạo để lưu dữ liệu do người dùng nhập vào
        node.next = null;     // vì là nút cuối danh sách nên không có nút sau nó.

Tiếp theo, ta sẽ thêm nút này vào danh sách. Sẽ xảy ra hai khả năng :
+ Nếu danh sách hiện tại đang rỗng, chưa có nút nào. Thì nút bên trên khi thêm vào sẽ là nút đầu của danh sách.
+ Nếu danh sách đã có có nút khác (không rỗng), thì ta sẽ tiến hành thêm nút kia vào cuối danh sách. Để thêm nút kia vào cuối danh sách thì ta sẽ cần duyệt tới cuối danh sách và thêm nó vào cuối danh sách.

        // thêm nút tạm vào danh sách
        if (list == null)   // danh sách rỗng
        {
            list = node;    // nút đầu danh sách sẽ có dữ liệu giống nút tạm
        }
        else
        {
            sll p = list;   // tạo một biến phụ để duyệt danh sách
            while (p.next != null)   // duyệt tới cuối danh sách
            {
                p = p.next;
            }
            p.next = node;   // thêm nút tạm vào cuối danh sách.
        }

Lý do chúng ta cần tạo biến phụ để duyệt danh sách là vì nếu ta dùng nút chính nút list để duyệt danh sách thì sau quá trình duyệt nút list sẽ trở thành nút gần cuối danh sách, không còn là nút đầu danh sách nữa. Do đó ta sẽ không quản lý được nút đầu danh sách nữa.

- Tạo vòng lặp để cho người dùng nhập dữ liệu liên tục :

Bên trên là quá trình thêm một nút vào danh sách của chúng ta. Để có thể cho người dùng sau khi nhập xong một nút, thêm nút đó vào danh sách rồi chuyển qua nhập nút khác thì ta sẽ cần một vòng lặp.

Ta sẽ tạo một hàm cho công việc nhập danh sách này :

static void nhapDanhSach(ref sll list)    // truyền dữ liệu kiểu tham biến
{
    int temp;
    bool checkTemp;
    string strTemp;

    do
    {
        Console.Write("\nNhập vào phần tử (nhập vào chữ cái bất kì để thoát) : ");
        strTemp = Console.ReadLine();
        checkTemp = int.TryParse(strTemp, out temp);  // kiểm tra xem người dùng nhập vào số ?

        if (checkTemp == true)   // nếu dữ liệu nhập vào là một số nguyên
        {
             // Khởi tạo nút tạm
            sll node = new sll();
            node.info = temp;    // temp là dữ liệu người dùng nhập vào
            node.next = null;    // vì là nút cuối danh sách nên không có nút sau nó.

            // thêm nút tạm vào danh sách
            if (list == null)    // danh sách rỗng
            {
                list = node;     // nút đầu danh sách sẽ có dữ liệu giống nút tạm
            } 

            else
            {
                sll p = list;   // tạo một biến phụ để duyệt danh sách
                while (p.next != null)   // duyệt tới cuối danh sách
                {
                    p = p.next;
                }

                p.next = node;   // thêm nút tạm vào cuối danh sách.
            }
        }
    } while (checkTemp == true);
}



4.  Duyệt các phần tử trong danh sách.

Viện duyệt, in ra màn hình các phần tử trong danh sách thì khá là đơn giản. Chúng ta chỉ việc kiểm tra xem danh sách có rỗng không. Nếu danh sách rỗng thì in ra màn hình là danh sách rỗng. Ngược lại thì in ra các phần tử trong danh sách.

Hàm duyệt danh sách :

static void duyetDanhSach(sll list)
{
    if (list == null)     // danh sách rỗng
    {
        Console.Write("\nDanh sách rỗng.");
    }

    else
    {
        Console.WriteLine("\nDanh sách hiện tại là :");

        sll p = list;
        while (p != null)
        {
            Console.Write(p.info + "  ");
            p = p.next;
        }
    }
}

 5. Tìm kiếm phần tử trong danh sách.

 Tìm kiếm thì cũng khá là đơn giản, và thực ra là tương tự như duyệt danh sách, ta cứ duyệt từ đầu đến cuối danh sách, nhưng thay vì in ra các dữ liệu các nút thì ta sẽ so sánh dữ liệu các nút với giá trị cần tìm kiếm. Nếu có nút nào có giá trị bằng với giá trị cần tìm thì là tìm thấy, ngược lại thì là không có trong danh sách.

 Hàm tìm kiếm phần tử :

static int timKiem(sll list)
{
    Console.Write("\nNhập vào giá trị cần tìm kiếm : ");
    int giaTri = int.Parse(Console.ReadLine());

    sll p = list;
    while (p != null)
    {
        if (p.info == giaTri)
        {
            Console.Write("\nPhần tử {0} có tồn tại trong danh sách.", giaTri);
            return 1;
        }

        else
        {
            p = p.next;
        }
    }

    Console.Write("\nPhần tử {0} không tồn tại trong danh sách.", giaTri);
    return 0;
}




Ngoài ra các bạn có thể để ý là mình không xét tới list bằng null hay khác null mà cứ thế cho duyệt luôn vì điều kiện khi while (p != null), nên nếu mà bằng null thì sẽ không chạy vào vòng lặp (không duyệt danh sách) mà in thẳng ra danh sách không chứa phần tử cần tìm luôn. Ngược lại thì sẽ duyệt rồi tìm kiếm như bình thường thôi.

6. Tính độ dài danh sách (Đếm số nút có trong danh sách).

Hàm này bản chất cũng chỉ là duyệt danh sách như hai hàm trên thôi.

static int demSoNut(sll list)
{
    int count = 0;
    sll q = list;
    while (q != null)
    {
        count++;
        q = q.next;
    }
    return count;
}

7. Thêm phần tử vào một vị trí trong danh sách.

Giả sử ta đang có hai nút cạnh nhau trong danh sách như hình dưới.


Ta đặt tên cho nút cần thêm là nút C.

Khi thêm một nút vào giữa hai nút trên, thì nút cần thêm (nút C) sẽ đứng giữa nút A và nút B. Do đó, nút A không còn là nút đứng liền trước B trong dánh sách nữa. Lúc này nút A sẽ đứng liền trước nút C trong danh sách và nút C sẽ đứng liền trước nút B trong danh sách.

Sau khi thêm : A ---> B    thành   A ---> C ---> B

Vì thế ta cần cho next của nút A đang từ trỏ liên kết tới nút B chuyển sang trỏ vào nút C. (Vì nút C sau khi thêm là nút đứng liền sau nút A)

Và cho next của nút C trỏ vào nút B để danh sách được kết nối liền mạch.

Hình minh họa cho sinh động 😀😀😀 :



Để thêm một phần tử vào một vị trí nào đó (vị trí do người dùng nhập vào) thì ta cần đi từ đầu danh sách tới vị trí đó.

Ví dụ : danh sách đang có 10 nút, ta cần thêm một nút vào vị trí thứ 5 trong danh sách thì :
+ sau khi thêm, phần tử được thêm sẽ là phần tử thứ 5 của danh sách, phần tử thứ 5 của danh sách trước đó trở thành phần thứ 6 của danh sách.
+ phần tử được thêm vào sẽ được thêm vào giữa phần tử thứ 4 và phần tử thứ 5 của danh sách hiện tại.

Do đó ta sẽ cần đi từ đầu danh sách tới phần tử thứ 4, sau đó trỏ liên kết phần tử này tới phần tử cần thêm, và cho phần tử cần thêm trỏ liên kết tới phần tử thứ 5 cũ là xong.

 Trong trường hợp đặc biệt : nút được thêm vào vị trí đầu danh sách, thì ta chỉ cần cho nút cần thêm trỏ tới nút đang đứng đầu danh sách hiện tại. Và cập nhật lại nút đầu danh sách thành nút mới thêm vào.

Trong trường hợp tổng quát, ta cần đi tới phần tử "vị trí cần thêm trừ đi 1".

Code hàm thêm phần tử :

static void themNut(ref sll list)
{
    // đếm số nút để biết có thể thêm vào những vị trí nào trong danh sách
    int count = demSoNut(list);

    // nhập vị trí cần thêm - chỉ cho nhập vào vị trí có thể
    int viTri;
    do
    {
        Console.Write("Nhập vị trí cần thêm (0 < vị trí <= {0}): ", count + 1);
        viTri = int.Parse(Console.ReadLine());
    } while (viTri < 1 || viTri > count + 1);

    // nhập dữ liệu (info) của nút thêm vào
    Console.Write("\nNhập vào dữ liệu cần thêm : ");
    int temp = int.Parse(Console.ReadLine());

    sll p = list;
    if (viTri == 1)   // nếu là thêm vào đầu danh sách
    {
        sll node = new sll();
        node.info = temp;
        node.next = p;    // cho nút cần thêm trỏ tới nút đang đứng đầu danh sách hiện tại

        list = node;    // cập nhật lại nút đầu danh sách hiện tại là nút mới thêm và
    }

    if (viTri > 1)
    {
        int i = 1;
        while (p != null)
        {
            if (i == (viTri - 1))    // vị trí - 1
            {
                sll node = new sll();
                node.info = temp;
                node.next = p.next;      // cho nút mới thêm trỏ tới nút "phía sau"

                p.next = node;   // chuyển liên kết từ nút "phía trước" tới trỏ vào nút mới thêm

                break;   // thêm xong rồi thì thoát thôi duyệt tiếp danh sách làm gì nữa
            }

            else
            {
                i++;
                p = p.next;    // chưa tới vị trí - 1 thì duyệt tiếp
            }
        }
    }
}

8. Xóa phần tử (theo vị trí) khỏi danh sách liên kết.

Công việc xóa phần tử thì cũng tương tự như thêm phần tử thôi.

Giả sử : danh sách đang có 3 nút như sau :

A --- > B ---> C

Và ta cần xóa B khỏi danh sách.

Sau khi xóa B khỏi danh sách thì phần tử đứng liền A trong danh sách sẽ là C. Nút đứng liền trước C trong danh sách sẽ là A.

Sau khi xóa : A --- > B ---> C   thành   A ---> C

Do đó, ta sẽ cho next của A đang từ trỏ tới B thành trỏ tới C. Vậy là xong.

Lưu ý : Ta chỉ cần chỉnh liên kết như bên trên là danh sách đã không chứa B nữa rồi, nhưng để tiết kiệm bộ nhớ, người ta thường giải phóng vùng nhớ chứa nút B.

Hình minh cho sinh động nào😎😎😎😎😎:



Tương tự như thêm nút vào danh sách, để xóa nút B thì ta cũng cần duyệt tới nút liền trước của B hiện tại là A và cho A trỏ tới C là nút liền sau B ở hiện tại.

Ngoài ra, còn một trường hợp đặc biệt là nút cần xóa là nút ở đầu danh sách, lúc này ta chỉ cần cho nút thứ hai của danh sách ở thời điểm hiện tại là nút quản lý đầu danh sách là xong.

Code hàm xóa phần tử :

static void xoaNut(ref sll list)
{
    if (list == null)
    {
        Console.Write("Danh sách rỗng - không có gì để xóa.");
    }

    else
    {
        // đếm số nút để biết có thể thêm vào những vị trí nào trong danh sách
        int count = demSoNut(list);

        int viTri;
        do
        {
            Console.Write("Nhập vị trí cần xóa (0 < vi trí <= {0}): ", count);
            viTri = int.Parse(Console.ReadLine());
        } while (viTri < 1 || viTri > count);

        sll p = list;

        if (viTri == 1)   // nút cần xóa là nút đầu danh sách
        {
            list = list.next;  // cập nhật lại list thành nút thứ sau nó ở danh sách
        }

        else
        {
            int i = 1;
            while (p != null)
            {
                if (i == viTri - 1)    // p là nút liền trước nút cần xóa trong danh sách
                {
                    sll node = new sll();
                    node = p.next.next;     // node là nút liền sau nút cần xóa trong danh sách

                    p.next = node;     // cho nút liền trước (p) trỏ tới nút liền sau (node)

                    break;     // xong việc rồi thì break thôi.
                }

                else    // duyệt tới viTri - 1
                {
                    i++;
                    p = p.next;
                }
            }
        }
    }
}

9. Code CSharp đầy đủ minh họa Danh sách liên kết đơn

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DS_Lienketkep
{
    class sll
    {
        public sll next;   // liên kết "con trỏ" tới nút kế nó
        public int info;   // dữ liệu mà nút chứa
    }

    class Program
    {
        static void nhapDanhSach(ref sll list)    // truyền dữ liệu kiểu tham biến
        {
            int temp;
            bool checkTemp;
            string strTemp;

            do
            {
                Console.Write("\nNhập vào phần tử (nhập vào chữ cái bất kì để thoát) : ");
                strTemp = Console.ReadLine();
                checkTemp = int.TryParse(strTemp, out temp);  // kiểm tra xem người dùng nhập vào số ?

                if (checkTemp == true)   // nếu dữ liệu nhập vào là một số nguyên
                {
                    // Khởi tạo nút tạm
                    sll node = new sll();
                    node.info = temp;    // temp là dữ liệu người dùng nhập vào
                    node.next = null;    // vì là nút cuối danh sách nên không có nút sau nó.

                    // thêm nút tạm vào danh sách
                    if (list == null)    // danh sách rỗng
                    {
                        list = node;     // nút đầu danh sách sẽ có dữ liệu giống nút tạm
                    } 

                    else
                    {
                        sll p = list;   // tạo một biến phụ để duyệt danh sách
                        while (p.next != null)   // duyệt tới cuối danh sách
                        {
                            p = p.next;
                        }

                        p.next = node;   // thêm nút tạm vào cuối danh sách.
                    }
                }
            } while (checkTemp == true);
        }

        static void duyetDanhSach(sll list)
        {
            if (list == null)     // danh sách rỗng
            {
                Console.Write("\nDanh sách rỗng.");
            }

            else
            {
                Console.WriteLine("\nDanh sách hiện tại là :");

                sll p = list;
                while (p != null)
                {
                    Console.Write(p.info + "  ");
                    p = p.next;
                }
            }
        }

        static int timKiem(sll list)
        {
            Console.Write("\nNhập vào giá trị cần tìm kiếm : ");
            int giaTri = int.Parse(Console.ReadLine());

            sll p = list;
            while (p != null)
            {
                if (p.info == giaTri)
                {
                    Console.Write("\nPhần tử {0} có tồn tại trong danh sách.", giaTri);
                    return 1;
                }

                else
                {
                    p = p.next;
                }
            }

            Console.Write("\nPhần tử {0} không tồn tại trong danh sách.", giaTri);
            return 0;
        }

        static int demSoNut(sll list)
        {
            int count = 0;
            sll q = list;
            while (q != null)
            {
                count++;
                q = q.next;
            }
            return count;
        }

        static void themNut(ref sll list)
        {
            // đếm số nút để biết có thể thêm vào những vị trí nào trong danh sách
            int count = demSoNut(list);

            // nhập vị trí cần thêm - chỉ cho nhập vào vị trí có thể
            int viTri;
            do
            {
                Console.Write("Nhập vị trí cần thêm (0 < vị trí <= {0}): ", count + 1);
                viTri = int.Parse(Console.ReadLine());
            } while (viTri < 1 || viTri > count + 1);

            // nhập dữ liệu (info) của nút thêm vào
            Console.Write("\nNhập vào dữ liệu cần thêm : ");
            int temp = int.Parse(Console.ReadLine());

            sll p = list;
            if (viTri == 1)   // nếu là thêm vào đầu danh sách
            {
                sll node = new sll();
                node.info = temp;
                node.next = p;    // cho nút cần thêm trỏ tới nút đang đứng đầu danh sách hiện tại

                list = node;    // cập nhật lại nút đầu danh sách hiện tại là nút mới thêm và
            }

            if (viTri > 1)
            {
                int i = 1;
                while (p != null)
                {
                    if (i == (viTri - 1))    // vị trí - 1
                    {
                        sll node = new sll();
                        node.info = temp;
                        node.next = p.next;      // cho nút mới thêm trỏ tới nút "phía sau"

                        p.next = node;   // chuyển liên kết từ nút "phía trước" tới trỏ vào nút mới thêm

                        break;   // thêm xong rồi thì thoát thôi duyệt tiếp danh sách làm gì nữa
                    }

                    else
                    {
                        i++;
                        p = p.next;    // chưa tới vị trí - 1 thì duyệt tiếp
                    }
                }
            }
        }

        static void xoaNut(ref sll list)
        {
            if (list == null)
            {
                Console.Write("Danh sách rỗng - không có gì để xóa.");
            }

            else
            {
                // đếm số nút để biết có thể thêm vào những vị trí nào trong danh sách
                int count = demSoNut(list);

                int viTri;
                do
                {
                    Console.Write("Nhập vị trí cần xóa (0 < vi trí <= {0}): ", count);
                    viTri = int.Parse(Console.ReadLine());
                } while (viTri < 1 || viTri > count);

                sll p = list;

                if (viTri == 1)   // nút cần xóa là nút đầu danh sách
                {
                    list = list.next;  // cập nhật lại list thành nút thứ sau nó ở danh sách
                }

                else
                {
                    int i = 1;
                    while (p != null)
                    {
                        if (i == viTri - 1)    // p là nút liền trước nút cần xóa trong danh sách
                        {
                            sll node = new sll();
                            node = p.next.next;     // node là nút liền sau nút cần xóa trong danh sách

                            p.next = node;     // cho nút liền trước (p) trỏ tới nút liền sau (node)

                            break;     // xong việc rồi thì break thôi.
                        }

                        else    // duyệt tới viTri - 1
                        {
                            i++;
                            p = p.next;
                        }
                    }
                }
            }
        }

        static void Main(string[] args)
        {
            Console.OutputEncoding = Encoding.UTF8;

            Console.Write("\t\t\t\tNhập danh sách.");

            sll list = null;   // khởi tạo ngay trong hàm main luôn
            nhapDanhSach(ref list);
            duyetDanhSach(list);

        luachon:
            Console.Write("\n\n\t\t\t\tBạn muốn làm gì tiếp theo :");
            Console.Write("\n1.Thêm phần tử.");
            Console.Write("\n2.Xóa phần tử.");
            Console.Write("\n3.Tìm kiếm");
            Console.Write("\n4.Đếm số nút của danh sách.");
            Console.Write("\n5.In ra danh sách hiện tại (duyệt danh sách)");
            Console.Write("\n6.Thoát.");
            Console.Write("\nNhập vào lựa chọn : ");
            string luaChon = Console.ReadLine();

            if (luaChon == "1")
            {
                themNut(ref list);
                duyetDanhSach(list);
                goto luachon;
            }

            else if (luaChon == "2")
            {
                if (list != null)
                {
                    xoaNut(ref list);
                    duyetDanhSach(list);
                }

                else
                {
                    xoaNut(ref list);
                }
                goto luachon;
            }

            else if (luaChon == "3")
            {
                timKiem(list);
                goto luachon;
            }

            else if (luaChon == "4")
            {
                int count = demSoNut(list);
                Console.Write("\nDanh sách có {0} nút.", count);
                goto luachon;
            }

            else if (luaChon == "5")
            {
                duyetDanhSach(list);
                goto luachon;
            }
        }
    }
}

Code trên Visual Studio 2012. Các bạn dùng các phiên bản khác có thể sẽ bị gặp lỗi cú pháp.

Bản notepad code online : https://paste.ubuntu.com/p/86hKRFHXpn/ (Có credit ở ngay dòng đầu code nhé. Bạn nào copy nộp cho thầy thì nhớ xóa đi nha. Khuyến khích các bạn nên đọc hiểu để tránh bị thầy hỏi và kiến thức này rất cần cho sau này khi các bạn học các môn khác và khi các bạn đi làm. )

Mong bài viết này sẽ giúp được các bạn hiểu hơn về Danh sách liên kết đơn và biết cách tạo Danh sách liên kết đơn trong CSharp.

Nếu có gì thắc mắc hay góp ý gì các bạn có thể comment dưới bài viết này nhé.

Chúc các bạn học tập tốt.

Tham khảo thêm : So sánh Danh sách liên kết và Mảng 

Bản quyền bài viết thuộc về Rebvn.com. Mọi copy vui lòng ghi rõ nguồn.

Nội dung chính
    Bài đăng mới hơn Bài đăng cũ hơn