- Danh sách liên kết đơn là gì?
- Tại sao phải dùng danh sách liên kết để lưu trữ dữ liệu?
Kiến thứ Yêu cầu:
Linked List = Pointer + Struct (class)
I. Danh sách liên kết đơn là gì?
- Cấu tạo
Gồm dãy các Node liên kết với nhau, mỗi Node gồm 2 thành phần:
- Data: là dữ liệu của node
- pNext: Con trỏ trỏ tới node kế tiếp
-----------------------------------------------------------
2 điều cơ bản cần nắm cho sự khác biệt của Linked List mạnh hơn mảng là
- cấp phát động, dùng bao nhiêu cấp phát bấy nhiêu khiến cho bộ nhớ cần dùng không bị dư lãng phí cũng như không bị thiếu. dễ dàng thêm vào
- đối với mạng các dự liệu phải liền kề nhau nhưng đối với Linked List thì các member không nhất thiết phải gần nhau vì nó quản lý theo kiểu con trỏ, dùng địa chỉ nên nếu trong trường hợp bộ nhớ còn 5 bộ nhớ trống nhưng 5 cái đó nó không nằm gần nhau khi đó chỉ có thể dùng Linked List để lưu trữ.
/*------------------------------------------------------------------------------------------------------*/
Giới thiệu
Danh sách liên kết là 1 cấu trúc dữ liệu cơ bản, được sử dụng để khắc phục hạn chế của mảng (cố định về kích thước). C++ nói chung và cụ thể là thư viện STL đã cung cấp sẵn một kiểu dữ liệu List. Tuy nhiên tôi vẫn muốn chia sẻ bài viết này để nêu rõ về bản chất của danh sách liên kết và một số thao tác cơ bản trên nó.
Tiền đề bài viết
Trong quá trình nghiên cứu tôi nhận thấy danh sách liên kết đơn là một cấu trúc dữ liệu khá thú vị, và nhờ nó tôi hình dung rõ hơn về chức năng lưu trữ địa chỉ của con trỏ. Do đó, tôi muốn chia sẻ với mọi người một số kiến thức cơ bản về danh sách liên kết (linked-list).
Đối tượng hướng đến
Bài viết dành cho các bạn lập trình viên đã có kiến thức cơ bản về struct và pointer trong ngôn ngữ C++, có nhu cầu tìm hiểu về cấu trúc dữ liệu danh sách liên kết (linked list).
Toàn bộ code trong các ví dụ minh họa bên dưới được tôi thực hiện với Visual Studio Propressional 2013trên môi trường Windows 8.1.
Tổ chức danh sách liên kết đơn
Cũng giống như mảng, danh sách liên kết cũng bao gồm các phần tử, có mối liên hệ với nhau. Tôi gọi mỗi phần tử đó là một Node. Node được xem là trái tim của danh sách liên kết, mỗi Node sẽ lưu trữ 2 thông tin:
- Thông tin dữ liệu: Lưu trữ các thông tìn về chính Node đó.
- Thông tin liên kết: Lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu phần tử đó nằm cuối danh sách.
Một cách tổng quát ta có:
- struct SNode
- {
- Data Info;
- SNode* pNext;
- };
Mỗi phần tử trong trong danh sách liên kết đơn là một biến động sẽ được yêu cầu cấp phát khi cần thiết, danh sách liên kết đơn chính là sự liên kết các biến này với nhau do đó ta hoàn toàn chủ động về số lượng các phần tử.
Để đơn giản, trong bài viết này tôi sẽ lấy ví dụ danh sách liên kết đơn lưu trữ các số nguyên.
Node của danh sách liên kết sẽ được định nghĩa như sau:
- struct SNode
- {
- int Data;
- SNode* pNext;
- };
Tôi sử dụng một phương thức GetNode để cấp phát động một Node khi cần thiết:
- SNode* GetNode(int x)
- {
- SNode *p = new SNode;
- p->Data = x;
- p->pNext = NULL;
- return p;
- }
Bây giờ chúng ta bắt đầu tìm hiểu một số phương thức đơn giản tạo nên sự liên kết các Node để tạo ra một danh sách liên kết đơn hoàn chỉnh.
Một số thao tác cơ bản trên danh sách liên kết đơn
Trong danh sách liên kết đơn, các Node sẽ không được lưu liên tiếp nhau trên bộ nhớ, Node trước sẽ mang thông tin địa chỉ của Node sau, như vậy nếu bạn xử lý lỗi một Node sẽ dẫn đến tính huống xấu nhất, ta sẽ mất toàn bộ thông tin của các Node phía sau.
Chúng ta sẽ bắt đầu làm việc với các thao tác cơ bản trên một danh sách liên kết đơn. Giả sử tôi có định nghĩa sau:
- struct SNode
- {
- int Data;
- SNode* pNext;
- };
- struct SList
- {
- SNode* pHead;
- SNode* pTail;
- SList(){}
- SList(SNode* Head, SNode* Tail)
- {
- this->pHead = Head;
- this->pTail = Tail;
- }
- };
Nếu biết được địa chỉ đầu tiên trong danh sách liên kết ta có thể dựa vào thông tin pNext để truy xuất đến các phần tử còn lại, do đó ta sẽ dùng một con trỏ pHead để lưu lại địa chỉ Node đầu tiên của danh sách. Trong một số trường hợp ta cũng cần thao tác trên phần tử cuối cùng của danh sách, nên tôi dùng thêm một con trỏ pTail để lưu trữ địa chỉ của Node cuối cùng trong danh sách.
Chèn vào đầu danh sách
Như đã trình bày ở trên, khi thao tác với mỗi Node trên danh sách liên kết ta cần thực hiện cẩn thận, đúng thứ tự để tránh mất thông tin của các Node phía sau. Dưới đây là thứ tự các bước chèn một phần tử vào đầu mảng.
Bước 1: cấp phát một Node mới (new_element).
Bước 2: gán pNext của Node mới trỏ đến Node đầu (cũ).
- new_element->pNext = pHead;
Bước 3: cập nhập lại giá trị pHead. Chính là cập nhật lại địa chỉ, thay đổi địa chỉ của nó về với node đầu mình tạo ra. và do node này cần phải đứng đầu tiên trong Linked List nên nó sẽ chứa địa chỉ của pHead.
- pHead = new_element;
Lưu đồ bên dưới thể hiện từng bước để thêm vào một Node mới ở đầu danh sách
Chèn vào cuối danh sách
Tương tự với thao tác chèn vào đầu danh sách, chèn vào cuối danh sách chúng ta chỉ cần cập nhập lại con trỏ pTail.
Bước 1: cấp phát một Node mới (new_element).
Bước 2: gán lại pNext của Node cuối cùng (cũ) sẽ trỏ đến Node mới.
- pTail->pNext = new_element;
Bước 3: cập nhập lại giá trị pTail, bây giờ Node cuối của danh sách là Node chúng ta vừa thêm.
- pTail = new_element;
Đây là lưu đồ thứ tự thực hiên các bước ở trên
Chèn vào danh sách sau một phần tử q
Chèn vào danh sách sau một phần tử q nào đó, chèn vào giữa danh sách không cần cập nhập lại hai con trỏ pHead và pTail tuy nhiên chúng ta cần hết sức cần thận để tránh mất dữ liệu phía sau.
Bước 1: cấp phát một Node mới - new_element.
Bước 2: gán pNext của Node mới bằng địa chỉ của Node sau q.
- new_element ->pNext = q-> pNext;
Bước 3: cập nhập lại pNext của Node q trỏ đến Node mới.
- q-> pNext = new_element;
Xóa một phần tử đầu danh sách
Tương tự như thao tác xóa phần tử đầu danh sách, để xóa một phần tử đứng sau phần tử q, ta thực hiện các bước sau:
Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.
- SNode* p = pHead;
Bước 2: cập nhập lại giá trị của pHead.
- pHead = pHead->pNext;
Bước 3: giải phóng vùng nhớ của Node cần xóa.
- delete p;
Xóa một phần tử đứng sau phần tử q
Xóa 1 phần tử ở đầu danh sách không chỉ đơn giản là cập nhập lại biến con trỏ pHead, mà ta phải giải phóng được vùng nhớ của Node cần xóa.
Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.
- SNode* p = q;
Bước 2: cập nhập lại giá trị pNext của Node q.
- q->pNext = p->pNext;
Bước 3: giải phóng vùng nhớ của Node cần xóa.
- delete p;
Duyệt danh sách
Khi có được giá trị của pHead ta có thể dựa và thông tin pNext để duyệt lần lượt các phần tử của danh sách.
- SNode* p;
- p = list.pHead;
- while (p != NULL)
- {
- // Process Node
- p = p->pNext;
- }
Lời kết
Source code được viết theo hướng cấu trúc để các bạn chưa có khái niệm về hướng đối tượng có thể tiếp cận một cách dễ dàng.
Có thể thấy được, danh sách liên kết đã khắc phục được nhược điểm của mảng - đó là kích thước cố định.Với bài viết này, hy vọng các bạn đã có cái nhìn tổng quát hơn về danh sách liên kết và các thao tác liên quan như: thêm phần tử, xóa phần tử ... và có thể ứng dụng được vào các dự án của mình.
0 comments :
Post a Comment