Danh Sách Liên Kết (linked List) Trong C# | Tự Học ICT

Danh sách liên kết (linked list) là một cấu trúc dữ liệu có vai trò đặc biệt và được sử dụng phổ biến không chỉ trong C# mà trong bất kỳ ngôn ngữ lập trình nào. Linked list là cơ sở để tạo ra các cấu trúc dữ liệu rất quan trọng khác như ngăn xếp (stack), hàng đợi (queue), đồ thị (graph), bảng băm (hash table). Linked list cũng có thể ứng dụng trực tiếp để lưu danh sách các trạng thái của chương trình, ví dụ, để thực hiện tính năng undo/redo. Trong C#, linked list đã được thực thi sẵn trong class LinkedList.

Theo như phân loại các kiểu dữ liệu tập hợp, linked list thuộc về nhóm truy xuất tuần tự (trong khi mảng và danh sách thuộc nhóm truy xuất trực tiếp). Linked list có ưu thế ở chỗ nó có thể lưu trữ một lượng dữ liệu rất lớn mà không cần các khối bộ nhớ liên tục (vd, đây là yêu cầu đối với cấu trúc mảng).

Tiêp theo trong bài học này chúng ta sẽ xem xét chi tiết cấu trúc của linked list và cách thực thi trong C#.

NỘI DUNG CỦA BÀI Ẩn 1. Khái niệm danh sách liên kết (linked list) 2. Phân loại danh sách liên kết 3. Thực thi linked list trong C# 4. Các phương thức cơ bản trên linked list 4.1. Tìm kiếm trong danh sách 4.2. Duyệt danh sách 4.3. Thêm phần tử vào cuối danh sách 4.4. Chèn phần tử vào giữa danh sách 4.5. Bỏ phần tử khỏi danh sách 5. Sử dụng lớp LinkedList trong C# 6. Kết luận

Khái niệm danh sách liên kết (linked list)

Linked list là một tập hợp của các phần tử trong đó mỗi phần tử được liên kết (link) với phần tử trước (và sau nó). Các phần tử của linked list cũng được gọi là các node. Mỗi node bao gồm hai phần: phần dữ liệu, và phần tham chiếu. Phần dữ liệu để lưu trữ dữ liệu (giống như phần tử của mảng). Phần tham chiếu chứa địa chỉ (ô nhớ) của node khác.

Trong linked list, phần tử đầu và phần tử cuối cùng có vai trò rất quan trọng, vì việc truy xuất phần tử (và duyệt danh sách) đều phải bắt đầu từ phần tử đầu tiên và kết thúc ở phần tử cuối cùng. Phần tử đầu tiên thường được gọi là header và được thực thi đặc biệt so với các phần tử còn lại để đánh dấu bắt đầu danh sách. Phần tử cuối cùng thường có phần tham chiếu trỏ tới giá trị null.

Như vậy có thể thấy các điểm khác biệt giữa linked list và mảng nằm ở các điểm sau:

Thứ nhất, các phần tử của mảng được được tham chiếu tới thông qua vị trí của nó (tức là chỉ số – index) trong mảng (so với phần tử đầu tiên). Các phần tử của linked list được tham chiếu tới thông qua quan hệ với phần tử khác. Do đó, không thể truy xuất trực tiếp phần tử của linked list mà phải “trượt” từ đầu (hoặc cuối) danh sách tới phần tử cần truy xuất.

Thứ hai, các phần tử của mảng phải nằm trong các ô nhớ liền kề (do đó mới có thể dùng index – vị trí so với ô đầu tiên – để truy xuất trực tiếp). Các phần tử của linked list không cần nằm trong các ô nhớ liền kề. Do đặc điểm này, linked list sử dụng hiệu quả bộ nhớ hơn so với mảng, cũng như có thể tạo ra các danh sách rất lớn.

Phân loại danh sách liên kết

Ví dụ minh họa chúng ta xem ở phần trên là một danh sách liên kết đơn (single-linked list), trong đó mỗi phần tử trỏ tới phần tử kế tiếp nó trong danh sách. Tức là, mỗi phần tử chỉ chứa tham chiếu (địa chỉ ô nhớ) tới phần tử kế tiếp. Việc duyệt danh sách như vậy chỉ có thể theo một chiều từ đầu danh sách.

Loại thứ hai thường gặp là danh sách liên kết đôi (double-linked list), trong đó mỗi phần tử chứa tham chiếu tới phần tử trước (previous) và sau (next) nó. Danh sách liên kết đôi phải đánh dấu cả phần tử đầu tiên và phần tử cuối cùng. Trường next của phần tử cuối cùng và trường previous của phần tử đầu tiên cùng trỏ tới giá trị Null. Có thể duyệt loại danh sách này theo hai chiều.

