Cách triển khai danh sách được liên kết trong C # nhanh chóng - GraphGuide.org

Trong bài viết này, tôi sẽ thảo luận về một trong những Cấu trúc dữ liệu quan trọng nhất – Danh sách được liên kết.

Tôi sẽ giải thích về:

Danh sách liên kết
Lợi thế của danh sách được liên kết
Các loại danh sách được liên kết
Cách tạo danh sách được liên kết
Các thao tác khác nhau trên danh sách Liên kết.

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

Danh sách liên kết là một cấu trúc dữ liệu tuyến tính bao gồm một nhóm các nút trong một chuỗi. Mỗi nút chứa hai phần.

Dữ liệu – Mỗi nút của danh sách liên kết có thể lưu trữ một dữ liệu.
Địa chỉ – Mỗi nút của danh sách được liên kết chứa một địa chỉ tới nút tiếp theo, được gọi là “Next”.

Nút đầu tiên của danh sách được liên kết được tham chiếu bởi một con trỏ có tên là Head

Ưu điểm của danh sách được liên kết

Chúng có bản chất động và phân bổ bộ nhớ khi và khi được yêu cầu.
Việc chèn và xóa rất dễ thực hiện.
Các cấu trúc dữ liệu khác như Ngăn xếp và Hàng đợi cũng có thể được thực hiện dễ dàng bằng cách sử dụng Danh sách liên kết.
Nó có thời gian truy cập nhanh hơn và có thể được mở rộng trong thời gian liên tục mà không tốn bộ nhớ.
Vì không cần xác định kích thước ban đầu cho một danh sách được liên kết, do đó việc sử dụng bộ nhớ có hiệu quả.
Có thể bẻ khóa ngược trong danh sách được liên kết kép.

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

Danh sách liên kết Singly: Danh sách liên kết đơn chứa các nút có một phần dữ liệu và một phần địa chỉ, tức là Tiếp theo, trỏ đến nút tiếp theo trong chuỗi các nút. Con trỏ tiếp theo của nút cuối cùng sẽ trỏ đến null.

Danh sách liên kết kép: Trong danh sách được liên kết kép, mỗi nút chứa hai liên kết – liên kết đầu tiên trỏ đến nút trước đó và liên kết tiếp theo trỏ đến nút tiếp theo trong chuỗi. Con trỏ trước của nút đầu tiên và con trỏ tiếp theo của nút cuối cùng sẽ trỏ tới vô giá trị.

Danh sách liên kết hình tròn: Trong danh sách liên kết vòng tròn, nút tiếp theo của nút cuối cùng sẽ trỏ đến nút đầu tiên, do đó tạo thành một chuỗi tròn.

Danh sách được liên kết theo vòng tròn kép: Trong loại danh sách liên kết này, con trỏ tiếp theo của nút cuối cùng sẽ trỏ đến nút đầu tiên và con trỏ trước đó của nút đầu tiên sẽ trỏ đến nút cuối cùng.

Tạo danh sách được liên kết

Nút của danh sách liên kết đơn chứa một phần dữ liệu và một phần liên kết. Liên kết sẽ chứa địa chỉ của nút tiếp theo và được khởi tạo thành null. Vì vậy, chúng tôi sẽ tạo định nghĩa lớp của nút cho danh sách liên kết đơn như sau:

```
internal class Node {
```
```
    internal int data;
```
```
    internal Node next;
```
```
    public Node(int d) {
```
```
        data = d;
```
```
        next = null;
```
```
    }
```
```
}
```

Nút cho danh sách được Liên kết đôi sẽ chứa một phần dữ liệu và hai phần liên kết – liên kết trước và liên kết tiếp theo. Do đó, chúng tôi tạo định nghĩa lớp của một nút cho danh sách được liên kết kép như được hiển thị bên dưới.

