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

đăng lúc

cấu trúc dữ liệu danh sách liên kết đôi. Minh họa trong CSharp...

Trong bài trước, mình đã viết về cấu trúc dữ liệu danh sách liên kết đơn trong CSharp. Ở bài này mình sẽ viết về cách khởi tạo và sử dụng một loại danh sách liên kết khác trong CSharp: danh sách liên kết kép.


Về bản chất, nếu bạn đã hiểu và nắm được lý thuyết về Danh sách liên kết đơn thì sẽ rất đơn giản khi tìm hiểu về Danh sách liên kết kép.

Sự khác biệt căn bản giữa danh sách liên kết đơn và danh sách liên kết kép là:

+ Với danh sách liên kết đơn: Mỗi nút trong danh sách liên kết đơn sẽ gồm hai thông tin: dữ liệu (info) mà nút đó sẽ giữ và liên kết con trỏ tới nút liền kề sau nó trong danh sách. Vì mỗi nút chỉ chứa duy nhất một liên kết con trỏ tới nút sau nó trong danh sách nên người ta gọi nó là danh sách liên kết đơn.

+ Với danh sách liên kết kép: Mỗi nút trong danh sách liên kết kép cũng sẽ chứa dữ liệu (info) của nút đó. Ngoài ra, thay vì chỉ chứa một liên kết tới nút sau nó như danh sách liên kết đơn, với danh sách liên kết kép, mỗi nút trong danh sách liên kết kép sẽ chứa hai liên kết: một liên kết trỏ tới nút liền trước nó và một liên kết trỏ tới nút liền sau nó trong danh sách. (Nếu đó là nút đầu danh sách thì liên kết trỏ tới nút trước nó sẽ được gán với một giá trị đặc biệt, và với  nút cuối danh sách thì liên kết trở tới nút sau nó cũng sẽ được gán với một giá trị đặc biệt.)

+ Với danh sách liên kết đơn, ta chỉ có thể duyệt danh sách theo 1 chiều, còn đối với một danh sách liên kết kép, ta có duyệt danh sách từ một trong hai đầu của danh sách đó.

Hình minh họa một danh sách liên kết đôi gồm 5 node.

  • Với nút đầu tiên của danh sách, vì không có nút nào trước nó nên liên kết trỏ tới nútphía trước nó sẽ được đặt cho một giá trị đặc biệt. Người ta thường cho liên kết này trỏ tới null. Tương tự với nút cuối cùng của danh sách.
  • Lưu ý : liên kết tới nút phía sau của nút A (trỏ tới nút B) không trùng với liên kết tới nút phía trước của nút B (trỏ tới nút A).

Vì ở bài trước mình đã nói khá chi tiết, cụ thể về Danh sách liên kết đơn rồi nên ở bài này, mình sẽ chỉ nói qua thôi vì nếu các bạn đã hiểu rõ về danh sách liên kết đơn cũng như cách tạo danh sách liên kết đơn trong CSharp thì việc hiểu Danh sách liên kết kép sẽ rất dễ dàng. Bạn có thể đọc lại bài trước của mình ở đây: Danh sách liên kết đơn trong CSharp.

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

     class dll
    {
        public dll Left, Right;   // Left là liên kết tới nút phía trước, Right là liên kết tới nút phía sau
        public int data;   // dữ liệu mà nút chứa
    }

Các bạn có thể thấy việc khởi tạo kiểu dữ liệu danh sách kép không khác gì so với việc khởi tạo danh sách liên kết đơn cả.

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 kép, ta cần quản lý hai phần tử: phần tử đầu và cuối danh sách. Vì vậy, chúng ta cần khai báo và khởi tạo tới hai phần tử để quản lý danh sách kép thay vì chỉ cần một phần tử như ở danh sách liên kết đơn.

    dll L = null, R = null;

L (viết tắt của Left) là nút đầu danh sách, R (viết tắt của Right) là nút cuối danh sách. (Theo chiều từ trái sang phải.)

Ta đặt cả hai giá trị L và R đều bằng null vì danh sách hiện tại khi khởi tạo đang rỗng chưa có phần tử nào cả.