Nếu trong danh sách liên kết đôi chúng ta cho trường Next của phần tử cuối cùng trỏ tới phần tử đầu tiên, đồng thời cho trường Previous của phần tử đầu tiên trỏ tới phần tử cuối cùng, chúng ta thu được một loại danh sách khác gọi là danh sách liên kết vòng (circular-linked list).

Danh sách liên kết đơn cũng có thể tạo thành danh sách liên kết vòng đơn khi cho trường Next của phần tử cuối cùng trỏ trở lại phần tử đầu tiên.

Thực thi linked list trong C#

C# đã hỗ trợ sẵn class LinkedList thực thi danh sách liên kết. Tuy nhiên, chúng ta sẽ tự thực hiện một phiên bản riêng để hiểu rõ hơn cách thực thi linked list trong C#. Lớp LinkedList chúng ta sẽ xem xét chi tiết ở phần sau.

using System; namespace P01_CustomLinkedList { class Program { static void Main(string[] args) { Console.Title = "Custom Linked List"; var list = new CustomLinkedList<string>(); list.Add("Hello"); list.Add("world"); list.Add("from"); list.Add("my"); list.Add("LinkedList"); list.Traverse(s=>Console.Write($"{s} ")); list.Remove("my"); Console.WriteLine(); list.Traverse(s => Console.Write($"{s} ")); var n = list.Insert("my", "from"); list.Insert("super", n); Console.WriteLine(); list.Traverse(s => Console.Write($"{s} ")); Console.ReadKey(); } } class Node<T> where T : IComparable { public T Data { get; set; } public Node<T> Next { get; set; } public Node() { Data = default; Next = null; } public Node(T element) { Data = element; Next = null; } } class CustomLinkedList<T> where T : IComparable { public Node<T> Header { get; set; } = new Node<T>(); public Node<T> Find(T data) { var currentNode = Header; while (currentNode.Next != null && currentNode.Data?.CompareTo(data) != 0) currentNode = currentNode.Next; if (currentNode != Header) return currentNode; return null; } public Node<T> FindPrevious(T data) { var currentNode = Header; while ((currentNode.Next != null) && (currentNode.Next?.Data.CompareTo(data) != 0)) currentNode = currentNode.Next; if (currentNode != Header) return currentNode; return null; } public Node<T> Insert(T data, T afterValue) { var newNode = new Node<T>(data); var currentNode = Find(afterValue); if (currentNode != null) { newNode.Next = currentNode.Next; currentNode.Next = newNode; return newNode; } return null; } public Node<T> Insert(T data, Node<T> afterNode) { var newNode = new Node<T>(data) { Next = afterNode.Next }; afterNode.Next = newNode; return newNode; } public Node<T> Add(T data) { var currentNode = Header; while (currentNode.Next != null) { currentNode = currentNode.Next; } var newNode = new Node<T>(data); currentNode.Next = newNode; return newNode; } public void Remove(T data) { var previousNode = FindPrevious(data); if (previousNode != null) { previousNode.Next = previousNode.Next.Next; } } public void Traverse(Action<T> action) { var currentNode = Header; while (currentNode.Next != null) { action?.Invoke(currentNode.Next.Data); currentNode = currentNode.Next; } } } }

Đây là một thực thi đơn giản của danh sách liên kết đơn trên C#. Mã nguồn trên cũng không được tối ưu để sử dụng thực tế.

Linked list này thực hiện được các chức năng:

• Tìm kiếm một node theo giá trị (phương thức Find và FindPrevious). Find tìm ra node có giá trị theo yêu cầu. FindPrevious tìm ra node ngay trước node có giá trị tương ứng.
• Chèn thêm một node vào sau node khác (phương thức Insert với hai overload).
• Chèn thêm một node vào cuối danh sách (phương thức Add).
• Xóa bỏ một node khỏi danh sách (phương thức Remove).
• Duyệt danh sách và thực hiện thao tác xử lý nào đó trên mỗi phần tử (phương thức Traverse).

Để thực thi, chúng ta đã sử dụng kỹ thuật lập trình generic, cũng như lớp generic delegate Action<T>. Dĩ nhiên, có thể có nhiều cách thực thi khác nhau. Chúng ta chỉ làm theo cách đơn giản nhất để mô tả nguyên lý.

Nếu hiểu nguyên lý chung của linked list cùng với code ví dụ trên, chúng ta có thể dễ dàng tạo ra các loại linked list còn lại.

Các phương thức cơ bản trên linked list

Trên linked list có thể thực hiện nhiều phép toán khác nhau. Tuy nhiên, nhóm phương thức sau là quan trọng nhất mà bất kỳ danh sách nào đều phải thực thi. Chúng ta đã thực hiện nó bằng code C# ở phần trên. Ở đây chúng ta sẽ giải thích chi tiết hơn.

Tìm kiếm trong danh sách

Đây là chức năng giúp tìm ra một node có giá trị bằng giá trị cần tìm. Thuật toán tìm kiếm này như sau:

1. Tạo ra một node tạm (trong code trên node tạm được đặt tên là currentNode). Node tạm này có thể hình dung như một con trỏ trượt dọc từ đầu đến cuối danh sách. Nó dừng lại ở node nào thì có thể đọc dữ liệu của node đó, đồng thời lấy thông tin về node tiếp theo để tiếp tục trượt tới. Các thông tin gán qua node tạm sẽ trực tiếp tác động lên node nó trỏ tới. Ban đầu cho node tạm trỏ vào header.
2. Chừng nào trường Next của node đang được xem xét chưa trỏ tới null (tức là chưa đến cuối danh sách), đồng thời trường dữ liệu không chứa giá trị cần tìm thì liên tục trượt node tạm này hướng về cuối danh sách.
3. Nếu tìm thấy node có giá trị phù hợp thì dừng lại và trả lại thông tin về node đó. Nếu trượt đến cuối mà vẫn không tìm thấy thì trả về null, báo rằng trong danh sách không có giá trị cần tìm.

Chức năng này rất quan trọng vì nó được sử dụng khi chèn một node mới vào sau một node đã có.

Duyệt danh sách

Chức năng này giúp chúng ta thực hiện một thao tác xử lý nào đó trên tất cả các phần tử của danh sách, ví dụ, để in ra màn hình. Thuật toán của chức năng này tương tự như tìm kiếm, tuy nhiên điều kiện dừng của quá trình trượt là đạt đến node cuối của danh sách, tức là node có trường Next trỏ tới null.

1. Tạo ra một node tạm (trong code trên được đặt tên là currentNode). Ban đầu cho node tạm trỏ vào header.
2. Chừng nào trường Next của node đang được xem xét chưa trỏ tới null (tức là chưa đến cuối danh sách) thì liên tục trượt node tạm này hướng về cuối danh sách.
3. Khi dừng ở node nào thì thực hiện lệnh do người dùng yêu cầu, ví dụ, in giá trị của node đó ra console.

Thêm phần tử vào cuối danh sách

Đây là phương thức tắt giúp nhanh chóng thêm phần tử vào cuối danh sách. Cách thực hiện như sau:

1. Tạo ra một node tạm. Sử dụng thuật toán duyệt ở trên để đưa node tạm trỏ vào node cuối danh sách.
2. Tạo node mới từ giá trị được cung cấp. Trường Next của node mới phải trỏ tới null.
3. Cho trường Next của node tạm trỏ vào node mới.

Lưu ý rằng, node tạm thực chất chỉ là một con trỏ tới node đang xem xét nên tác động vào node tạm cũng chính là tác động vào node đang được duyệt.

Chèn phần tử vào giữa danh sách

Đây là chức năng sử dụng nhiều nhất trong danh sách liên kết. Nhiệm vụ của nó là chèn một node mới vào sau một node chỉ định. Cách thực hiện như sau:

1. Sử dụng phương thức tìm kiếm ở trên để trượt node tạm tới ô chỉ định.
2. Tạo node mới từ giá trị được cung cấp.
3. Cho trường Next của node mới trỏ tới cùng node như trường Next của node tạm.
4. Cho trường Next của node tạm trỏ tới node mới.

Bỏ phần tử khỏi danh sách

Để bỏ phần tử khỏi danh sách, chúng ta phải xây dựng thêm một phương thức tìm kiếm khác. Phương thức tìm kiếm mới này không tìm tới đúng node có giá trị như chỉ định (tức là node cần xóa), mà là tìm tới node nằm trước nó.

Khi tìm kiếm được node phù hợp, trường Next của nó sẽ được điều chỉnh để trỏ tới node phía sau node cần xóa. Node cần xóa giờ không có node nào trỏ tới nữa, tương đương với việc nó bị loại khỏi danh sách.

Vấn đề mấu chốt trong tất cả các phương thức trên là duy trì liên kết giữa các node, thứ hai là “trượt” qua các liên kết để tìm đến node có giá trị cần thiết. Để hiểu hai vấn đề này bạn cần nắm rõ khái niệm tương tự như con trỏ (pointer) trong C/C++ hay tham chiếu (reference) trong C#. Nếu không hình dung được cách hoạt động của pointer hoặc reference, bạn sẽ rất khó hình dung ra cách thức hoạt động của linked list. Nếu cảm thấy vướng mắc ở đây, bạn nên tạm dừng để đọc kỹ lại về pointer hay reference (không quan trọng ngôn ngữ nào, chủ yếu để nắm được ý tưởng của nó).

