Khái niệm danh sách liên kết đơn đóng vai trò quan trọng trong các thao tác lập trình. Ứng dụng nó mang lại là vô cùng lớn. Vì thế bạn đọc nếu muốn tìm hiểu ngành này thì không thể bỏ qua các kiến thức về danh sách liên kết đơn. Bài viết sau từ Teky sẽ giúp bạn đọc tìm hiểu thêm thông tin về chủ đề này như định nghĩa, đặc điểm và cách cài đặt danh sách liên kết đơn.
Tìm hiểu về danh sách liên kết
Trước khi tìm hiểu về danh sách liên kết đơn, ta sẽ bắt đầu với danh sách liên kết trước. Để cho dễ hình dung, bạn có thể hiểu danh sách liên kết trong C có chức năng khá giống với một mảng. Tuy nhiên vẫn có những điểm khác biệt nhất định. Cách phân biệt danh sách liên kết và mảng như sau:
| Nội dung | Mảng | Danh sách liên kết |
| Kích thước
(Danh sách liên kết chiếm ưu thế) |
|
|
| Cấp phát bộ nhớ
(Danh sách liên kết chiếm ưu thế) |
|
|
| Thứ tự và cách sắp xếp
(Danh sách liên kết chiếm ưu thế) |
|
|
| Truy cập
(Mảng chiếm ưu thế) |
|
|
| Tìm kiếm
(Mảng chiếm ưu thế) |
|
|
Danh sách liên kết đơn (Single linked list) là một trong 3 phân loại của danh sách liên kết C++.
Danh sách liên kết đơn là gì?
Danh sách liên kết đơn còn được gọi là Single Linked List. Nó được dùng để chỉ một cấu trúc dữ liệu di động hay còn có thể hình dung như một danh sách mà trong đó mỗi phần tử đều liên kết với phần tử đứng sau nó.
Mô hình danh sách liên kết đơn
Single Linked List được dùng phổ biến với ngôn ngữ lập trình C++. Trong Linked List C++, mỗi phần tử được cấu tạo nên từ hai thành phần chính. Đó là thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu chịu trách nhiệm lưu trữ thông tin về bản thân phần tử đó. Còn thành phần liên kết sẽ giúp lưu địa chỉ của phần tử đứng sau phần tử chủ thể đó. Nếu phần tử được xét đang đứng cuối danh sách thì thành phần liên kết sẽ bằng NULL. Một phần tử hoàn chỉnh được cấu thành từ data (dữ liệu) và pointer (liên kết) sẽ được gọi là một node (hay còn được gọi là nút).
Đặc điểm của danh sách liên kết đơn
Tính cấp phát dữ liệu động
Trong khi chạy chương trình, Single link list C++ sẽ được cấp phát bộ nhớ. Các phần tử được lưu trữ một cách ngẫu nhiên trong RAM. Khi thêm hoặc bớt phần tử, kích thước của danh sách cũng sẽ thay đổi. Kích thước tối đa của Single linked list trong c++ phụ thuộc vào bộ nhớ khả dụng của RAM.
Tính liên kết của phần tử đầu và phần tử đứng sau
Vì có sự liên kết giữa hai phần đứng trước đứng sau nên chỉ cần nắm được thông tin của phần tử đầu tiên và phần tử cuối cùng là người dùng có thể dễ dàng quản lý được cả danh sách. Tuy nhiên nếu muốn truy cập đến một vị trí bất kỳ thì phải tiến hành duyệt từ đầu đến phần tử đó. Ngoài ra, trong danh sách liên kết đơn C++ cũng chỉ cho phép người dùng tìm kiếm tuyến tính duy nhất 1 phân tử.
Cách cài đặt danh sách liên kết đơn
Tạo node
Một danh sách được tạo lên từ nhiều node. Do vậy ta sẽ đi từ bước tạo node trước. Như đã nói ở trên, một node bao gồm 2 phần là thành phần liên kết và thành phần dữ liệu. Đối với thành phần dữ liệu, bạn có thể tự tạo lên dữ liệu theo ý muốn (class) hoặc sử dụng dữ liệu có sẵn (struct). Còn phần liên kết thì đương nhiên sẽ là con trỏ. Con trỏ này trỏ từ node trước đến node liền kề phía sau.
Với phần ví dụ tạo node này, ta sẽ sử dụng int cho phần dữ liệu như sau:
struct Node
{
int data;
Node* next;
};
Để tạo thêm 1 node mới, ta sẽ tiến hành khởi tạo giá trị ban đầu và trả địa chỉ về cho node được cấp phát.
Node* CreateNode(int init_data)
{
Node* node = new Node;
node->data = init_data;
node->next = NULL;
Node vừa được tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả. Do đó nên phần liên kết gán bằng NULL.
Code danh sách liên kết đơn C++
Thêm một node vào giữa danh sách liên kết đơn
Khi đã có sẵn những node rồi, ta sẽ tiến hành tạo lập 1 list trong C++. Do đặc tính của node là liên kết với nhau nên ta chỉ cần nắm được thông tin của node đầu (head) và nốt cuối (tail) là có thể quản lý được danh sách.
struct LinkedList
{
Node* head;
Node* tail;
};
Khi hàm tạo danh sách mới được hình thành, chúng vẫn chưa có phần tử nào cả. Vì thế ta sẽ gắn phần đầu và cuối tạm vào NULL.
void CreateList(LinkedList& l)
{
l.head = NULL;
l.tail = NULL;
}
Thêm phần tử vào danh sách liên kết đơn
Thêm phần tử đầu
Đầu tiên ta cần xác định xem danh sách liên kết đơn này có rỗng hay không. Nếu danh sách đó rỗng, ta gán luôn head vào node cần thêm. Nếu danh sách không rỗng, ta trỏ liên kết từ head vào node mới. Sau đó mới gán lại head vào node này.
void AddHead(LinkedList& l, Node* node)
{
if (l.head == NULL)
{
l.head = node;
l.tail = node;
}
else
{
node->next = l.head;
l.head = node;
}
}
Thêm phần tử đuôi
Thêm một node vào đuôi danh sách
Tương tự như cách thêm phần tử đầu, ta cũng sẽ xác định xem danh sách này có rỗng hay không. Nếu rỗng thì cho node mới làm tail luôn. Nếu không rỗng thì trỏ tail sẵn có đến node này rồi gán lại tail vào node mới được trỏ.
void AddTail(LinkedList& l, Node* node)
{
if (l.head == NULL)
{
l.head = node;
l.tail = node;
}
else
{
l.tail->next = node;
l.tail = node;
}
}
Thêm vào điểm bất kỳ
Gọi p là node cần thêm, còn q là node đằng trước vị trí cần thêm. Đầu tiên, ta sẽ kiểm tra xem node q có gán với NULL hay không. Nếu có gán tức là danh sách rỗng. Khi đó chỉ cần gán p lên đầu là được. Nếu không, người dùng sẽ thực hiện theo các bước sau: trỏ p->next = q->next, sau đó q->next = p. Khi hoàn thành, phải kiểm tra tiếp q có phải nốt cuối hay không. Nếu phải thì cần tiếp tục gán p vài tail.
void InsertAfterQ(LinkedList& l, Node* p, Node* q)
{
if (q != NULL)
{
p->next = q->next;
q->next = p;
Xóa phần tử khỏi danh sách liên kết đơn
Xóa ở đầu
Đầu tiên, ta tiến hành kiểm tra xem danh sách đó có rỗng không. Nếu có thì trực tiếp xóa đi và để giá trị bằng 0 là được. Còn nếu danh sách không rỗng thì thực hiện theo những bước sau. Đầu tiên là gán lại head vào vị trí đằng sau phần tử cần xóa, nhớ phải lưu head lại. Sau đó mới tiến hành xóa.
int RemoveHead(LinkedList& l, int& x)
{
if (l.head != NULL)
{
Node* node = l.head;
x = node->data; // Lưu giá trị của node head lại
l.head = node->next;
delete node; // Hủy node head đi
if (l.head == NULL)
l.tail = NULL;
return 1;
}
return 0;
}
Xóa ở điểm bất kỳ
Cách xóa một node
Nếu cần xóa node p sau một node q bất kỳ, ta sẽ có 3 trường hợp cần xét:
- Nếu q là NULL suy ra danh sách rỗng, không cần xóa mà chỉ cần chỉnh về 0
- Nếu next của q là NULL, chứng tỏ p là NULL, suy ra p không tồn tại để xóa
- Nếu p có tồn tại, kiểm tra xem p có phải tail không, nếu có thì chỉ cần gán tail lại vào q là được.
int RemoveAfterQ(LinkedList& l, Node* q, int& x)
{
if (q != NULL)
{
Node* p = q->next;
if (p != NULL)
{
if (l.tail == p)
l.tail = q;
q->next = p->next;
x = p->data;
delete p;
return 1;
}
return 0;
}
return 0;
}
Duyệt danh sách liên kết đơn và in
Để kiểm tra xem danh sách đã hoàn chỉnh hay chưa, ta sẽ gán một node bằng head. Sau đó kiểm tra xem node đó NULL hay không. Nếu đã đạt tức là ta đã có dữ liệu của node này. Tiếp tục thực hiện thao tác đó cho đến node NULL, đó chính tail của danh sách.
Mời bạn đọc tham khảo thêm: SQL là gì?
Vậy trong bài viết vừa rồi, Teky đã giúp bạn tìm hiểu thêm về các đặc điểm của danh sách liên kết đơn cũng như cách tạo một danh sách hoàn chỉnh. Mong rằng những kiến thức này sẽ giúp ích cho quá trình học tập và làm việc của bạn.
The post Danh sách liên kết đơn – Tất cả thông tin chi tiết nhất appeared first on TEKY - Học viện sáng tạo công nghệ.
source https://teky.edu.vn/blog/danh-sach-lien-ket-don/
Không có nhận xét nào:
Đăng nhận xét