Thứ Năm, 22 tháng 7, 2021

Danh sách liên kết đơn – Tất cả thông tin chi tiết nhất

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ế)

  • Kích thước được cố định mọi lúc
  • Trong khi khai báo cần chỉ rõ kích thước
  • Kích thước thay đổi liên tục trong quá trình thêm, bớt phân tử.
  • Kích thước tối đa chỉ phụ thuộc vào bộ nhớ
Cấp phát bộ nhớ

(Danh sách liên kết chiếm ưu thế)

  • Tĩnh: Bộ nhớ được cấp theo chế độ trong quá trình biên dịch.
  • Động: Bộ nhớ được cấp theo chế độ trong quá trình khởi chạy.
Thứ tự và cách sắp xếp

(Danh sách liên kết chiếm ưu thế)

  • Được lưu lại trên một dãy các ô nhớ liền kề
  • Được lưu lại trên các ô nhớ bất kỳ
Truy cập

(Mảng chiếm ưu thế)

  • Bằng cách sử dụng chỉ số mảng, cho phép truy cập đến một phần tử ngẫu nhiên: O(1)
  • Muốn truy cập đến phần tử ngẫu nhiên cần phải trải qua quá trình duyệt từ đầu đến cuối phần tử đó: O(n)
Tìm kiếm

(Mảng chiếm ưu thế)

  • Có thể tìm kiếm bằng 2 ngôn ngữ tuyến tính và nhị phân
  • Chỉ có thể tìm kiếm bằng tuyến tính

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

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

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

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

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