Linked List
What is a Linked List?
A linked list is a linear data structure where elements (called nodes) are stored in non-contiguous memory locations. Each node contains data and a pointer to the next node. Unlike arrays, linked lists don't require contiguous memory and can grow/shrink dynamically.
Think of a linked list like a treasure hunt — each clue (node) tells you where the next clue is. You can't jump directly to clue #5; you must follow the chain from the beginning.
Array vs Linked List
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous | Non-contiguous (scattered) |
| Access by index | O(1) — direct | O(n) — must traverse |
| Insert at beginning | O(n) — shift elements | O(1) |
| Insert at end | O(1) if space | O(n) or O(1) with tail pointer |
| Delete | O(n) — shift elements | O(1) with pointer to node |
| Memory overhead | None | Extra pointer per node |
| Cache performance | Excellent | Poor (scattered memory) |
Singly Linked List — Full Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
class LinkedList {
Node* head;
public:
LinkedList() : head(nullptr) {}
void insertFront(int data) {
Node* node = new Node(data);
node->next = head;
head = node;
}
void insertEnd(int data) {
Node* node = new Node(data);
if (!head) { head = node; return; }
Node* curr = head;
while (curr->next) curr = curr->next;
curr->next = node;
}
void deleteVal(int data) {
if (!head) return;
if (head->data == data) { Node* t = head; head = head->next; delete t; return; }
Node* curr = head;
while (curr->next && curr->next->data != data) curr = curr->next;
if (curr->next) { Node* t = curr->next; curr->next = t->next; delete t; }
}
bool search(int data) {
Node* curr = head;
while (curr) { if (curr->data == data) return true; curr = curr->next; }
return false;
}
void reverse() {
Node *prev = nullptr, *curr = head, *next = nullptr;
while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; }
head = prev;
}
void print() {
Node* curr = head;
while (curr) { cout << curr->data << " -> "; curr = curr->next; }
cout << "NULL" << endl;
}
};
int main() {
LinkedList ll;
ll.insertEnd(1); ll.insertEnd(2); ll.insertEnd(3);
ll.insertFront(0);
ll.print(); // 0 -> 1 -> 2 -> 3 -> NULL
ll.deleteVal(2);
ll.print(); // 0 -> 1 -> 3 -> NULL
ll.reverse();
ll.print(); // 3 -> 1 -> 0 -> NULL
cout << boolalpha << ll.search(1) << endl; // true
return 0;
}public class LinkedList {
static class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
Node head;
void insertFront(int data) {
Node node = new Node(data);
node.next = head;
head = node;
}
void insertEnd(int data) {
Node node = new Node(data);
if (head == null) { head = node; return; }
Node curr = head;
while (curr.next != null) curr = curr.next;
curr.next = node;
}
void delete(int data) {
if (head == null) return;
if (head.data == data) { head = head.next; return; }
Node curr = head;
while (curr.next != null && curr.next.data != data) curr = curr.next;
if (curr.next != null) curr.next = curr.next.next;
}
void reverse() {
Node prev = null, curr = head, next = null;
while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; }
head = prev;
}
void print() {
Node curr = head;
while (curr != null) { System.out.print(curr.data + " -> "); curr = curr.next; }
System.out.println("NULL");
}
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.insertEnd(1); ll.insertEnd(2); ll.insertEnd(3);
ll.insertFront(0);
ll.print(); // 0 -> 1 -> 2 -> 3 -> NULL
ll.delete(2);
ll.print(); // 0 -> 1 -> 3 -> NULL
ll.reverse();
ll.print(); // 3 -> 1 -> 0 -> NULL
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_front(self, data):
node = Node(data)
node.next = self.head
self.head = node
def insert_end(self, data):
node = Node(data)
if not self.head:
self.head = node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
def delete(self, data):
if not self.head: return
if self.head.data == data:
self.head = self.head.next
return
curr = self.head
while curr.next and curr.next.data != data:
curr = curr.next
if curr.next:
curr.next = curr.next.next
def reverse(self):
prev, curr = None, self.head
while curr:
curr.next, prev, curr = prev, curr, curr.next
self.head = prev
def print_list(self):
curr = self.head
result = []
while curr:
result.append(str(curr.data))
curr = curr.next
print(" -> ".join(result) + " -> NULL")
ll = LinkedList()
ll.insert_end(1); ll.insert_end(2); ll.insert_end(3)
ll.insert_front(0)
ll.print_list() # 0 -> 1 -> 2 -> 3 -> NULL
ll.delete(2)
ll.print_list() # 0 -> 1 -> 3 -> NULL
ll.reverse()
ll.print_list() # 3 -> 1 -> 0 -> NULLclass Node {
constructor(data) { this.data = data; this.next = null; }
}
class LinkedList {
constructor() { this.head = null; }
insertFront(data) {
const node = new Node(data);
node.next = this.head;
this.head = node;
}
insertEnd(data) {
const node = new Node(data);
if (!this.head) { this.head = node; return; }
let curr = this.head;
while (curr.next) curr = curr.next;
curr.next = node;
}
delete(data) {
if (!this.head) return;
if (this.head.data === data) { this.head = this.head.next; return; }
let curr = this.head;
while (curr.next && curr.next.data !== data) curr = curr.next;
if (curr.next) curr.next = curr.next.next;
}
reverse() {
let prev = null, curr = this.head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
this.head = prev;
}
print() {
const parts = [];
let curr = this.head;
while (curr) { parts.push(curr.data); curr = curr.next; }
console.log(parts.join(" -> ") + " -> NULL");
}
}
const ll = new LinkedList();
ll.insertEnd(1); ll.insertEnd(2); ll.insertEnd(3);
ll.insertFront(0);
ll.print(); // 0 -> 1 -> 2 -> 3 -> NULL
ll.delete(2);
ll.print(); // 0 -> 1 -> 3 -> NULL
ll.reverse();
ll.print(); // 3 -> 1 -> 0 -> NULL