← Back to DSA Course | Chapter 4: Linked Lists | Lesson 1 of 8

Singly Linked List क्या है

एक singly linked list एक treasure hunt जैसी है जहां हर clue एक prize रखता है और बताता है अगला clue कहां ढूंढना है, और आप सिर्फ आगे जा सकते हैं।

In this page:

  1. What is a Singly Linked List
  2. Basic Operations
  3. Traversal
  4. Advantages
  5. Limitations
Syntax
markup 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

current = head
while current:
    process(current.data)
    current = current.next

What is a Singly Linked List

एक singly linked list अपने elements को nodes की एक chain के रूप में store करता है, जहां हर node एक value और sequence में अगले node का एक single pointer रखता है, आखिर में एक final node के साथ जिसका next pointer null है।

उदाहरण: What is a Singly Linked List

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{1, nullptr};
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};
    for (Node* cur = head; cur; cur = cur->next) cout << cur->data << " -> ";
    cout << "null" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        for (Node cur = head; cur != null; cur = cur.next) System.out.print(cur.data + " -> ");
        System.out.println("null");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
cur = head
while cur:
    print(cur.data, "-> ", end="")
    cur = cur.next
print("null")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
    struct Node *head = malloc(sizeof(struct Node));
    head->data = 1;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;
    for (struct Node *cur = head; cur; cur = cur->next) printf("%d -> ", cur->data);
    printf("null\n");
    return 0;
}

Basic Operations

एक array के विपरीत, एक linked list को contiguous memory या fixed size की ज़रूरत नहीं, जो head पर एक node insert या remove करने जैसे operations को बेहद सस्ता बनाता है, क्योंकि आप बस एक pointer update कर रहे हैं, elements shift नहीं कर रहे।

उदाहरण: Basic Operations

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{2, nullptr};
    Node* newHead = new Node{1, head};
    head = newHead;
    for (Node* cur = head; cur; cur = cur->next) cout << cur->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node head = new Node(2);
        Node newHead = new Node(1);
        newHead.next = head;
        head = newHead;
        for (Node cur = head; cur != null; cur = cur.next) System.out.print(cur.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(2)
new_head = Node(1)
new_head.next = head
head = new_head
cur = head
while cur:
    print(cur.data, end=" ")
    cur = cur.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
    struct Node *head = malloc(sizeof(struct Node));
    head->data = 2; head->next = NULL;
    struct Node *newHead = malloc(sizeof(struct Node));
    newHead->data = 1; newHead->next = head;
    head = newHead;
    for (struct Node *cur = head; cur; cur = cur->next) printf("%d ", cur->data);
    printf("\n");
    return 0;
}

Traversal

किसी singly linked list को traverse करने का मतलब है head पर शुरू करना और हर node के next pointer का पीछा करना जब तक आप आखिर तक न पहुंच जाएं, जो किसी दिए node तक पहुंचने का इकलौता तरीका है क्योंकि एक array की तरह कोई direct indexing नहीं।

उदाहरण: Traversal

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{10, new Node{20, new Node{30, nullptr}}};
    int count = 0;
    for (Node* cur = head; cur; cur = cur->next) { cout << cur->data << " "; count++; }
    cout << "\nNodes visited: " << count << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        int count = 0;
        for (Node cur = head; cur != null; cur = cur.next) { System.out.print(cur.data + " "); count++; }
        System.out.println("\nNodes visited: " + count);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
count = 0
cur = head
while cur:
    print(cur.data, end=" ")
    count += 1
    cur = cur.next
print("\nNodes visited:", count)
#include <stdio.h>
#include <stdlib.h>
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 = malloc(sizeof(struct Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;
    int count = 0;
    for (struct Node *cur = head; cur; cur = cur->next) { printf("%d ", cur->data); count++; }
    printf("\nNodes visited: %d\n", count);
    return 0;
}

Advantages

चूंकि nodes ज़रूरत पड़ने पर individually allocated होते हैं, एक linked list बिना कभी resize या copy होने की ज़रूरत के dynamically बढ़ या सिकुड़ सकती है, और एक known position पर insert करना O(1) है एक बार आप वहां पहले से हों।

उदाहरण: Advantages

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{1, nullptr};
    for (int i = 2; i <= 5; i++) {
        Node* n = new Node{i, nullptr};
        n->next = head; head = n;
    }
    for (Node* cur = head; cur; cur = cur->next) cout << cur->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node head = new Node(1);
        for (int i = 2; i <= 5; i++) {
            Node n = new Node(i);
            n.next = head; head = n;
        }
        for (Node cur = head; cur != null; cur = cur.next) System.out.print(cur.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
for i in range(2, 6):
    n = Node(i)
    n.next = head
    head = n
cur = head
while cur:
    print(cur.data, end=" ")
    cur = cur.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
    struct Node *head = malloc(sizeof(struct Node));
    head->data = 1; head->next = NULL;
    for (int i = 2; i <= 5; i++) {
        struct Node *n = malloc(sizeof(struct Node));
        n->data = i; n->next = head; head = n;
    }
    for (struct Node *cur = head; cur; cur = cur->next) printf("%d ", cur->data);
    printf("\n");
    return 0;
}

Limitations

उस flexibility का trade-off यह है कि k-th node तक पहुंचने के लिए head से एक समय में एक node चलना पड़ता है, एक O(n) operation, और हर node अपने actual data के साथ इसका pointer store करने के लिए extra memory उपयोग करता है।

उदाहरण: Limitations

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{1, new Node{2, new Node{3, new Node{4, nullptr}}}};
    int k = 2, steps = 0;
    Node* cur = head;
    while (steps < k) { cur = cur->next; steps++; }
    cout << "Node at index " << k << " = " << cur->data << ", took " << steps << " steps (O(n))" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4);
        int k = 2, steps = 0;
        Node cur = head;
        while (steps < k) { cur = cur.next; steps++; }
        System.out.println("Node at index " + k + " = " + cur.data + ", took " + steps + " steps (O(n))");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2); head.next.next = Node(3); head.next.next.next = Node(4)
k, steps, cur = 2, 0, head
while steps < k:
    cur = cur.next
    steps += 1
print(f"Node at index {k} = {cur.data}, took {steps} steps (O(n))")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
    struct Node *n4 = malloc(sizeof(struct Node)); n4->data = 4; n4->next = NULL;
    struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = n4;
    struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
    struct Node *head = malloc(sizeof(struct Node)); head->data = 1; head->next = n2;
    int k = 2, steps = 0;
    struct Node *cur = head;
    while (steps < k) { cur = cur->next; steps++; }
    printf("Node at index %d = %d, took %d steps (O(n))\n", k, cur->data, steps);
    return 0;
}
Related Topics

Doubly Linked List क्या है · Circular Linked List क्या है · Linked List को Reverse करना · Linked List का Middle ढूँढना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. पुरानी value save किए बिना head (या एक next) बदलकर list का बाकी हिस्सा खो देना।
  2. head के nullptr होने पर head->next dereference करना, जो एक empty list पर crash करता है।
  3. new से nodes allocate करना और कभी free न करना, एक memory leak का कारण बनते हुए।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Rabin-Karp Algorithm Next Lesson → Doubly Linked List

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.