```
internal class DNode {
```
```
    internal int data;
```
```
    internal DNode prev;
```
```
    internal DNode next;
```
```
    public DNode(int d) {
```
```
        data = d;
```
```
        prev = null;
```
```
        next = null;
```
```
    }
```
```
}
```

Bây giờ, nút của chúng ta đã được tạo, vì vậy, chúng ta sẽ tạo một lớp danh sách liên kết ngay bây giờ. Khi một Danh sách liên kết mới được khởi tạo, nó chỉ có phần đầu là Null. Lớp SinglyLinkedList sẽ chứa các nút thuộc loại Node. Do đó, định nghĩa lớp SinglyLinkedList sẽ giống như bên dưới.

```
internal class SingleLinkedList {
```
```
    internal Node head;
```
```
}
```

Lớp DoublyLinkedList sẽ chứa các nút thuộc loại DNode. Do đó, lớp DoublyLinkedList sẽ trông như thế này.

```
internal class DoubleLinkedList {
```
```
    internal DNode head;
```
```
}
```

Các hoạt động khác nhau trên danh sách được liên kết

Chèn dữ liệu vào trước danh sách được liên kết:

Nút đầu tiên, head, sẽ rỗng khi danh sách liên kết được khởi tạo. Khi chúng ta muốn thêm bất kỳ nút nào ở phía trước, chúng ta muốn phần đầu trỏ đến nó.
Chúng tôi sẽ tạo một nút mới. Nút tiếp theo của nút mới sẽ trỏ đến phần đầu của danh sách được liên kết.
Nút head trước đó bây giờ là nút thứ hai của Danh sách được Liên kết vì nút new được thêm vào phía trước. Vì vậy, chúng tôi sẽ gán head cho nút new.

