Trang chủ » Bài 16 – Danh sách liên kết (Phần 1)
Lập trình C/C++

Bài 16 – Danh sách liên kết (Phần 1)

cplusplus

Xin chào mọi người

Có lẽ cũng lâu rồi, mình mới bắt đầu lại mấy series về C++, một phần do website vừa nâng cấp xong (phần còn lại do lười :P). Nên hôm nay mình quyết định viết cho xong series về C++ này để có thể tiếp tục cho những bài viết về sau 🙂

Trước đây, khi muốn lưu trữ 1 khối dữ liệu, ta cần khai báo mảng. Vấn đề xảy ra khi ta khai báo mảng tĩnh là phải ước lượng trước số phần tử, điều đó là hoàn toàn bất khả thi. Về sau ta sử dụng cấp phát động để cấp phát 1 số lượng phần tử trong mảng. Điều này có vẻ rất khả thi, vì ta có thể sử dụng bộ nhớ tối ưu nhất. Tuy nhiên, nếu ta cứ liên tục cấp phát rồi giải phóng bộ nhớ, rất có thể sẽ xảy ra hiện tượng “phân mảnh vùng nhớ” (giống như cài rồi xoá file trong Windows liên tục vậy :D).

Vậy nên, hôm nay mình sẽ giới thiệu về cấu trúc dữ liệu khác, đó chính là Danh sách liên kết (Linked List).

1. Khái niệm

Danh sách liên kết là dãy các phần tử (nút – node) được liên kết với nhau. Thông thường ta liên kết bằng con trỏ.

Hình ảnh dưới đây minh hoạ rất rõ nét về Linked list:

linked-list

Nhìn rất giống các mắt xích với nhau nhỉ? Phía trên là danh sách liên kết đơn, ngoài ra còn có DSLK đôi, DSLK vòng,… nhưng bản chất nó cũng tương tự như DSLK đơn vậy thôi :D.

Hình trên, mỗi ô lớn là 1 node, trong đó chứa Data và 1 con trỏ để trỏ tới node kế tiếp để có tính “liên kết”. Thông thường mình xây dựng node bằng struct:

struct Data {
int x;
};
// Xay dung 1 node
struct Node {
Data data;
Node* ptrNext;
};
// Va cuoi cung la list
struct List {
Node* ptrHead;
Node* ptrTail;
};

 2. Các thao tác trong DSLK

Tất nhiên, muốn thao tác với DSLK thì ta phải khởi tạo nó nhỉ?

void Init(List& list) // Can su dung reference &
{
list.ptrHead = list.ptrTail = NULL;
}
bool isEmpty(List& list)
{
// Neu ca hai nut Head va Tail = NULL thi DSLK rong
return (list.ptrHead == NULL && list.ptrTail == NULL);
}

Tạo 1 node và add vào DSLK, hình minh hoạ dưới đây sẽ giải thích rõ:

add-node-linked-list

// Tao 1 node
Node* createNode(Data data)
{
Node* node = new Node;
node->data = data;
node->ptrNext = NULL;
return node;
}
// Tham so thu 2 co the la Data hoac Node
// Ta danh dau addHead la (1)
void addHead(List& list, Data data)
{
Node* node = createNode(data);
// Kiem tra neu DSLK rong thi add vao Head va Tail
if (isEmpty(list))
{
list.ptrHead = list.ptrTail = node;
}
else
{
node->ptrNext = list.ptrHead
list.ptrHead = node;
}
}
// addTail la (2)
void addTail(List& list, Data data)
{
Node* node = createNode(data);
if (isEmpty(list))
{
list.ptrHead = list.ptrTail = currNode;
}
else
{
list.ptrTail->ptrNext = node;
list.ptrTail = node;
}
}
// addNode la (3)
bool addNode(List& list, Data data, int position)
{
Node* node = createNode(data);
if (isEmpty(list))
{
list.ptrHead = list.ptrTail = node;
}
else
{
int currPos = 0;
Node* currNode = list.ptrHead;
while (currPos < position) {
// Neu day la Tail 
if (currNode == list.ptrTail) return false; 
else currNode = currNode->ptrNext;
++currPos;
}
// Neu add vao Head
// Ta co the viet position == 0
if (currNode == list.ptrHead) addHead(list, data);
else if (currNode == list.ptrTail) addTail(list, data);
else
{
node->ptrNext = currNode->ptrNext;
currNode->ptrNext = node;
}
}
}

Đến đây mình xin tạm kết thúc phần 1 của Danh sách liên kết. Cảm ơn mọi người đã theo dõi! Hẹn gặp lại ở những bài tiếp theo~

Tags

About the author

Võ Hoài Sơn

Tính tình bất định
Chọc vào là bịnh
Rất yêu lập trình
Luôn code hết mình
Mình hiện đang là sinh viên của trường ĐH Khoa học tự nhiên TPHCM. Bản thân rất thích code, kiêm luôn cả mần thơ nên thường hơi hâm hâm dở dở. Ngoài ra chém gió, chém chuối, chém trái cây các kiểu cũng là sở trường của mình. Rất mong được làm quen với các bạn :D

Add Comment