Introduction to Singly Linked List

Singly Linked List ek linear data structure hai jo nodes ka sequence hota hai. Har node do cheezein store karta hai:

1. Data: Jo actual value hoti hai
2. Next Pointer: Jo agle node ka address hold karta hai

Isse hum dynamic memory me data ko store aur manage kar sakte hai bina fixed size ke, unlike arrays.

Why Linked List instead of Array?

1. Arrays ka size fix hota hai, par linked list dynamically grow/shrink kar sakti hai.
2. Insertion/Deletion arrays me costly hota hai, lekin linked list me ye efficiently hota hai.
3. Lekin linked list me random access (e.g. index se direct access) possible nahi hota.

Node Structure

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};

Explanation:

int data;

• Yeh ek integer variable hai.
• Isme hum wo value store karte hain jo hum linked list me rakhna chahte hain.
• Example: agar aap 10 insert karte ho, toh data = 10 hoga.

Node* next;

• Yeh ek pointer hai jo next node ke address ko store karta hai.
• Jab aap multiple nodes banate ho, toh ek node ke next me doosre node ka address hota hai.
• Agar node last hai, toh next = NULL.

void insertAtEnd(Node*& head, int val) {
  Node* newNode = new Node(val);
   
  if (head == NULL) {
    head = newNode;
    return;
  }

  Node* temp = head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
}

Explanation:

void insertAtEnd(Node*& head, int val)

• (Node*& head, int val):
• Node*& head: Yeh reference to pointer hai. Yaani function ke andar agar head ko modify karte ho, toh original list bhi change hogi.
• int val: Insert karne wali value.

Node* newNode = new Node(val);

• Hum heap memory mein ek new node create kar rahe hain.
• new Node(val) ka matlab hai ek constructor call jisme val diya gaya hai.
• newNode ke andar ab:
• data = val
• next = NULL (constructor ke through

Example:

Agar val = 10, toh newNode ka structure ho jaayega:

| data: 10 | next: NULL |

if (head == NULL) {
  head = newNode;
  return;
}

• Agar list empty hai, yaani head == NULL, toh pehla node insert ho raha hai.
• Toh head pointer ko direct newNode pe point kar do.
• Aur return kar jao. (Kyunki list mein ek hi node hai abhi)

head → | data: 10 | next: NULL |

Node* temp = head;
while (temp->next != NULL) {
  temp = temp->next;
}

• Hum ek temp pointer banate hain, jo list ke start se traverse karega.
• Jab tak temp->next != NULL, tab tak temp ko aage badhate jao.
• Jab loop rukta hai, tab temp last node pe hota hai.

Example:

List = 10 → 20 → 30

temp pehle 10 pe, fir 20, fir 30 pe jaayega, jahan temp->next == NULL.

temp->next = newNode;

• Ab jo last node hai (temp), uske next pointer ko newNode pe point karwa do.
• Isse newNode list ke end me attach ho jaata hai.

Final Structure:

Agar pehle list thi:

10 → 20 → 30 → NULL

Aur humne val = 40 pass kiya, toh ab ban jaayegi:

10 → 20 → 30 → 40 → NULL

Traversal (Print Linked List)

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

Explanation:

Node* temp = head;

• Hum ek temporary pointer temp banate hain jo list ko traverse karega.
• Agar directly head ko use karte, toh original pointer change ho sakta tha.
• Isliye hum temp me head ki copy lete hain.

while (temp != NULL)

• Jab tak temp NULL nahi hota (yaani jab tak list khatam nahi hoti), loop chalega.
• NULL ka matlab hota hai list ka end.

cout << temp->data << " -> ";

• Har node ka data print karo, uske baad ek arrow (->) lagao.
• Example: agar node ke andar 10 hai, toh print karega:

10 ->

temp = temp->next;

• Ab temp ko agle node pe le jao.
• Yaani next pointer follow karo:
• temp = temp->next;

cout << "NULL" << endl;

• Jab loop khatam ho jaaye (list end tak pahuch jaaye), tab NULL print karo.
• Isse reader ko samajh aata hai ki list yahin tak thi.

Input List:

Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);

Output

10 -> 20 -> 30 -> NULL

Deletion at Head

void deleteAtHead(Node*& head) {
    if (head == NULL) return;

    Node* toDelete = head;
    head = head->next;
    delete toDelete;
}

Explanation:

void deleteAtHead(Node*& head)

• Parameter: Node*& head
• Yeh reference to pointer hai.
• Yaani agar hum head ko change karte hain function ke andar, toh actual head pointer bhi update ho jaata hai.

if (head == NULL) return;

• Pehle check karte hain ki list empty toh nahi.
• Agar head NULL hai, toh koi node hai hi nahi delete karne ke liye, isliye function ko wahi return kar do.

Node* toDelete = head;

• Hum ek temporary pointer toDelete banate hain jo abhi ke head ko point karta hai.
• Isse hum baad me delete karenge.
• Is step ka matlab: "jis node ko delete karna hai, usko temporarily store kar lo."

head = head->next;

• Ab head pointer ko aage shift kar do.
• Yaani ab list ka new head, pehle wale node ka next node ho jaata hai.

Example:

Head Before Delete.

head → | 10 | → | 20 | → | 30 | → NULL

Head After Delete.

head → | 20 | → | 30 | → NULL

delete toDelete;

• Finally, jo purana head node tha (toDelete), usko memory se delete kar do.
• C++ me manually memory free karna padta hai (delete keyword se), warna memory leak ho sakta hai.

Full Example:

Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);

deleteAtHead(head);
printList(head);

Output:

20 -> 30 -> NULL

Full Code

#include <iostream>
using namespace std;


class Node {
public:
    int data;
    Node* next;


    Node(int val) {
        data = val;
        next = NULL;
    }
};

int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);

    cout << "Linked List: ";
    printList(head);

    deleteAtHead(head);
    cout << "After Deletion at Head: ";
    printList(head);

    return 0;
}

Output:

Linked List: 10 -> 20 -> 30 -> NULL

After Deletion at Head: 20 -> 30 -> NULL

Practice Questions

1. Insert at beginning of list
2. Delete node by value
3. Count nodes in a linked list

Conclusion

Singly Linked List DSA ka ek fundamental topic hai jo future me complex concepts like stacks, queues, linked list-based trees banane ke kaam aata hai. Ye Practice Questions ko khud try karo aur comment box mein apna solution share kro.