Home > Giải thuật > Danh sách liên kết đơn > Xóa Node trong danh sách liên kết đơn

Xóa Node trong 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 cách xóa Node trong danh sách liên kết đơn.

Chúng ta sẽ cùng nhau tìm hiểu 3 trường hợp khi xóa một Node khỏi danh sách liên kết đơn:

  • Xóa Node ở đầu danh sách liên kết đơn.
  • Xóa Node ở cuối danh sách liên kết đơn.
  • Xóa Node ở giữa danh sách liên kết đơn.

1. Xóa Node ở đầu danh sách liên kết đơn

Trong trường hợp chúng ta muốn xóa một Node, mà Node đó lại nằm ở đầu danh sách. Đây là một trường hợp đặc biệt, các bạn hãy xem các bước thực hiện sau đây:

Giả sử chúng ta có một Node pDel là Node cần xóa và một danh sách liên kết đơn.

xoa node 1 PNG

Bước 1: Vì Node cần xóa ở đầu danh sách, tức là ngay node pHead. Vì vậy chúng ta cần di chuyển pHead từ pDel sang Node kế tiếp: list.pHead = list.pHead -> pNext

xoa node 2 PNG

Bước 2: Sau khi di chuyển pHead sang Node kế tiếp, chúng ta sẽ ngắt mối liên kết giữa pDel với Node phía sau nó: pDel -> pNext = Null.

xoa node 3 PNG

Bước 3: Bây giờ pDel không còn liên kết với bất kì Node nào trong danh sách nữa, chúng ta đã có thể xóa Node này. delete pDel

xoa node 4 PNG

// Nếu pDel == list.pHead, tức là số cần xóa ở đầu danh sách
      if(pDel == list.pHead){
        list.pHead = list.pHead -> pNext;
        pDel -> pNext = NULL;
        delete pDel;
        pDel = NULL;
      }

2. Xóa Node ở cuối danh sách liên kết đơn.

Trong trường hợp Node muốn xóa lại nằm ở cuối danh sách, tương tự như việc xóa ở đầu danh sách. Ta chỉ cần di chuyển pTail về Node trước đó (pPre) và thay đổi pNext = NULL.

xoa node 7 PNG

Sau khi di chuyển pTail về Node trước đó và ngắt mối liên kết giữa pPre với pDel, ta thực hiện xóa Node pDel: delete pDel

//Nếu pDel == list.pTail, tức là số cần xóa ở cuối danh sách
      if(pDel -> pNext == NULL){
        list.pTail = pPre;
        pPre -> pNext = NULL;
        delete pDel;
        pDel = NULL;
      }

3. Xóa Node ở giữa danh sách liên kết đơn.

Và trường hợp cuối cùng, khi xóa Node mà Node đó không nằm đầu cũng không nằm cuối danh sách, ta thực hiện các bước như sau:

Khi ta muốn xóa một Node ở giữa danh sách, đầu tiên ta cần xác định Node cần xóa pDel và Node đứng trước nó pPre.

xoa node 8 PNG

Sau khi xác định được pDel và pPre, ta thay đổi mối liên kết giữa pPre đến pTail (pPre -> pNext = pDel -> pNext) và cho pDel -> pNext == NULL. Các bạn có thể xem hướng mũi tên để biết được các bước thực hiện của nó.

xoa node 9 PNG

Ta có thể xóa Node pDel khi đã ngắt mối liên kết giữa nó với các Node khác: delete pDel

// và trường hợp cuối cùng số muốn xóa nằm ở giữa danh sách
      else{
        pPre -> pNext = pDel -> pNext;
        pDel -> pNext = NULL;
        delete pDel;
        pDel = NULL; 
      }

4. Ví dụ xóa Node trong danh sách liên kết đơn

Chúng ta sẽ sử dụng dữ liệu ở ví dụ trước để thực hiện xóa cho ví dụ này, vừa có thể ôn lại kiến thức cũ vừa áp dụng kiến thức mới.

#include <iostream>
using namespace std;
/* 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
}
 
/* Đếm số phần tử trong danh sách */
 int SizeOfList(SingleList list)
{
    Node *pTmp=list.pHead;
    int nSize=0;
    while(pTmp!=NULL)
    {
        pTmp=pTmp->pNext;
        nSize++;
    }
    return nSize;
}
 
/* tạo Node trong danh sách liên kết đơn */
Node *CreateNode(int d)
{
    Node *pNode=new Node; //sử dụng pNode để tạo một Node mới
    if(pNode!=NULL) // Nếu pNode != Null, tức là pNode có giá trị thì
    {
       pNode->data=d; // gán giá trị data cho d
       pNode->pNext=NULL;// và cho con trỏ pNext trỏ tới giá trị Null
    }
    else // Nếu pNode == Null, tức là pNode không có giá trị thì xuất thông tin
    {
      cout<<"Error allocated memory";
    }
    return pNode;//trả về pNode
}
 
/* chèn Node đầu danh sách */
void InsertFirst(SingleList &list,int d)
{
  Node *pNode=CreateNode(d);
  if(list.pHead==NULL)
  {
    list.pHead=list.pTail=pNode;
  }
  else
  {
    pNode->pNext=list.pHead;
    list.pHead=pNode;
  }
}
 