Sử dụng lớp LinkedList trong C#

Class CustomLinkedList mà chúng ta làm ở trên chỉ mang tính minh họa chứ không sử dụng trong thực tế. Như đã nói, C# đã xây dựng sẵn lớp LinkedList và chúng ta có thể sử dụng ngay, thay vì phải tự mình xây dựng. Trong phần này, chúng ta sẽ tìm hiểu lớp LinkedList thông qua thực hiện một ví dụ.

Trong ví dụ này chúng ta sẽ sử dụng LinkedList để xây dựng một chương trình đọc sách rất đơn giản với giao diện console. Mỗi lần chương trình chỉ hiển thị văn bản từ một trang sách. Chúng ta sử dụng các phím tắt P (previous) và N (next) để chuyển qua lại giữa các trang.

Bạn có thể dễ dàng hình dung, văn bản của một cuốn sách chia theo từng trang dĩ nhiên là một danh sách liên kết. Mỗi trang sẽ là một node. Việc đọc sách đương nhiên nên theo tuần tự trang.

using System; using System.Collections.Generic; using System.IO; using System.Text; namespace P02_LinkedList_BookReader { class Program { static void Main(string[] args) { Console.OutputEncoding = Encoding.Unicode; var pages = Open("Chú lính chì dũng cảm.txt"); var current = pages.First; while (current != null) { Console.Clear(); Console.WriteLine($"- page {current.Value.Number} -\r\n"); Console.WriteLine(current.Value.Content); Console.WriteLine("\r\n< Previous [P] | [N] Next >"); switch (Console.ReadKey(true).Key) { case ConsoleKey.N: if (current.Next != null) { current = current.Next; } break; case ConsoleKey.P: if (current.Previous != null) { current = current.Previous; } break; default: return; } } } static LinkedList<Page> Open(string file, int charPerPage = 1000) { Console.Title = Path.GetFileNameWithoutExtension(file); LinkedList<Page> pages = new LinkedList<Page>(); var content = File.ReadAllText(file); var p = 0; for (p = 0; p < content.Length / charPerPage; p++) { var pageContent = content.Substring(charPerPage * p, charPerPage); pages.AddLast(new Page { Number = p + 1, Content = pageContent }); } pages.AddLast(new Page { Number = p + 1, Content = content.Substring(charPerPage * p) }); return pages; } } class Page { public int Number { get; set; } public string Content { get; set; } } }

Có thể nhận xét, LinkedList trong C# hỗ trợ danh sách liên kết đôi nhưng không vòng. Từ tên gọi có thể dễ dàng suy ra chức năng của các phương thức. Về đại thể nó rất gần với lớp CustomLinkedList chúng ta xây dựng ở phần trước.

Trong chương trình trên, chúng ta đọc toàn bộ text từ một file văn bản (plain text – txt), rồi cắt thành từng phần nhỏ. Mỗi phần chứa 1000 ký tự. Mỗi phần nhỏ này sẽ tạo thành một object của Page. Các object này lần lượt được gắn vào một danh sách liên kết tạo ra bởi lớp LinkedList<Page>.

Khi ấn N (next) thì sẽ trượt node tạm (tức là node hiện tại, trong code trên là biến current) về cuối thêm 1 đơn vị. Nếu ấn P (previous) thì trượt node hiện tại về đầu thêm 1 đơn vị. Nếu ở đầu và cuối danh sách thì lệnh P và N mất tác dụng.

Bạn cũng có thể cải tiến chương trình trên để nó đọc được file truyện plain text bất kỳ khi chạy từ Command Prompt, thay vì code cứng tên file trong chương trình.

Kết luận

Trong bài học này chúng ta đã xem xét chi tiết về danh sách liên kết (linked list) và cách thức xây dựng nó trong C#. Chúng ta cũng đã biết rằng, C#, khác với một số ngôn ngữ, đã xây dựng sẵn lớp LinkedList thực thi danh sách liên kết đôi. Chúng ta có thể sử dụng ngay lớp LinkedList này mà không cần tự mình xây dựng lại nữa.

Lưu ý rằng, danh cách liên kết là một nội dung rất quan trọng vì nó được ứng dụng khi xây dựng các cấu trúc dữ liệu khác mà chúng ta sẽ xem xét trong khóa học này.

Chúc bạn học tốt!

[wpdm_package id=’10332′]

+ Nếu bạn thấy site hữu ích, trước khi rời đi hãy giúp đỡ site bằng một hành động nhỏ để site có thể phát triển và phục vụ bạn tốt hơn.+ Nếu bạn thấy bài viết hữu ích, hãy giúp chia sẻ tới mọi người.+ Nếu có thắc mắc hoặc cần trao đổi thêm, mời bạn viết trong phần thảo luận cuối trang.Cảm ơn bạn!