Danh sách được liên kết là một Cấu trúc dữ liệu tuyến tính có chứa các nút và mỗi nút có hai trường; một là giá trị hoặc dữ liệu sẽ được chèn vào và trường kia lưu trữ địa chỉ của nút tiếp theo.
Nhiệm vụ của chúng ta ở đây là xóa một nút khỏi phần cuối của Danh sách được liên kết. Nút cuối cùng được gọi là nút đuôi. Nếu không có nút nào trong Danh sách được Liên kết, hãy trả về NULL.
Ví dụ -
Đầu vào 1 - 1 → 2 → 3 → 4 → 5
Đầu ra - 1 → 2 → 3 → 4 →
Giải thích - Trong danh sách liên kết đơn đã cho, nút từ cuối là '5'. Sau khi xóa nút cuối cùng, đầu ra sẽ là, 1 → 2 → 3 → 4 →.
Đầu vào 2 - 5 → 8 → 3
Đầu ra - 5 → 8 →
Giải thích - Trong danh sách liên kết đơn đã cho, nút từ cuối là '3'. Sau khi xóa nút ở cuối, đầu ra sẽ là, 5 → 8 →.
Phương pháp tiếp cận để giải quyết vấn đề này
Cách tiếp cận đơn giản để giải quyết vấn đề cụ thể này là tạo một nút trước đó để sau này lưu trữ giá trị của nút hiện tại khi con trỏ hiện tại sẽ trỏ đến nút cuối cùng của danh sách được liên kết.
Lặp lại trên tất cả các nút của danh sách liên kết nếu nút hiện tại trỏ đến nút cuối cùng. Và cuối cùng, quay lại từ danh sách được liên kết.
-
Khởi tạo danh sách được liên kết bằng cách chèn các nút vào đó.
-
Hàm insertAtFirst (nút * &head, int data) sẽ chèn tất cả các nút trong danh sách được liên kết.
-
Một hàm deleteAtTail (nút * head) nhận một con trỏ hiện đang trỏ đến phần đầu.
-
Tạo một con trỏ Node trước đó và khởi tạo nó dưới dạng NULL.
-
Tạo một con trỏ Node tạm thời hiện đang trỏ đến phần đầu của con trỏ.
-
Di chuyển con trỏ tạm thời cho đến khi nó không đến cuối danh sách được liên kết.
-
Lưu trữ giá trị của con trỏ tạm thời trong con trỏ nút trước đó.
-
Xóa con trỏ tạm thời.
-
Trả lại danh sách được liên kết.
Ví dụ
#include<iostream>
using namespace std;
class node{
public:
int data;
node*next;
node(int d){
data=d;
node*next= NULL;
}
};
void insertAtFirst(node*&head, int data){
node*n= new node(data);
n->next= head;
head=n;
}
void printNode(node*head){
while(head!=NULL){
cout<<head->data<<"->";
head=head->next;
}
cout<<endl;
}
void deleteatTail(node*head){
node*prev= NULL;
node*temp= head;
while(temp->next!=NULL){
prev= temp;
temp=temp->next;
}
delete temp;
prev->next= NULL;
return;
}
int main(){
node*head= NULL;
insertAtFirst(head,5);
insertAtFirst(head,4);
insertAtFirst(head,3);
insertAtFirst(head,2);
insertAtFirst(head,1);
deleteatTail(head);
printNode(head);
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
1→2→3→4→
Trong danh sách liên kết đơn đầu vào đã cho, 1 → 2 → 3 → 4 → 5, nút cuối cùng của danh sách liên kết là ‘5’. Do đó, sau khi xóa nút cuối cùng, danh sách được liên kết sẽ trở thành 1 → 2 → 3 → 4 →.