DANH SÁCH LIÊN KẾT ĐƠN
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

Cấu trúc dữ liệu của danh sách liên kết đơn

Trong hướng dẫn này mình sẽ giới thiệu đến các bạn danh sách liên kết đơn là gì, cũng như cấu trúc dữ liệu của nó và cách khai báo danh sách.

Danh sách liên kết đơn là loại DSLK đơn giản và dễ cài đặt nhất trong 3 loại mà chúng ta sẽ học trong series cấu trúc dữ liệu. Để hiểu được nó thì bạn phải có kiến thức nền tảng C++ hoặc C nhé.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

1. Danh sách liên kết đơn là gì?

Danh sách liên kết đơn là một cấu trúc dữ liệu động sử dụng con trỏ để cài đặt và trỏ đến các phần tử trong danh sách.

Trong DSLK đơn thì mỗi phần tử sẽ liên kết với phần tử đứng sau nó trong danh sách, ta gọi là các phần tử đó là Node. Mỗi node có hai thông số cần quan tâm, đó là:

  • Giá trị (data)
  • Mối liên kết tới node khác (pNext).

dslk don la gi PNG

Như hình trên, ở node thứ hai có liên kết với node thứ nhất thông qua pNext, tương tự như vậy node thứ ba liên kết với node thứ hai cũng thông qua pNext.

2. Cấu trúc dữ liệu của DSLK đơn – quản lý bằng pHead

Trong danh sách liên kết đơn ta có mỗi phần tử liên kết với phần tử đứng sau nó trong danh sách. Mỗi phần tử gồm một Node và mỗi Node có hai thông tin: Giá trị (data) và con trỏ pNext trỏ tới phần tử kế tiếp.

Ở phần này chúng ta sẽ quản lý danh sách liên kết bằng 1 con trỏ pHead (trỏ tới phần tử đầu).

Ví dụ: ta có một danh sách liên kết đơn sử dụng pHead để quản lý

dslk don 2 PNG

Trong danh sách ta cần xác định các thông tin sau:

  • pHead là Node đầu của danh sách liên kết đơn.
  • Các giá trị 8, 9, 5 phía bên trái gạch đỏ là giá trị (data) của Node.
  • pNext là con trỏ, trỏ đến phần tử sau.

Dựa vào các thông tin trên, ta có cấu trúc dữ liệu sử dụng pHead để quản lý:

/* 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
}

Như vậy là chúng ta đã khai báo các thông tin có trong một danh sách liên kết đơn sử dụng pHead để quản lý.

3. Cấu trúc dữ liệu của DSLK đơn – quản lý bằng pHead và pTail

Về cơ bản việc sử dụng pHead và pTail để quản lý DSLK đơn tương tự như việc sử dụng pHead. Tuy nhiên khi chúng ta sử dụng pHead và pTail thì việc insertLast() sẽ rất thuận tiện và dễ dàng.

Minh họa danh sách liên kết đơn sử dụng 2 con trỏ pHead và pTail. pHead luôn luôn quản lý node đầu, pTail luôn luôn quản lý node cuối.

cau truc du lieu pheadandptail PNG

Ta có pHead quản lý Node đầu và pTail quản lý Node cuối, vì vậy khi khai báo ở cấu trúc SingleList() chúng ta sẽ khai báo cả pHead và pTail.

/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
  Node *pHead; //Node đầu pHead
  Node *pTail; // Node cuối pTail
};

Cũng như khi khởi tạo giá trị, thì chúng ta sẽ phải khởi tạo cho cả pHead và pTail bằng Null.

void Initialize(SingleList &list)
{
  list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}

Full code: cấu trúc dữ liệu trong DSLK đơn

/* 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
}

Việc sử dụng pHead và pTail có ưu điểm là không cần phải duyệt DSLk khi insertLast, nhưng bù lại nhược điểm của nó sẽ tốn bộ nhớ để khởi tạo biến pTail. Vì vậy các bạn hãy điều chỉnh việc sử dụng hai cách quản lý này cho phù hợp với bài toán.

Kết luận

Trong bài viết này mình đã giới thiệu về danh sách liên kết đơn và cấu trúc dữ liệu của nó. Ở bài tiếp theo chúng ta sẽ cùng nhau thực hiện tạo Node trong danh sách liên kết đơn. Các bạn hãy chú ý theo dõi nhé.

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top