3. Nhập danh sách.

Tương tự như với danh sách liên kết đơn, 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 một nút vào danh sách, ta sẽ tạo một phần tử tạm có kiểu dữ liệu dll.

        // Khởi tạo nút tạm
        dll element = new dll();


Với danh sách liên kết đôi thì ta có thể thêm theo một trong hai chiều, thêm dần theo phía bên phải (nút thêm vào là nút bên phải của nút trước đó) hoặc thêm dần theo phía bên trái. Để cho thuận, mình sẽ làm theo cách thêm vào phía bên phải.

Khi thêm một nút vào danh sách thì nút ta thêm vào s sẽ xảy ra hai trường hợp:

+ Danh sách hiện đang rỗng, chưa có nút nào cả. Lúc này, L và R sẽ đều đang là null. Thực chất, chỉ cần L = null cũng sẽ đồng nghĩa với việc R = null (và ngược lại). Hay nói cách khác chỉ cần kiểm tra một trong hai thằng này có bằng null không là đủ để biết danh sách có đang rỗng không rồi.

Vì thêm dần theo phía bên phải nên mình sẽ kiểm tra L = null.

     if (L == null)
     {
          element.data = temp; // temp là biến tạm dùng để lưu dữ liệu do người dùng nhập vào.
          element.Left = null; // vì đây là nút đầu danh sách nên liên kết tới nút trái và phải đều là null
          element.Right = null;

          L = R = element;
     }

+ Danh sách không rỗng hay nói cách khác là phần tử được thêm vào không phải là phần tử đầu danh sách.

Lúc khi chưa thêm phần tử element vào cuối danh sách, thì R đang quản lý phần tử cuối danh sách. sau khi thêm phần tử element vào thì:

+ Phần tử bên trái element sẽ là R và được trỏ tới R, bên phải element sẽ trỏ tới null vì nó là phần tử cuối cùng ở thời điểm hiện tại.

+ Lúc này nó sẽ là phần tử bên phải của R nên cần cho phần tử bên phải R trỏ tới element.

+ Cuối cùng là cập nhật lại element sẽ do R quản lý.

Các bạn hãy xem code bên dưới sẽ thấy dễ hiểu hơn.

     if (L != null)
     {
          element.data = temp; // temp là biến tạm dùng để lưu dữ liệu do người dùng nhập vào.
          element.Left = R;
          element.Right = null;
          R.Right = element;

          R = element;
     }

Code hàm nhập danh sách:

static void nhap(ref dll L, ref dll R)
{
    int i = 1;
    int temp;
    string strTemp;
    bool checkTemp;

    dll element;
    do
    {
        Console.Write("\nNhập phần tử {0} (nhập chữ cái bất kì để thoát): ", i);
        strTemp = Console.ReadLine();
        checkTemp = int.TryParse(strTemp, out temp);

        if (checkTemp == true)
        {
            element = new dll();

            if (L == null)
            {
                element.Left = null;
                element.data = temp;
                element.Right = null;

                L = R = element;
            }

            else
            {
                element.data = temp;
                element.Left = R;
                element.Right = null;
                R.Right = element;

                R = element;
            }
        }
        i++;
    } while (checkTemp == true);
}


Nếu các bạn không hiểu đoạn code trên, có thể qua bài trước và đọc mục 3. Nhập danh sách bên dưới sẽ có phần giải thích chi tiết.

4. Duyệt (xuất) danh sách hiện tại.

static void xuat(dll L, dll R)
{
    if (L == null) // danh sách rỗng
    {
        Console.Write("\nDanh sách rỗng.");
    }

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

        dll temp = L;
        do
        {
            Console.Write(temp.data + "  ");
            temp = temp.Right;
        } while (temp != null);
    }
}

Hàm này khá dễ hiểu rồi, các bạn có thể qua bài trước nếu chưa hiểu nhé. Hàm này ở danh sách liên kết đơn và danh sách liên kết đôi tương tự nhau thôi.

5. Đếm số phần tử trong danh sách.

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

