รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นที่มีโหนดและแต่ละโหนดมีสองฟิลด์ หนึ่งคือค่าหรือข้อมูลที่จะแทรกและฟิลด์อื่นเก็บที่อยู่ของโหนดถัดไป
งานของเราคือการลบโหนดออกจากจุดสิ้นสุดของรายการที่เชื่อมโยง โหนดสุดท้ายเรียกว่าโหนดท้าย หากไม่มีโหนดในรายการที่เชื่อมโยง ให้คืนค่า NULL
ตัวอย่างเช่น −
อินพุต 1 − 1 → 2 → 3 → 4 → 5
ผลผลิต − 1 → 2 → 3 → 4 →
คำอธิบาย - ในรายการที่เชื่อมโยงโดยลำพังที่กำหนด โหนดจากจุดสิ้นสุดคือ '5' หลังจากลบโหนดสุดท้ายแล้ว เอาต์พุตจะเป็น 1 → 2 → 3 → 4 →
อินพุต 2 − 5 → 8 →3
ผลผลิต − 5 → 8 →
คำอธิบาย - ในรายการที่เชื่อมโยงโดยลำพังที่กำหนด โหนดจากจุดสิ้นสุดคือ '3' หลังจากลบโหนดออกจากจุดสิ้นสุด ผลลัพธ์จะเป็น 5 →8 →.
แนวทางการแก้ปัญหานี้
วิธีง่ายๆ ในการแก้ปัญหานี้คือการสร้างโหนดก่อนหน้าที่เก็บค่าของโหนดปัจจุบันในภายหลังเมื่อตัวชี้ปัจจุบันจะชี้ไปที่โหนดสุดท้ายของรายการที่เชื่อมโยง
วนซ้ำทุกโหนดของรายการที่เชื่อมโยงหากโหนดปัจจุบันชี้ไปที่โหนดสุดท้าย และสุดท้าย กลับจากรายการที่เชื่อมโยง
-
เริ่มต้นรายการที่เชื่อมโยงโดยการแทรกโหนดเข้าไป
-
ฟังก์ชัน insertAtFirst(node*&head, int data) จะแทรกโหนดทั้งหมดในรายการที่เชื่อมโยง
-
ฟังก์ชัน deleteAtTail(node*head) ใช้ตัวชี้ที่กำลังชี้ไปที่ส่วนหัว
-
สร้างตัวชี้โหนดก่อนหน้าและเริ่มต้นเป็น NULL
-
สร้างตัวชี้โหนดชั่วคราวซึ่งกำลังชี้ไปที่ส่วนหัวของตัวชี้
-
เลื่อนไปตามตัวชี้ชั่วคราวจนกว่าจะไปไม่สุดของรายการที่เชื่อมโยง
-
เก็บค่าของตัวชี้ชั่วคราวในพอยน์เตอร์ของโหนดก่อนหน้า
-
ลบตัวชี้ชั่วคราว
-
กลับรายการเชื่อมโยง
ตัวอย่าง
#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);
} ผลลัพธ์
การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
1→2→3→4→
ในรายการเชื่อมโยงเดี่ยวอินพุตที่กำหนด 1 → 2 → 3 → 4 → 5 โหนดสุดท้ายของรายการที่เชื่อมโยงคือ '5' ดังนั้น หลังจากลบโหนดสุดท้าย รายการที่เชื่อมโยงจะกลายเป็น 1 → 2 → 3 → 4 →
