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

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

cplusplus

Xin chào mọi người

Trong lập trình có 1 phương thức kĩ thuật là CRUD (Create, Read, Update, Delete), kỹ thuật này giúp cho việc quản lý dữ liệu dễ dàng hơn, code trở nên linh hoạt hơn.

Liệu rằng điều mình nói ở trên có liên quan gì với DSLK?

Ở phần 1, mình đã giới thiệu về cách khởi tạo và thêm node vào trong DSLK. Vậy thì nó có giống giống ký tự “C” (Create) trong CRUD nhỉ? Hôm nay mình sẽ giới thiệu về 3 ký tự “R” “U” “D” còn lại, đó chính là cách đọc, sửa và xoá node trong DSLK.

3. Đọc/sửa node trong DSLK

Các bạn đọc sơ qua code, mình sẽ giải thích ở dưới:

// Tìm node kế tiếp trong DSLK
Node* getNext(List list, Node* currNode)
{
  // Nếu node hiện tại là Tail
  if (currNode == list.ptrTail) return NULL;
  else return currNode->ptrNext;
}

// Tìm node trước đó trong DSLK
Node* getPrev(List list, Node* currNode)
{
  // Nếu node hiện tại là Head
  if (currNode == list.ptrHead) return NULL;
  else
  {
    Node* node = list.ptrHead;
    // Tìm node kế tiếp dựa vào currNode
    while (node->ptrNext != currNode)
      if (node->ptrNext != list.)node = node->ptrNext;
    
  }
}

// Tìm node theo index cho trước
Node* getNode(List list, int index)
{
  int position = 0;
  Node* currNode = list.ptrHead;
  while (position < index) { ++position; if (currNode == list.ptrTail) return NULL; else currNode = currNode->ptrNext;
  }
  return currNode;
}

Hàm getNext cho phép ta lấy 1 node ở phía sau node hiện tại (currNode), nếu currNode là Tail thì dĩ nhiên làm gì còn node nào phía sau nữa 😀 nó sẽ trả về NULL. Tương tự hàm getPrev cho phép ta lấy 1 node ở phía trước currNode. Tuy nhiên các bạn cần lưu ý.

Do tính chất của DSLK đơn là con trỏ trong 1 node chỉ trỏ theo 1 chiều (mà thường ta chọn trỏ tới node kế tiếp), nên ta không thể lấy node phía trước theo cách thông thường được. Ta cần phải tạo 1 vòng lặp từ Head đến currNode, và lấy node ngay phía trước nó theo điều kiện đặt sẵn trong hàm.

Mở rộng ra, ta có hàm getNode. Hàm này có chức năng tương tự như mảng 1 chiều, lấy giá trị theo index được cho. Và việc ta cần làm là kiểm tra “liệu rằng index có nằm trong DSLK hay không“. Đó là tất cả những gì cần có để duyệt DSLK đơn.

Tất nhiên, một khi các bạn đã đọc được node rồi, thì không có cớ gì lại không sửa được nó cả 😀 những việc bạn cần làm là tìm node cần sửa, và “mổ xẻ” nó thôi… Rất đơn giản đúng không nào?

4. Xoá node trong DSLK

Với việc xoá node trong DSLK, hình sau sẽ mô tả đầy đủ:

delete-linked-list

Nhìn sơ qua, có vẻ nó khá là rắc rối nhỉ? Cứ tưởng tượng nếu thêm node như thế nào, thì xoá node chỉ là ngược lại 😀

void delHead(List& list)
{
  /* Ta không thể trực tiếp delete list.ptrHead
     Làm vậy thì những node sau sẽ trở thành giá trị rác
     Do chưa được giải phóng khỏi bộ nhớ
     Cho nên ta phải gán ptrHead cho node kế tiếp */
  Node* delNode = list.ptrHead;
  list.ptrHead = delNode->ptrNext;
  delete delNode;
}

void delTail(List& list)
{
  Node* delNode = list.ptrTail;
  // Lấy node phía trước node cần xoá để gán cho ptrTail
  list.ptrTail = getPrev(delNode);
  delete delNode;
}

void delNode(List& list, int index)
{
  int position = 0;
  // Sử dụng hàm có sẵn để lấy node cần xoá
  Node* delNode = getNode(list, index);
  if (delNode == list.ptrHead) delHead(list);
  else if (delNode == list.ptrTail) delTail(list);
  else
  {
    // Lấy node phía trước node cần xoá
    Node* prevNode = getPrev(list, delNode);
    // Và trỏ đến node phía sau node cần xoá
    prevNode->ptrNext = delNode->ptrNext;
    // Cuối cùng là xoá node
    delete delNode;
  }
}

// Xoá toàn bộ node trong list
void delList(List& list)
{
  /* Do mình đã nói khi delHead
     Ta không thể del từ Head -> Tail
     Vì làm vậy, những node phía sau sẽ thành giá trị rác
     Nên ta cần phải xoá từ Tail -> Head */
  Node* currDelNode = list.ptrTail;
  // Lấy node phía trước để làm node trung gian
  while (currDelNode != list.ptrHead)
  {
    Node* prevNode = getPrev(list, currDelNode);
    delete currDelNode;
    // Sau đó lấy node trung gian để xoá nút phía trước nữa
    currDelNode = prevNode;
  }
  // Lúc này, chỉ còn 1 node là ptrHead
  delete list.ptrHead;
}

Khi kết hợp code với hình ảnh minh hoạ mà mình đã cung cấp phía trên, chắc hẳn mọi người sẽ có cách nhìn dễ hiểu hơn về DSLK. Nếu có câu hỏi nào về DSLK xin hãy comment phía bên dưới để được giải đáp nhé 😀

Trên đây là bài viết về Danh sách liên kết trong C++. Cảm ơn mọi người đã theo dõi, hẹn gặp lại ở những bài viết 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