Danh sách liên kết là một cấu trúc dữ liệu tuyến tính có nhiều nút được kết nối với nhau. Mỗi nút bao gồm hai trường - Trường dữ liệu và địa chỉ của nút tiếp theo.
Giả sử chúng ta có một danh sách được liên kết đơn lẻ và chúng ta cần xóa nút đầu tiên khỏi danh sách được liên kết này. Ví dụ:
Đầu vào 1 - 4 → 3 → 2 → 1
Đầu ra - 3 → 2 → 1 →
Giải thích - ‘4’ là nút đầu tiên trong danh sách được liên kết đơn đã cho. Sau khi xóa nút đầu tiên, danh sách liên kết sẽ là 3 → 2 → 1.
Đầu vào 2 - 1 → 2 → 3 →
Đầu ra - 2 → 3 →
Giải thích - Sau khi xóa nút đầu tiên ‘1’, danh sách liên kết sẽ là 2 → 3.
Phương pháp tiếp cận để giải quyết vấn đề này
Ban đầu, chúng tôi có một danh sách liên kết bao gồm các nút. Mỗi nút chứa dữ liệu và địa chỉ đến nút tiếp theo. Sau khi chèn dữ liệu vào danh sách liên kết, chúng ta sẽ tạo một hàm để xóa nút đầu tiên.
Như vậy, chúng ta sẽ tạo một con trỏ tạm thời mà ban đầu trỏ đến phần đầu và di chuyển phần đầu đến nút tiếp theo. Bây giờ, hãy xóa nút tạm thời và trả lại danh sách được liên kết.
-
Một hàm deleteAthead (nút * &head) đưa con trỏ đến phần đầu và xóa nút đầu tiên của danh sách được liên kết.
-
Tạo một con trỏ tạm thời trỏ đến phần đầu.
-
Đầu di chuyển đến nút tiếp theo.
-
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;
int main(){
class node{
public:
int data;
node*next;
node(int d){
data=d;
node*next=NULL;
}
};
void insertAtFirstNode(node*&head, int data){
node*n= new node(data);
n->next= head;
head=n;
}
void print(node*head){
while(head!=NULL){
cout<<head->data<<"->";
head=head->next;
}
cout<<endl;
}
void deleteAtFirst(node*&head){
if(head==NULL){
return;
}
node*temp=head;
head= head->next;
delete temp;
return;
}
int main(){
node*head= NULL;
insertAtFirstNode(head,1);
insertAtFirstNode(head,2);
insertAtFirstNode(head,3);
insertAtFirstNode(head,4);
deleteAtFirst(head);
print(head);
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
3 → 2 → 1 →
Vì danh sách liên kết đơn đã cho là 4 → 3 → 2 → 1 →, sau khi xóa nút đầu tiên là 4, danh sách liên kết sẽ trở thành, 3 → 2 → 1 →