Generic collection LinkedList trong C#

Một danh sách liên kết (LinkedList) là một dãy các cấu trúc dữ liệu bao gồm một nhóm các nút (node) được kết nối với nhau thông qua các liên kết (link) tạo thành một chuỗi. Mỗi node gồm dữ liệu ở node đó và tham chiếu đến node kế tiếp trong chuỗi.

– Danh sách liên kết là cấu trúc dữ liệu được sử dụng phổ biến thứ hai sau mảng. Dưới đây là các khái niệm cơ bản liên quan tới danh sách liên kết:

• Link (liên kết): mỗi link của một danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử.
• Next: mỗi liên kết của một danh sách liên kết chứa một link tới node sau.
• Prev: mỗi liên kết của một danh sách liên kết chứa một link tới node trước.

– Danh sách liên kết có thể được biểu diễn như là một chuỗi các nút (node). Mỗi node sẽ trỏ tới node kế tiếp.

– Có 3 loại danh sách liên kết LinkedList:

1. Liên kết đơn – Singly Linked List.
2. Liên kết đôi – Doubly Linked List.
3. Liên kết vòng – Circular Linked List.

Xem thêm: Chi tiết về 3 loại danh sách liên kết LinkedList.

– Giả sử đây là bộ nhớ máy tính của chúng ta, những phần màu cam là vùng nhớ đã dùng rồi, còn những phần màu trắng là vùng nhớ chưa dùng:

– Với cấu trúc dữ liệu mảng, giả sử chúng ta có một mảng gồm 4 phần tử, với bộ nhớ như trên thì không thể lưu trữ vào vùng bộ nhớ trống ① và ②, mà phải tìm một bộ nhớ trống có ít nhất 4 phần tử như ③ thì mới đặt vào đủ, và khi kích thước mảng tăng lên thì bộ nhớ ③ không còn phù hợp nữa, sẽ phải đi tìm bộ nhớ trống khác. Đó là hạn chế của array.

– Còn LinkedList thì sao!? Hình bên dưới vùng nhớ màu cam là vùng nhớ đã dùng rồi, ở mỗi vùng nhớ trống LinkedList sẽ chứa 2 phần tử ■■

1. Phần tử đầu tiên ■ lưu trữ giá trị.
2. Phần tử thứ hai ■ lưu trữ một tham chiếu đến node tiếp theo.

Liên kết đơn – Singly Linked List

– Node chứa giá trị (value) và tham chiếu next trỏ đến node tiếp theo. Một node chỉ truy cập đến node sau nó. Node cuối cùng sẽ không trỏ đi đâu cả mà nó sẽ trỏ đến null.

– Liên kết đơn chỉ có thể đi được từ đầu đến cuối danh sách liên kết.

Liên kết đôi – Doubly Linked List

Đây là liên kết mà mỗi node ngoài value, còn có 2 tham chiếu prev và next. Do đó, chúng ta có thể đi tiến hoặc đi lùi đều được.

• Tham chiếu next trỏ đến node tiếp theo.
• Tham chiếu prev trỏ về node phía sau.

Liên kết vòng – Circular Linked List

Liên kết vòng thì tương tự như liên kết đơn, nhưng khác một điều là node cuối cùng không trỏ đến null mà sẽ trỏ đến node đầu tiên. Như vậy, chúng ta có thể vòng đi vòng lại danh sách liên kết.

Nhược điểm

– Kém hiệu quả khi duyệt phần tử, thay đổi giá trị, vì các node nó sự liên kết với nhau.

– Chứa nhiều liên kết node nên bộ nhớ lưu trữ lớn hơn array, tốn nhất là khi chúng ta sử dụng liên kết đôi – Doubly Linked List.

Ưu điểm

– Với kiểu array (list, hash,…)

• Array là cấu trúc dữ liệu liên tục, nên cần thông gian lưu trữ liên tục và đủ lớn để lưu trữ được tất cả các phần tử.
• Việc thêm bớt phần tử khó khăn, vì khi đó cần dịch chuyển vị trí của nhiều phần tử.

– Linked List có ưu điểm hơn:

• Các node của danh sách liên kết có thể lưu trữ trên các vùng nhớ không liên tục, các vùng nhớ bị phân mảnh, do đó tận dụng được vùng nhớ trống.
• Việc thêm, bớt phần tử rất tiện chỉ cần thay đổi liên kết giữa các node.

using System.Collections.Generic;

namespace MinhHoangBlog
{
	class Rect
	{
		public int width { get; set; }
		public int height { get; set; }
	}

	class Program
	{
		static void Main(string[] args)
		{
			// Khai báo
			LinkedList<string> llstr = new LinkedList<string>();
			LinkedList<Rect> llrect = new LinkedList<Rect>
			(
				new Rect[]
				{
					new Rect { width = 0, height = 0 },
					new Rect { width = 1, height = 1 }
				}	
			);

			// Trả về số lượng phần tử
			int nodeCnt = llrect.Count;     // 2

			// Lấy node đầu tiên và node cuối cùng HIỆN TẠI (tại thời điểm get)
			LinkedListNode<Rect> currentFirstNode = llrect.First;
			LinkedListNode<Rect> currentLastNode = llrect.Last;

			// Node có thể có giá trị null, hoặc giá trị trùng nhau
			// Thêm node vào vị trí đầu tiên
			LinkedListNode<Rect> firstNodeOld = llrect.AddFirst(new Rect { width = 2, height = 2 });
			LinkedListNode<Rect> firstNodeNew = llrect.AddFirst(new Rect { width = 3, height = 3 });

			// Thêm một node vào phía sau một node
			llrect.AddAfter(firstNodeNew, new Rect { width = 4, height = 4 });

			// Thêm một node vào phía trước một node
			llrect.AddBefore(firstNodeOld, new Rect { width = 5, height = 5 });

			// Thêm node vào vị trí sau cùng
			llrect.AddLast(new Rect { width = 6, height = 6 });

			// Xóa bỏ một node bằng phần tử truyền vào
			llrect.Remove(new Rect { width = 1, height = 1 });

			// Xóa bỏ node đầu tiên
			llrect.RemoveFirst();

			// Xóa bỏ node cuối cùng
			llrect.RemoveLast();

			// Tìm node đầu tiên có giá trị thỏa mãn
			LinkedListNode<Rect> nodeFindFirst = llrect.Find(new Rect { width = 6, height = 6 });

			// Tìm node cuối cùng có giá trị thỏa mãn
			LinkedListNode<Rect> nodeFindLast = llrect.FindLast(new Rect { width = 6, height = 6 });

			// Xóa toàn bộ node của LinkedList
			llrect.Clear();
		}
	}
}

Xem thêm: LinkedList<T> Class (System.Collections.Generic) | Microsoft Docs.

Cảm ơn bạn đã theo dõi. Đừng ngần ngại hãy cùng thảo luận với chúng tôi!