Triển khai danh sách được liên kết trong C # - VisualGuide.org

CodeProject Trong bài viết này, tôi sẽ giải thích về danh sách liên kết, ưu và nhược điểm của việc sử dụng danh sách liên kết và sau đó triển khai danh sách liên kết trong C #. Tuy nhiên, Microsoft cung cấp danh sách liên kết được đánh máy mạnh mẽ LinkedList(T) Trong System.Collections.Generickhông gian. Ở đây, tôi sẽ giải thích cách triển khai cốt lõi của Danh sách được liên kết.

Danh sách liên kết là gì?

Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính. Đó là một tập hợp các yếu tố. Phần tử được gọi là Node.
Mỗi phần tử có giá trị (dữ liệu) và tham chiếu của nút tiếp theo. Nút đầu tiên được gọi là Head và phần tử cuối cùng có tham chiếu đến null.

Các loại danh sách được liên kết

Về cơ bản, có 3 loại danh sách liên kết.

Singly Linked List: Một danh sách được liên kết đơn là một danh sách có một giá trị (dữ liệu) và một tham chiếu đến nút tiếp theo. Trong đó, tham chiếu tiếp theo của nút cuối cùng sẽ là null.
Doubly Linked List: Danh sách được liên kết kép là danh sách có dữ liệu và 2 tham chiếu, một cho nút tiếp theo và một cho nút trước đó và tham chiếu tiếp theo của nút cuối cùng sẽ là null.
Circular Linked List: Trong danh sách liên kết vòng tròn, tham chiếu tiếp theo của nút cuối cùng sẽ là phần tử đầu hoặc phần tử đầu tiên. Danh sách liên kết tròn có thể là danh sách liên kết đơn hoặc danh sách liên kết kép.

Trong bài viết này, tôi sẽ giải thích việc triển khai danh sách liên kết đơn lẻ.

Ưu và nhược điểm

Ưu điểm chính của danh sách liên kết là nó là một cấu trúc dữ liệu động. Không giống như trong mảng mà độ dài của mảng được xác định trước, chúng ta có thể thêm số động dữ liệu trong danh sách liên kết mà không cần lo lắng về kích thước của danh sách được liên kết. Vì vậy, danh sách liên kết có thể được sử dụng khi có một số lượng dữ liệu chưa biết cần được lưu trữ tại thời điểm chạy.

Nhược điểm của danh sách liên kết là nó chiếm nhiều không gian hơn mảng. Bởi vì nó lưu trữ tham chiếu của các nút tiếp theo / trước đó.

Triển khai danh sách được liên kết

Lớp nút

Đây là lớp nút có 2 thuộc tính:

public class Node
{
    public Node Next;
    public object Value;
}

Một tài sản là ‘Next‘, sẽ có tham chiếu của nút tiếp theo và một nút khác là’Value‘, sẽ có dữ liệu trong nút này.

Lớp danh sách liên kết

Bây giờ triển khai lớp danh sách được liên kết như sau:

public class LinkedList
{
   private Node head;
   private Node current;//This will have latest node
   public int Count;
}

‘head‘sẽ có nút đầu. ‘current‘sẽ có nút mới nhất, tức là nút đuôi và’Count‘sẽ trả về tổng số nút trong danh sách được liên kết.

Người xây dựng

Ban đầu, head và current sẽ giống nhau và sẽ có nút trống, vì vậy chúng tôi sẽ tạo phương thức khởi tạo cho cài đặt đó.

public LinkedList()
{
  head = new Node();
  current = head;
}

Hoạt động trong danh sách được liên kết

Bây giờ, chúng ta sẽ tạo một số thao tác trên danh sách liên kết.

Thêm nút sau phần tử cuối cùng:
```
public void AddAtLast(object data)
{
   Node newNode = new Node();
   newNode.Value = data;
   current.Next = newNode;
   current = newNode;
   Count++;
}
```
Phương thức này sẽ thêm nút sau nút đuôi và nó sẽ tăng số lượng lên một. Tương tự, bạn có thể thêm nút làm nút đầu tiên.

Thêm nút làm phần tử nắm tay:

public void AddAtStart(object data)
{
  Node newNode = new Node() { Value = data};
  newNode.Next = head.Next;//new node will have reference of head's next reference
  head.Next = newNode;//and now head will refer to new node
  Count++;
}

Xóa nút từ đầu:
```
public void RemoveFromStart()
{
   if (Count > 0)
   {
     head.Next = head.Next.Next;
     Count--;
   }
   else
   {
     Console.WriteLine("No element exist in this linked list.");
   }
}
```
Tương tự, bạn có thể viết phương thức để loại bỏ nút từ cuối cùng hoặc khỏi bất kỳ chỉ mục nào. Bạn phải thực hiện chuyển từ đầu đến chỉ mục cụ thể đó và loại bỏ nút như trên bằng cách thay đổi tham chiếu.

Duyệt qua toàn bộ danh sách được liên kết:

/// <summary>
/// Traverse from head and print all nodes value
/// </summary>

public void PrintAllNodes()
{
//Traverse from head
Console.Write("Head ->");
Node curr = head;
while (curr.Next != null)
{
curr = curr.Next;
Console.Write(curr.Value);
Console.Write("->");
}
Console.Write("NULL");
}

Bắt đầu từ đầu và đi qua cho đến khi bạn nhận được nút tiếp theo như null.

Ghi chú: Tương tự, bạn có thể viết mã để xóa nút của chỉ mục cụ thể, chèn nút vào vị trí cụ thể, v.v.

Đến lúc ăn mừng…

Bây giờ đã đến lúc kiểm tra mã của chúng tôi. Để kiểm tra mã của chúng tôi, chúng tôi sẽ viết main phương thức và cuộc gọi danh sách liên kết và các hoạt động của nó trong đó.

class Program
{
    static void Main(string[] args)
    {           
        LinkedList lnklist = new LinkedList();
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.AddAtLast(12);
        lnklist.AddAtLast("John");
        lnklist.AddAtLast("Peter");
        lnklist.AddAtLast(34);
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.AddAtStart(55);
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.RemoveFromStart();
        lnklist.PrintAllNodes();

        Console.ReadKey();
    }
}

Đoán kết quả đầu ra sẽ như thế nào. Nó đây.

Ghi chú: Bài đăng xuất hiện lần đầu trên www.w3techno.blogspot.com.
Bạn có thể download dự án này. Tải về, CLICK HERE.

Bạn có thích bài viết này không? Vui lòng liên hệ với tôi bằng cách để lại bình luận bên dưới.

Triển khai danh sách được liên kết trong C # – VisualGuide.org

mtoplist