Linked Lists

Dynamic Chain of Nodes

💡 Linked list ek treasure hunt jaisi hai — har clue (node) tumhe agle clue ka address batata hai. Array ek seedhi si numbered street jaisa hai (fixed houses), linked list ek chain of clues hai jo runtime par kahi bhi grow ho sakti hai.

Array ki size fixed hoti hai (declare karte waqt decide karni padti hai). Linked list dynamically grow/shrink ho sakti hai — har element ("node") do cheezein rakhta hai: data, aur agle node ka pointer. Pehle node ka address ek "head" pointer mein store hota hai; last node ka next NULL hota hai (list ka end batata hai).

Insert/delete linked list mein O(1) ho sakta hai (agar position pata ho) — sirf pointers rewire karne padte hain, poore array ko shift nahi karna padta jaisa arrays mein hota hai. Lekin random access (jaise "10th element do") linked list mein O(n) hai — head se shuru karke sequentially chalna padta hai, array ki tarah seedha index[10] nahi kar sakte.

struct Node {
  int data;
  struct Node *next;
};

int main() {
  struct Node *head = malloc(sizeof(struct Node));
  head->data = 10;
  head->next = malloc(sizeof(struct Node));
  head->next->data = 20;
  head->next->next = NULL;   // list ka end

  struct Node *curr = head;
  while (curr != NULL) {
    printf("%d -> ", curr->data);
    curr = curr->next;
  }
  printf("NULL\n");  // 10 -> 20 -> NULL
  return 0;
}

🔗

Linked list ek treasure hunt jaisi hai — har clue (node) tumhe agle clue ka address batata hai. Array ek seedhi si numbered street jaisa hai (fixed houses), linked list ek chain of clues hai jo runtime par kahi bhi grow ho sakti hai.

1 / 6

⚡ Quick Recap

Node = data + next pointer
Dynamically grow hoti hai, array ki tarah fixed size nahi
Insert/delete fast (O(1)), random access slow (O(n))

Is page mein (2 subtopics)

Beginning mein insert karna O(1) hai — bas naya node banao, uska next purane head ko point karo, aur head ko naye node par update kar do. End mein insert karna O(n) hai (agar "tail" pointer track na karo) — poori list traverse karke last node dhundna padta hai.

struct Node* insertAtBeginning(struct Node *head, int value) {
  struct Node *newNode = malloc(sizeof(struct Node));
  newNode->data = value;
  newNode->next = head;   // naya node purane head ko point kare
  return newNode;          // naya node hi ab head hai
}

struct Node* insertAtEnd(struct Node *head, int value) {
  struct Node *newNode = malloc(sizeof(struct Node));
  newNode->data = value;
  newNode->next = NULL;

  if (head == NULL) return newNode;

  struct Node *curr = head;
  while (curr->next != NULL) curr = curr->next;  // end tak jao
  curr->next = newNode;
  return head;
}

💡Tip: Agar end mein bahut baar insert karna ho, ek alag "tail" pointer maintain karna (list ke saath) O(n) ko O(1) mein badal deta hai — traversal ki zaroorat hi nahi padti.

List ko free() karte waqt ek common mistake hai node ko free() karke uska next pointer use karne ki koshish karna — free() ke baad memory ka content undefined hai. Sahi tarika: next ko pehle save karo, phir current ko free() karo.

void freeList(struct Node *head) {
  struct Node *curr = head;
  while (curr != NULL) {
    struct Node *next = curr->next;  // pehle save karo
    free(curr);                       // ab free karo
    curr = next;                      // saved next se aage badho
  }
}

⚠️Common Mistake: free(curr); curr = curr->next; likhna GALAT hai — curr free() hone ke baad curr->next access karna use-after-free bug hai. Hamesha next ko free() se PEHLE save karo.

← Previous🪄 Macros Next →🎛️ Bit Manipulation

Code10x

Linked Lists

Inserting at the Beginning vs the End

Freeing a Linked List — Memory Leak Se Bachna