static int demSoPhanTu(dll L)
{
    int count = 0;
    dll temp = L;
    while(temp != null)
    {
        count++;
        temp = temp.Right;
    }
    return count;
}

6. Thêm phần tử vào một vị trí bất kì trong danh sách.

Khi chèn một phần tử vào danh sách sẽ xảy ra hai khả năng:

- Danh sách đang rỗng: lúc này khi thêm một phần tử vào thì L sẽ trùng với R nói cách khác là đều trỏ tới phần tử này.

    if (L == null)
    {
        Console.Write("Nhập vào giá trị cần thêm : ");
        int newData = int.Parse(Console.ReadLine());

        L = R = new dll();
        L.data = R.data = newData;
        L.Left = R.Left = null;
        L.Right = R.Right = null;
    }

- Danh sách không rỗng. Lúc này, chúng ta sẽ yêu cầu người dùng nhập vào vị trí muốn thêm phần tử:

+ Nếu người dùng muốn thêm phần tử vào vị trí cuối danh sách: thì sẽ tương tự như ở mục 2. Nhập danh sách, với trường hợp là thêm phần tử vào danh sách đang không rỗng thôi.

     int count = demSoPhanTu(L); // đếm số phần tử của danh sách

     if (viTri == count + 1) // thêm vào cuối danh sách sẽ là thêm vào vị trí count + 1
     {
          element = new dll();
          element.data = temp; // temp là biến tạm dùng để lưu dữ liệu do người dùng nhập vào.
          element.Left = R;
          element.Right = null;
          R.Right = element;

          R = element;
     }

+ Trường hợp thêm vào đầu danh sách tương tự như khi thêm phần tử vào cuối danh sách,

    if (viTri == 1)
    {
        element = new dll();
        element.data = temp; // temp là dữ liệu của nút mà người dùng muốn thêm vào.
        element.Left = null;
        element.Right = L;

        L = element;
    }

+ Trường hợp thêm vào một ví trị ở giữa danh sách  (1 < viTri < count + 1):

Giả sử ta cần chèn một phần tử vào giữa nút A và nút B. Ta gọi phần tử cần chèn là element (có kiểu dữ liệu là dll).

  • Ban đầu khi chưa chèn: A ⇄ B
          A.Right  = B;
          B.Left = A;
  • Sau khi chèn thì temp sẽ nằm giữa A và B, lúc này danh sách trở thành: A ⇄ element ⇄ B. Do đó ta sẽ cần chỉnh lại liên kết thành:
          A.Right = element;
          B.Left = element;
          // và ta cũng cần cho các liên kết của temp trỏ sang A và B.
          element.Left = A;
          element.Right = B;


Lưu ý: để chèn một phần tử vào một vị trí nằm giữa danh sách (1 < viTri < count + 1) thì chúng ta sẽ cần duyệt từ đầu danh sách đến viTri cần chèn. Quá trình duyệt danh sách này y hệt như ở hàm đếm số phần tử hay hàm xuất danh sách, nhưng quá trình duyệt sẽ dừng khi đến được vị trí cần thêm.

    if (viTri > 1 && viTri < count + 1)
    {
        temp = L; // biến phụ để duyệt danh sách
        while (temp != null) // duyệt danh sách
        {
            if (i == viTri - 1) // tìm được nút trước vị trí cần thêm
            {
                dll element = new dll();
                element.data = newData; // dữ liệu của nút được thêm vào
                element.Left = temp; // temp đóng vai trò như nút A ở vị dụ trên.
                element.Right = temp.Right; // temp.Right là nút B ở ví dụ trên.

                temp.Right.Left = element; // temp.Right.Left là B.Left
                temp.Right = element;

                break;
            }

            else // chưa tới thì cứ duyệt tiếp để đến được viTri - 1
            {
                i++;
                temp = temp.Right;
            }
        }
    }

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