internal void InsertFront(SingleLinkedList singlyList, int new_data) {

    Node new_node = new Node(new_data);

    new_node.next = singlyList.head;

```
    singlyList.head = new_node;
```
```
}
```

.ie trỏ con trỏ trước đó của nút đầu đến nút mới. Vì vậy, phương thức sẽ như thế này.

Để chèn dữ liệu vào trước danh sách được liên kết kép, chúng ta phải làm theo một bước bổ sungtrỏ con trỏ trước đó của nút đầu đến nút mới. Vì vậy, phương thức sẽ như thế này.

internal void InsertFront(DoubleLinkedList doubleLinkedList, int data) {

    DNode newNode = new DNode(data);

    newNode.next = doubleLinkedList.head;

```
    newNode.prev = null;
```

    if (doubleLinkedList.head != null) {

        doubleLinkedList.head.prev = newNode;

```
    }
```

    doubleLinkedList.head = newNode;

```
}
```

Chèn dữ liệu vào cuối danh sách được liên kết

Nếu Danh sách được Liên kết trống, thì chúng tôi chỉ cần thêm nút mới làm Head của Danh sách được Liên kết.
Nếu Danh sách liên kết không trống, thì chúng ta tìm nút cuối cùng và thực hiện tiếp theo của nút cuối cùng đến nút mới, do đó nút new bây giờ là nút cuối cùng.

internal void InsertLast(SingleLinkedList singlyList, int new_data)

```
{
```

    Node new_node = new Node(new_data);

    if (singlyList.head == null) {

        singlyList.head = new_node;

```
        return;
```
```
    }
```

    Node lastNode = GetLastNode(singlyList);

```
    lastNode.next = new_node;
```
```
}
```

.ie, trỏ con trỏ trước của nút mới đến nút cuối cùng. Vì vậy phương thức sẽ giống như thế này.

Để chèn dữ liệu vào cuối danh sách được liên kết kép, chúng ta phải làm theo một bước bổ sung;, trỏ con trỏ trước của nút mới đến nút cuối cùng. Vì vậy phương thức sẽ giống như thế này.

internal void InsertLast(DoubleLinkedList doubleLinkedList, int data) {

    DNode newNode = new DNode(data);

    if (doubleLinkedList.head == null) {

```
        newNode.prev = null;
```

        doubleLinkedList.head = newNode;

```
        return;
```
```
    }
```

    DNode lastNode = GetLastNode(doubleLinkedList);

```
    lastNode.next = newNode;
```
```
    newNode.prev = lastNode;
```
```
}
```

Nút cuối cùng sẽ là nút tiếp theo trỏ tới null. Do đó, chúng tôi sẽ duyệt qua danh sách cho đến khi chúng tôi tìm thấy nút tiếp theo là null và trả về nút đó là nút cuối cùng. Do đó, phương pháp để lấy nút cuối cùng sẽ là.

internal Node GetLastNode(SingleLinkedList singlyList) {

```
    Node temp = singlyList.head;
```
```
    while (temp.next != null) {
```
```
        temp = temp.next;
```
```
    }
```
```
    return temp;
```
```
}
```

Trong phương pháp được đề cập ở trên, truyền đối tượng doubleLinkedList để lấy nút cuối cùng cho danh sách được liên kết kép.

Chèn dữ liệu sau một nút nhất định của danh sách được liên kết:

Chúng ta phải chèn một nút mới sau một nút nhất định.
Chúng tôi sẽ đặt nút tiếp theo của nút mới thành nút tiếp theo của nút đã cho.
Sau đó, chúng tôi sẽ đặt nút tiếp theo của nút đã cho thành nút mới

Vì vậy, phương pháp cho danh sách được liên kết đơn lẻ sẽ giống như thế này.

internal void InsertAfter(Node prev_node, int new_data)

```
{
```
```
    if (prev_node == null) {
```

        Console.WriteLine(“The given previous node Cannot be null”);

```
        return;
```
```
    }
```

    Node new_node = new Node(new_data);

    new_node.next = prev_node.next;

```
    prev_node.next = new_node;
```
```
}
```

Để thực hiện thao tác này trên danh sách liên kết kép, chúng ta cần làm theo hai bước bổ sung:

Đặt phần trước của nút mới thành nút đã cho.
Đặt nút trước của nút tiếp theo của nút đã cho thành nút new.

Vì vậy, phương thức cho danh sách được liên kết kép sẽ giống như thế này.

internal void InsertAfter(DNode prev_node, int data)

```
{
```
```
    if (prev_node == null) {
```

        Console.WriteLine(“The given prevoius node cannot be null”);

```
        return;
```
```
    }
```

    DNode newNode = new DNode(data);

    newNode.next = prev_node.next;

```
    prev_node.next = newNode;
```
```
    newNode.prev = prev_node;
```
```
    if (newNode.next != null) {
```

        newNode.next.prev = newNode;

```
    }
```
```
}
```

Xóa một nút khỏi danh sách được liên kết bằng cách sử dụng một giá trị khóa nhất định:

Bước đầu tiên là tìm nút có giá trị khóa.
Chúng tôi sẽ duyệt qua danh sách được liên kết và sử dụng thêm một con trỏ để theo dõi nút trước đó trong khi duyệt qua danh sách được liên kết.
Nếu nút cần xóa là nút đầu tiên, thì chỉ cần đặt con trỏ Tiếp theo của Đầu trỏ đến phần tử tiếp theo từ Nút cần xóa.
Nếu nút nằm ở giữa ở đâu đó, thì hãy tìm nút trước nó và tạo Node trước khi nó trỏ đến Node bên cạnh.
Nếu nút bị xóa là nút cuối cùng, thì hãy tìm nút trước nó và đặt nó trỏ thành null.

Vì vậy, phương thức cho danh sách được liên kết đơn lẻ sẽ giống như thế này.

internal void DeleteNodebyKey(SingleLinkedList singlyList, int key)

```
{
```
```
    Node temp = singlyList.head;
```
```
    Node prev = null;
```

    if (temp != null && temp.data == key) {

        singlyList.head = temp.next;

```
        return;
```
```
    }
```

    while (temp != null && temp.data != key) {

```
        prev = temp;
```
```
        temp = temp.next;
```
```
    }
```
```
    if (temp == null) {
```
```
        return;
```
```
    }
```
```
    prev.next = temp.next;
```
```
}
```

Để thực hiện thao tác này trên danh sách được liên kết kép, chúng ta không cần bất kỳ con trỏ bổ sung nào cho nút trước đó vì danh sách được liên kết kép đã có một con trỏ đến nút trước đó. Vì vậy phương pháp xóa sẽ là.

internal void DeleteNodebyKey(DoubleLinkedList doubleLinkedList, int key)

```
{
```

    DNode temp = doubleLinkedList.head;

    if (temp != null && temp.data == key) {

        doubleLinkedList.head = temp.next;

        doubleLinkedList.head.prev = null;

```
        return;
```
```
    }
```

    while (temp != null && temp.data != key) {

```
        temp = temp.next;
```
```
    }
```
```
    if (temp == null) {
```
```
        return;
```
```
    }
```
```
    if (temp.next != null) {
```

        temp.next.prev = temp.prev;

```
    }
```
```
    if (temp.prev != null) {
```

        temp.prev.next = temp.next;

```
    }
```
```
}
```

Đảo ngược danh sách được liên kết Singly.

Đây là một trong những câu hỏi phỏng vấn nổi tiếng nhất. Chúng ta cần đảo ngược các liên kết của mỗi nút để trỏ đến nút trước của nó và nút cuối cùng phải là nút đầu. Điều này có thể đạt được bằng phương pháp lặp cũng như đệ quy. Ở đây tôi đang giải thích phương pháp lặp.

Chúng ta cần thêm hai con trỏ để theo dõi nút trước đó và nút next, khởi tạo chúng thành null.
Bắt đầu duyệt qua danh sách từ nút head đến nút cuối cùng và đảo ngược con trỏ của một nút trong mỗi lần lặp.
Khi danh sách đã hết, hãy đặt nút cuối cùng làm nút head.

Phương thức sẽ như thế này.

public void ReverseLinkedList(SingleLinkedList singlyList)

```
{
```
```
    Node prev = null;
```

    Node current = singlyList.head;

```
    Node temp = null;
```
```
    while (current != null) {
```
```
        temp = current.next;
```
```
        current.next = prev;
```
```
        prev = current;
```
```
        current = temp;
```
```
    }
```
```
    singlyList.head = prev;
```
```
}
```

Kết luận

Chúng tôi đã triển khai danh sách Liên kết đơn và danh sách Liên kết kép bằng C #. Chúng tôi cũng đã thực hiện các hoạt động khác nhau trên chúng. Vui lòng tham khảo mã đính kèm để hiểu rõ hơn. Bạn sẽ tìm thấy thêm một số phương pháp trong đoạn mã đính kèm như tìm phần tử ở giữa và tìm kiếm danh sách được liên kết. Vui lòng đưa ra phản hồi có giá trị của bạn trong phần bình luận.

Hy vọng thông qua bài viết trên của tôi, bạn đã lựa chọn được giải pháp tối ưu nhất giúp giải quyết vấn đề triển khai danh sách được liên kết trong C # đang gặp phải. Nếu còn bất kỳ thắc mắc hay câu hỏi nào, đừng ngại ngần chia sẻ ngay dưới phần bình luận để graphguide.org cung cấp thông tin mới nhất đến bạn. Hẹn gặp lại ở những bài viết tiếp theo! 😉

Hãy xem thêm những bài viết tham khảo dưới đây:

Giới thiệu về ghi đè phương pháp – Giải thích từ khóa ảo, ghi đè và mới trong C #
Triển khai Mảng chuỗi C #
Mảng răng cưa trong C #

Cách triển khai danh sách được liên kết trong C # nhanh chóng – GraphGuide.org

mtoplist