STDIO
Tìm kiếm gần đây

    Nội dung

    Danh Sách Liên Kết Đơn

    24/09/2014
    30/06/2020
    Cơ bản về danh sách liên kết trong C/C++, bao gồm mô tả, giải thuật và code mẫ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ó.

    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 2013 trê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. 

    ss_1

    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

    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

    ss_2

    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

    ss_3

    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 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;

    ss_4

    Xóa một phần tử đầu danh sách

    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 = 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;

    ss_5

    Xóa một phần tử đứng sau phần tử q

    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 = q->pNext;

    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;
    

    ss_6

    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.

    Bài viết liên quan

    Linked List - Stack - Queue

    Danh sách liên kết là một trong những cấu trúc phổ biến và thường được sử dụng để quản lý dữ liệu trong chương trình. Bài viết này giới thiệu một số cấu trúc dữ liệu phổ ...

    Hiếu Nguyễn18/11/2014

    HTML - Phần 3: Các Thẻ Định Dạng Danh Sách

    Tiếp nối chuỗi bài viết về lập trình web cơ bản với HTML, thì trong bài viết hôm nay tôi sẽ đề cập đến các thẻ định dạnh danh sách (ul, ol, li) trong HTML. Các thẻ danh ...

    Nguyễn Nghĩa25/10/2015

    HTML - Phần 4: Thẻ Liên Kết Trong HTML

    Thẻ liên kết được xem như là trái tim của một trang web. Một trang web thông thường không thể thiếu thẻ liên kết, thẻ liên kết giúp điều hướng giữa các trang trong một ...

    Nguyễn Nghĩa25/10/2015

    Thỏa Thuận Sử Dụng Dịch Vụ STDIO

    Thỏa thuận này quy định về điều kiện giao kết hợp đồng, quyền lợi, nghĩa vụ và các vấn đề pháp lý khác có liên quan đến người sử dụng, người đọc, người viết khi truy cập ...

    STDIO07/04/2014

    Ứng Dụng Stack - Biểu Thức Trung Tố (Infix)

    Ứng dụng Stack trong bài toán trung tố, hậu tố và tiền tố là một trong những ứng dụng quan trọng của Stack và là một vấn đề hay đối với bạn đọc. Trong đó bài toán về ...

    Tran Khanh Nguyen02/04/2017

    CBP-3: Khai Báo Component Cơ Bản, Tích Hợp Component Vào Entity

    Khai báo component CAnimation để thêm hình ảnh hiển thị cho Entity, đây là một Component tiêu biểu và có liên quan đến một số Component khác nên tôi sẽ hiện thực để độc ...

    Tuấn Trần20/08/2015

    Stack – Ngăn Xếp

    Stack – Ngăn xếp là cấu trúc dữ liệu quan trọng , là kiến thức không thể thiếu trong khoa học máy tính và được ứng dụng rất nhiều trong lập trình. Nó là kiểu dữ liệu cơ ...

    Bùi Nguyễn Minh Hoàng30/08/2015

    STL - List Trong C++

    STL là viết tắt của cụm từ Standard Template Library, là bộ thư viện chuẩn của C++, STL cung cấp các lớp cài đặt sẵn, cho phép thao tác với các kiểu dữ liệu cơ bản cũng ...

    Trung Nguyễn21/09/2014

    Các Thẻ - Tag Thông Dụng Trong HTML

    HTML (Hyper text markup languague) là một dạng ngôn ngữ được dùng để tạo nên các trang web. HTML là một ngôn ngữ trình bày, và nếu có điều gì đó khác biệt giữa một ngôn ...

    Tuấn Trần18/08/2015

    Sử Dụng CSDL Hướng Đối Tượng DB4O Với Android - Phần 2 Thực Hiện App Đơn Giản - Chương Trình Trắc Nghiệm

    Tiếp theo bài viết 'Sử dụng hệ quản trị cơ sở dữ liệu DB4O trên Android', bài viết này sẽ hướng dẫn xây dựng một chương trình trắc nghiệm đơn giản và tập trung vào các ...

    Nguyễn Hồng Sơn15/03/2016

    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    [email protected]

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020