static void them(ref dll L, ref dll R)
{
    if (L == null)
    {
        Console.Write("Nhập vào giá trị cần thêm : ");
        int newData = int.Parse(Console.ReadLine());

        L = R = new dll();
        L.data = R.data = newData;
        L.Left = R.Left = null;
        L.Right = R.Right = null;
    }


    else
    {
        int count = demSoPhanTu(L);
        int viTri;
        do
        {
            Console.Write("\nNhập vào vị trí muốn thêm (đoạn từ 1 đến {0}) : ", count + 1);
            viTri = int.Parse(Console.ReadLine());
        } while (viTri < 1 || viTri > count + 1);

        Console.Write("\nNhập vào giá trị muốn thêm : ");
        int newData = int.Parse(Console.ReadLine());

        int i = 1;
        dll element;

        if (viTri == 1)
        {
            element = new dll();
            element.data = newData;
            element.Left = null;
            element.Right = L;

            L = element;
        }

        else if (viTri > 1 && viTri < count + 1)
        {
            dll temp = L;
            while (temp != null)
            {
                if (i == viTri - 1)
                {
                    element = new dll();
                    element.data = newData;
                    element.Left = temp;
                    element.Right = temp.Right;

                    temp.Right.Left = element;
                    temp.Right = element;

                    break;
                }

                else
                {
                    i++;
                    temp = temp.Right;
                }
            }
        }


        else
        {
            element = new dll();
            element.data = newData;
            element.Left = R;
            element.Right = null;
            R.Right = element;

            R = element;
        }
    }
}

6. Hàm xóa phần tử.

Hàm xóa phần tử cũng tương tự như hàm thêm phần tử, chúng ta cũng sẽ cần xét tới 3 trường hợp là:

+ Vị trí cần xóa nằm đầu danh sách.
+ Vị trí cần xóa nằm giữa danh sách.
+ Vị trí cần xóa nằm cuối danh sách.

Cách xử lý từng trường hợp này cũng tương tự như ở hàm thêm phần tử. Các bạn có thể tự phân tích để hiểu rõ hơn nhé.

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

static void xoa(ref dll L, ref dll R)
{

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

    else
    {
        int count = demSoPhanTu(L);
        int viTri;
        do
        {
            Console.Write("\nNhập vào vị trí muốn xóa (đoạn từ 1 đến {0}) : ", count);
            viTri = int.Parse(Console.ReadLine());
        } while (viTri < 1 || viTri > count);


        if (viTri == 1)
        {
            if(count == 1) // danh sách chỉ còn 1 phần tử trước khi xóa
            {
                L = null;
            }

            else // danh sách có nhiều hơn 1 phần tử
            {
                L = L.Right;
                L.Left = null;
            }
        }

        else if (viTri > 1 && viTri < count)
        {
            int i = 1;
            dll temp = L;

            do
            {
                if (i == viTri - 1)
                {
                    dll element = new dll();

                    element = temp.Right.Right;

                    element.Left = temp;
                    temp.Right = element;

                    break;
                }

                else
                {
                    i++;
                    temp = temp.Right;
                }
            } while (temp != null);
        }

        else
        {
            R = R.Left;
            R.Right = null;
        }
    }
}

7. 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;
using System.Threading.Tasks;

namespace Double_link_list
{
    class dll
    {
        public int data;
        public dll Left, Right;
    }

    class Program
    {
        static void nhap(ref dll L, ref dll R)
        {
            int i = 1;
            int temp;
            string strTemp;
            bool checkTemp;

            dll element;
            do
            {
                Console.Write("\nNhập phần tử {0} (nhập chữ cái bất kì để thoát): ", i);
                strTemp = Console.ReadLine();
                checkTemp = int.TryParse(strTemp, out temp);

                if (checkTemp == true)
                {
                    element = new dll();

                    if (L == null)
                    {
                        element.Left = null;
                        element.data = temp;
                        element.Right = null;

                        L = R = element;
                    }

                    else
                    {
                        element.data = temp;
                        element.Left = R;
                        element.Right = null;
                        R.Right = element;

                        R = element;
                    }
                }
                i++;
            } while (checkTemp == true);
        }