/* chèn node vào cuối danh sách */
void InsertLast(SingleList &list,int d)
{ 
  Node *pNode=CreateNode(d);
  if(list.pTail==NULL)
  {
    list.pHead=list.pTail=pNode;
  }
  else
  {
    list.pTail->pNext=pNode;
    list.pTail=pNode;
  }
}
 
/* chèn node vào giữa danh sách */
void InsertMid(SingleList &list, int pos, int d){
  // Nếu pos < 0 hoặc pos lớn hơn kích thước của danh sách thì reuturn
  if(pos < 0 || pos >= SizeOfList(list)){
    cout<<"Không thể chèn Node!!!";
    return;
  }
  // Nếu pos == 0 thì gọi hàm InsertFirst
  if(pos == 0){
    InsertFirst(list, d);
  }
  //Nếu pos == SizeOfList - 1 thì gọi hàm InsertLast
  else if(pos == SizeOfList(list)-1){
    InsertLast(list, d);
  }
  //Ngược lại thì thay đổi mối liên kết giữa các phần tử, cụ thể:
  else{
    Node *pNode = CreateNode(d);
    Node *pIns = list.pHead;
    Node *pPre = NULL;
    int i = 0;
    //thực hiện vòng lặp tìm pPre và pIns
    while(pIns != NULL){
      if(i == pos)
      break;
      pPre = pIns;
      pIns = pIns ->pNext;
      i++;
    }
    //sau khi tìm được thì thay đổi con trỏ pNext
    pPre ->pNext=pNode;
    pNode->pNext=pIns;
  }
}
 
/* xóa node khỏi danh sách liên kết */
void RemoveNode(SingleList &list, int d){
  Node *pDel = list.pHead; // tạo một node pDel để xóa
  //Nếu pDel == Null thì danh sách rỗng
  if(pDel == NULL){
    cout<<"Danh sách rỗng!!";
  }
  //ngược lại thì xét điều kiện
  else{
    Node *pPre = NULL;
    //dùng vòng lặp while để tìm ra pDel và pPre (vị trí đứng trước pDel)
    while(pDel != NULL){
      if(pDel -> data == d){
        break;
      }
      pPre = pDel;
      pDel = pDel -> pNext;
    }
    //Nếu pDel == null tức là không tìm thấy số cần xóa
    if(pDel == NULL){
      cout<<"Không tìm thấy số cần xóa";
    }
    // Ngược lại tiếp tục xét điều kiện
    else{
      // Nếu pDel == list.pHead, tức là số cần xóa ở đầu danh sách
      if(pDel == list.pHead){
        list.pHead = list.pHead -> pNext;
        pDel -> pNext = NULL;
        delete pDel;
        pDel = NULL;
      }
      //Nếu pDel == list.pTail, tức là số cần xóa ở cuối danh sách
      else if(pDel -> pNext == NULL){
        list.pTail = pPre;
        pPre -> pNext = NULL;
        delete pDel;
        pDel = NULL;
      }
      // và trường hợp cuối cùng số muốn xóa nằm ở giữa danh sách
      else{
        pPre -> pNext = pDel -> pNext;
        pDel -> pNext = NULL;
        delete pDel;
        pDel = NULL; 
      }
    }
  }
}

/* hàm xuất dữ liệu */
void PrintList(SingleList list)
{
  Node *pTmp=list.pHead;
  if(pTmp==NULL)
  {
    cout<<"The list is empty!";
    return;
  }
  while(pTmp!=NULL)
  {
    cout<<pTmp->data<<" ";
  pTmp=pTmp->pNext;
  }
}
 
int main() {
  SingleList list;
  Initialize(list);
 
//Thêm node đầu danh sách
  InsertFirst(list, 5);
  InsertFirst(list, 7);
  InsertFirst(list, 3);
  cout<<"Các Node trong danh sách sau khi InsertFirst là: ";
  PrintList(list);
 
//Thêm node cuối danh sách
  InsertLast(list, 4);
  InsertLast(list, 2);
  InsertLast(list, 6);
  cout<<"\nCác Node trong danh sách sau khi InsertLast là: ";
  PrintList(list);
 
//Thêm node giữa danh sách
  InsertMid(list, 4, 11);
  InsertMid(list, 2, 12);
  InsertMid(list, 3, 13);
  cout<<"\nCác Node trong danh sách sau khi InsertMid là: ";
  PrintList(list);

//Xóa node khỏi danh sách
  RemoveNode(list, 3);
  RemoveNode(list, 11);
  RemoveNode(list, 6);
  cout<<"\nCác Node trong danh sách sau khi xóa là: ";
  PrintList(list);
  
  cout<<"\n-------------------------------------\n";
  cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả:

xoa node 5 PNG

Như vậy là chúng ta đã thực hiện xong các trường hợp xóa Node trong danh sách liên kết đơn. Ở bài tiếp theo chúng ta sẽ thực hiện tìm kiếm và sắp xếp các phần tử trong DSLK, các bạn hãy chú ý theo dõi nhé !!!

BÀI VIẾT

notice png LIST home png HOME hot gif BÁO
LỖI
top png TOP