Cấu trúc dữ liệu của DSLK đơn

Trong bài viết này, codehow sẽ giới thiệu đến các bạn cấu trúc dữ liệu của DLSK đơn trong C / C++. Đây là dạng cấu trúc dữ liệu đơn giản nhất trong ba loại danh sách liên kết trong đó có danh sách liên kết đôi và danh sách liên kết vòng.

Để hiểu được các bài viết trong series cấu trúc dữ liệu này, các bạn cần có kiến thức cơ bản về ngôn ngữ lập trình C và C++.

Chúng ta sẽ tìm hiểu về cấu trúc dữ liệu của DSLK đơn là gì? Cấu trúc và cách cài đặt nó như thế nào? Bây giờ thì hãy bắt đầu cùng mình thôi nhé.

Danh sách liên kết đơn (DSLK đơn) là gì?

Mỗi phần tử trong danh sách đều được liên kết với phần tử ngay phía sau nó thông qua một liên kết (Linked). Mỗi phần tử được gọi là một node hoặc một nút.

Một node bao gôm hai phần:

• data: Giá trị của node.
• pNext: Đây là liên kết với phần tử ngay phía sau nó.

Các bạn hãy nhìn hình bên trên, các node được nối với nhau thông qua pNext. Đặc biệt đối với node cuối cùng, nó sẽ trỏ đến giá trị NULL.

Để hiểu rõ hơn về bản chất của DSLK đơn, các bạn hãy qua phần tiếp theo. Ở đó mình sẽ đưa ra các đặc điểm của DSLK đơn nhé.

Đặc điểm của DSLK đơn

Như đã nói thì DSLK đơn là một cấu trúc dữ liệu động và được tạo nên thông qua việc cấp phát động. Vậy nên nó có một số đặc điểm sau đây:

• Các phần tử được lưu trữ ngẫu nhiên trong bộ nhớ khả dụng của RAM.
• Khi chạy chương trình bộ nhớ sẽ được cấp phát tự động.
• Kích thước động, có thể thay đổi tùy biến theo các thao tác thêm, sửa, xóa.
• Không cần phải khai báo kích thước.
• Truy xuất các phần tử tuần tự.
• Có thể quản lý danh sách thông qua phần tử đầu hoặc cuối.

Trên đây là một số đặc điểm đặc trưng của DSLK đơn, ngoài ra nó còn một số đặc điểm, tính năng khác nữa. Trong quá trình sử dụng các bạn sẽ tự rút ra cho bản thân nhé.

Cấu trúc dữ liệu của DSLK đơn

Về cấu trúc dữ liệu của danh sách liên kết đơn, chúng ta có thể cài đặt và quản lý DSLK đơn bằng hai cách. Cách thứ nhất là sử dụng pHead (node đầu) để cài đặt và quản lý DSLK đơn. Cách thứ hai là sử dụng cả pHead (node đầu) và pTail (node cuối) để cài đặt và quản lý DSLK đơn.

Bây giờ chúng ta sẽ đi vào tìm hiểu từng cách thôi nhé.

Cách 1: quản lý bằng pHead

Trước khi đi vào cài đặt DSLK đơn sử dụng pHead, mình nhắc lại một số thông tin để các bạn nắm nhé.

• Mỗi phần tử được gọi là một node.
• Mỗi node có hai phần đó là data và pNext.
• Mỗi phần tử (mỗi node) được liên kết với phần tử ngay phía sau nó thông qua con trỏ pNext.

Ví dụ: Mình có một DSLK đơn sử dụng con trỏ pHead để quản lý dưới đây.

Trong đó:

• pHead: node đầu tiên của danh sách.
• pNext: Con trỏ để trỏ tới phần tử kế tiếp.
• Các số 8, 9, 5 bên phải node chính là data (giá trị của node).

Trên đây là cấu trúc của một danh sách liên kết đơn được cài đặt và quản lý bằng pHead, vậy làm thế nào để thực hiện nó bằng ngôn ngữ C và C++. Các bạn có thể tham khảo ngay phía bên dưới nhé.

/* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */
struct Node
{
  int data;// giá trị data của node
  Node *pNext;// con trỏ pNext
};
/* Khai báo Node đầu pHead */
struct SingleList
{
  Node *pHead; //Node đầu pHead
};
/* khởi tạo giá trị cho Node */
void Initialize(SingleList &list)
{
  list.pHead=NULL;// khởi tạo giá trị cho Node là Null
}

Để cài đặt DSLK đơn sử dụng con trỏ pHead, ta cần các cấu trúc như sau:

• Cấu trúc khai báo data và pNext.
• Cấu trúc khai báo pHead.
• Hàm khởi tạo giá trị cho con trỏ pHead.

Như vậy là chúng ta đã khai báo xong các thông tin cần có trong một DSLK đơn được quản lý bằng pHead.

Cách 2: quản lý bằng pHead và pTail

Về cơ bản thì việc quản lý bằng pHead & pTail tương tự như việc quản lý bằng pHead. Tuy nhiên nếu chúng ta sử dụng cách này, việc truy xuất sẽ dễ dàng hơn rất nhiều.

Ví dụ: Giả sử chúng ta muốn truy xuất phần tử cuối cùng. Nếu sử dụng pHead không thôi thì chúng ta phải truy xuất tuần tự từ đầu danh sách. Còn nếu sử dụng pHead và pTail thì chúng ta chỉ cần truy xuất phần tử cuối chính là pTail.

pHead luôn luôn quản lý node đầu và pTail quản lý node cuối, như hình dưới đây:

/* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */
struct Node
{
  int data;// giá trị data của node
  Node *pNext;// con trỏ pNext
};
/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
  Node *pHead; //Node đầu pHead
  Node *pTail; // Node cuối pTail
};
/* khởi tạo giá trị cho Node đầu và Node cuối */
void Initialize(SingleList &list)
{
  list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}

Tương tự như việc quản lý bằng pHead, chúng ta cần tạo các cấu trúc dưới dây:

• Cấu trúc khai báo data và pNext.
• Cấu trúc khai báo pHead và pTail.
• Hàm khởi tạo giá trị cho pHead và pTail.

Mặc dù sử dụng cách này sẽ truy xuất dữ liệu sẽ nhanh hơn, tuy nhiên chúng ta sẽ tốn bộ nhớ để lưu trữ thêm pTail. Các bạn hay xem bài toán như thế nào để cân nhắc việc sử dụng một trong hai cách nhé.

Kết luận

Như vậy là chúng ta đã cùng nhau tìm hiểu về cấu trúc của DSLK đơn trong C / C++. Qua bài viết này, mình cần các bạn nắm rõ các kiến thứ sau đây:

• Danh sách liên kết đơn là gì?
• Đặc điểm của danh sách liên kết đơn.
• Có hai cách cài đặt và quản lý DSLK đơn đó là: Sử dụng pHead và sử dụng pHead & pTail.

Ở bài viết tiếp theo, mình sẽ hướng dẫn các bạn cách tạo node mới trong DSLK đơn, các bạn chú ý theo dõi nhé. Cảm ơn các bạn rất nhiều !!!