Singly Linked List
What is a Singly Linked List
A singly linked list stores its elements as a chain of nodes, where each node holds a value and a single pointer to the next node in the sequence, ending with a final node whose next pointer is null.
Example: 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;
}Login to try C/C++/Java code in the editor
Basic Operations
Unlike an array, a linked list doesn't need contiguous memory or a fixed size, which makes operations like inserting or removing a node at the head extremely cheap, since you're just updating a pointer, not shifting elements.
Example: 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;
}Login to try C/C++/Java code in the editor
Traversal
Traversing a singly linked list means starting at the head and following each node's next pointer until you reach the end, which is the only way to reach a given node since there's no direct indexing like an array offers.
Example: 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;
}Login to try C/C++/Java code in the editor
Advantages
Because nodes are allocated individually as needed, a linked list can grow or shrink dynamically without ever needing to be resized or copied, and inserting at a known position is O(1) once you're already there.
Example: 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;
}Login to try C/C++/Java code in the editor
Limitations
The trade-off for that flexibility is that reaching the k-th node requires walking from the head one node at a time, an O(n) operation, and each node uses extra memory to store its pointer alongside its actual data.
Example: 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;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: