Trong lập trình C#, LinkedList<T> là một cấu trúc dữ liệu thuộc loại danh sách liên kết kép, nơi mỗi phần tử được gọi là một nút (node). Mỗi nút chứa dữ liệu và hai tham chiếu: một trỏ đến nút trước đó và một trỏ đến nút tiếp theo. Điều này cho phép duyệt qua danh sách theo cả hai chiều, từ đầu đến cuối và ngược lại.
Contents
1. Khởi tạo LinkedList
Để sử dụng LinkedList, bạn cần nạp namespace System.Collections.Generic:
using System.Collections.Generic;Bạn có thể khởi tạo một danh sách liên kết với kiểu dữ liệu cụ thể như sau:
LinkedList<string> danhSach = new LinkedList<string>();Trong ví dụ này, danhSach là một danh sách liên kết chứa các chuỗi ký tự.
2. Thao tác với LinkedList
a. Thêm phần tử
- Thêm vào đầu danh sách:
danhSach.AddFirst("Phần tử đầu");- Thêm vào cuối danh sách:
danhSach.AddLast("Phần tử cuối");- Thêm sau một nút cụ thể:
LinkedListNode<string> node = danhSach.Find("Phần tử đầu");
if (node != null)
{
danhSach.AddAfter(node, "Phần tử sau");
}- Thêm trước một nút cụ thể:
LinkedListNode<string> node = danhSach.Find("Phần tử cuối");
if (node != null)
{
danhSach.AddBefore(node, "Phần tử trước");
}b. Xóa phần tử
- Xóa nút đầu tiên:
danhSach.RemoveFirst();- Xóa nút cuối cùng:
danhSach.RemoveLast();- Xóa một nút với giá trị cụ thể:
danhSach.Remove("Phần tử cần xóa");c. Duyệt qua các phần tử
Bạn có thể sử dụng vòng lặp foreach để duyệt qua các phần tử trong danh sách:
foreach (string item in danhSach)
{
Console.WriteLine(item);
}d. Kiểm tra sự tồn tại của phần tử
Để kiểm tra xem một giá trị có tồn tại trong danh sách hay không:
bool tonTai = danhSach.Contains("Giá trị cần kiểm tra");3. Các thuộc tính và phương thức quan trọng
Count: Trả về số lượng nút trong danh sách.
int soLuong = danhSach.Count;First: Trả về nút đầu tiên của danh sách.
LinkedListNode<string> nutDau = danhSach.First;Last: Trả về nút cuối cùng của danh sách.
LinkedListNode<string> nutCuoi = danhSach.Last;4. Lưu ý khi sử dụng LinkedList
- Hiệu suất: Việc thêm hoặc xóa phần tử ở đầu hoặc cuối danh sách liên kết có hiệu suất cao, nhưng truy cập phần tử theo chỉ số sẽ chậm hơn so với mảng hoặc
List<T>. - Sử dụng phù hợp:
LinkedListhữu ích khi bạn cần thường xuyên thêm hoặc xóa phần tử ở đầu hoặc cuối danh sách, hoặc khi cần duyệt qua danh sách theo cả hai chiều.
5. Mục đích sử dụng LinkedList
LinkedList trong C# phù hợp cho các tình huống đặc thù, nơi bạn cần quản lý danh sách các phần tử với các yêu cầu như:
a. Thêm và xóa phần tử nhanh ở đầu hoặc cuối danh sách
- Với
LinkedList, bạn có thể thêm hoặc xóa phần tử ở đầu (AddFirst/RemoveFirst) hoặc cuối (AddLast/RemoveLast) một cách nhanh chóng mà không cần dời các phần tử khác, nhờ vào cấu trúc liên kết. - Ví dụ ứng dụng:
- Quản lý hàng đợi (queue) hoặc ngăn xếp (stack) với các thao tác thêm/xóa linh hoạt.
- Xây dựng thuật toán cần thao tác nhanh trên đầu hoặc cuối danh sách, chẳng hạn như duyệt theo cấp độ trong cây nhị phân.
b. Không cần truy cập phần tử theo chỉ số
LinkedListkhông hỗ trợ truy cập ngẫu nhiên (random access) theo chỉ số, nhưng cho phép duyệt qua từng nút. Điều này hữu ích trong các bài toán mà thứ tự phần tử không quan trọng, hoặc bạn không cần thao tác với vị trí cụ thể.- Ví dụ ứng dụng:
- Triển khai danh sách động cho các thuật toán mà thứ tự xử lý phần tử không phụ thuộc vào chỉ số.
c. Thêm hoặc xóa phần tử tại vị trí bất kỳ
LinkedListcho phép thêm (AddBefore,AddAfter) và xóa phần tử tại các vị trí bất kỳ được xác định bởiLinkedListNode. Đây là một lợi thế so vớiList<T>, vì việc thêm/xóa giữa danh sách liên kết không yêu cầu dịch chuyển các phần tử khác.- Ví dụ ứng dụng:
- Quản lý danh sách yêu cầu hoặc nhiệm vụ, nơi bạn cần thêm hoặc xóa các mục tại một vị trí cụ thể, chẳng hạn thêm yêu cầu ưu tiên.
d. Duyệt danh sách theo cả hai chiều
LinkedListlà danh sách liên kết kép (doubly linked list), cho phép duyệt từ đầu đến cuối và ngược lại. Tính năng này hữu ích trong các thuật toán cần duyệt qua danh sách ở cả hai chiều.- Ví dụ ứng dụng:
- Triển khai undo/redo trong trình soạn thảo văn bản.
- Quản lý lịch sử trình duyệt web.
e. Khi hiệu suất thêm/xóa quan trọng hơn truy cập ngẫu nhiên
- Nếu ứng dụng cần thao tác thêm hoặc xóa phần tử thường xuyên, nhưng không cần truy cập phần tử ngẫu nhiên theo chỉ số,
LinkedListsẽ hiệu quả hơn so vớiList<T>. - Ví dụ ứng dụng:
- Triển khai thuật toán sắp xếp hoặc lọc mà các phần tử cần được thêm vào danh sách một cách linh hoạt.
So sánh nhanh LinkedList và List
| Đặc điểm | LinkedList<T> | List<T> |
|---|---|---|
| Thêm/xóa đầu/cuối danh sách | Hiệu suất cao (O(1)) | Hiệu suất trung bình (O(n)) |
| Thêm/xóa giữa danh sách | Hiệu suất cao nếu đã có LinkedListNode | Phải dời các phần tử khác (O(n)) |
| Truy cập ngẫu nhiên | Không hỗ trợ (chỉ duyệt tuần tự) | Hỗ trợ qua chỉ số (O(1)) |
| Duyệt hai chiều | Có | Không |
| Ứng dụng phổ biến | Thêm/xóa động, quản lý cấu trúc tuần tự | Truy cập ngẫu nhiên, quản lý danh sách cố định |