        static void xuat(dll L, dll R)
        {
            if (L == null)
            {
                Console.Write("\nDanh sách rỗng.");
            }

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

                dll temp = L;
                do
                {
                    Console.Write(temp.data + "  ");
                    temp = temp.Right;
                } while (temp != null);
            }
        }

        static int demSoPhanTu(dll L)
        {
            int count = 0;
            dll temp = L;
            while(temp != null)
            {
                count++;
                temp = temp.Right;
            }
            return count;
        }

        static void them(ref dll L, ref dll R)
        {
            if (L == null)
            {
                Console.Write("Nhập vào giá trị cần thêm : ");
                int newData = int.Parse(Console.ReadLine());

                L = R = new dll();
                L.data = R.data = newData;
                L.Left = R.Left = null;
                L.Right = R.Right = null;
            }


            else
            {
             int count = demSoPhanTu(L);
                int viTri;
                do
                {
                    Console.Write("\nNhập vào vị trí muốn thêm (đoạn từ 1 đến {0}) : ", count + 1);
                    viTri = int.Parse(Console.ReadLine());
                } while (viTri < 1 || viTri > count + 1);

                Console.Write("\nNhập vào giá trị muốn thêm : ");
                int newData = int.Parse(Console.ReadLine());

                int i = 1;
                dll element;

                if (viTri == 1)
                {
                    element = new dll();
                    element.data = newData;
                    element.Left = null;
                    element.Right = L;

                    L = element;
                }

                else if (viTri > 1 && viTri < count + 1)
                {
                    dll temp = L;
                    while (temp != null)
                    {
                        if (i == viTri - 1)
                        {
                            element = new dll();
                            element.data = newData;
                            element.Left = temp;
                            element.Right = temp.Right;

                            temp.Right.Left = element;
                            temp.Right = element;

                            break;
                        }

                        else
                        {
                            i++;
                            temp = temp.Right;
                        }
                    }
                }


                else
                {
                    element = new dll();
                    element.data = newData;
                    element.Left = R;
                    element.Right = null;
                    R.Right = element;

                    R = element;
                }
            }
        }

        static void xoa(ref dll L, ref dll R)
        {

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

            else
            {
             int count = demSoPhanTu(L);
                int viTri;
                do
                {
                    Console.Write("\nNhập vào vị trí muốn xóa (đoạn từ 1 đến {0}) : ", count);
                    viTri = int.Parse(Console.ReadLine());
                } while (viTri < 1 || viTri > count);


                if (viTri == 1)
                {
                    if(count == 1) // danh sách chỉ còn 1 phần tử trước khi xóa
                    {
                        L = null;
                    }

                    else // danh sách có nhiều hơn 1 phần tử
                    {
                        L = L.Right;
                        L.Left = null;
                    }
                }

                else if (viTri > 1 && viTri < count)
                {
                    int i = 1;
                    dll temp = L;

                    do
                    {
                        if (i == viTri - 1)
                        {
                            dll element = new dll();

                            element = temp.Right.Right;

                            element.Left = temp;
                            temp.Right = element;

                            break;
                        }

                        else
                        {
                            i++;
                            temp = temp.Right;
                        }
                    } while (temp != null);
                }

                else
                {
                    R = R.Left;
                    R.Right = null;
                }
            }
        }


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

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

            dll L = null, R = null;
            nhap(ref L, ref R);
            xuat(L, R);

        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.Đếm số phần tử.");
            Console.Write("\n4.Thoát.");
            Console.Write("\nNhập vào lựa chọn : ");
            string luaChon = Console.ReadLine();

            if (luaChon == "1")
            {
                them(ref L, ref R);
                xuat(L, R);
                goto luachon;
            }

            else if (luaChon == "2")
            {
                int count = demSoPhanTu(L);
                if (count != 0)
                {
                    xoa(ref L, ref R);
                    xuat(L, R);
                }

                else
                {
                    xoa(ref L, ref R);
                }
                goto luachon;
            }

            else if (luaChon == "3")
            {
                int count = demSoPhanTu(L);
                Console.Write("\nDanh sách có {0} phần tử.", count);
                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/Y8343mXfgB/ (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 kép và biết cách tạo Danh sách liên kết kép 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