Linked List
Last updated
A linked list stores a sequence as a chain of nodes, where each node holds a value and a pointer to the next node. Unlike an array, the nodes aren't contiguous in memory - you follow the next pointers to walk the list. Press play above to watch nodes get linked at the head and tail, a value get searched for by walking the chain, and a node get removed by rewiring a pointer.
Inserting or deleting at the head is O(1) because you just repoint the head. Reaching a position in the middle or the tail is O(n) because you must walk there first. That trade-off - cheap ends, no random access - is what distinguishes a linked list from an array.
Time complexity
| Operation | Complexity | Notes |
|---|---|---|
| Insert at head | O(1) | Repoint head |
| Insert at tail | O(n) | Walk to the end first (O(1) with a tail pointer) |
| Search | O(n) | Follow next pointers |
| Delete head | O(1) | Repoint head past it |
| Access by index | O(n) | No random access |
Linked list vs array
| Aspect | Linked list | Array |
|---|---|---|
| Memory | Scattered nodes + pointers | Contiguous block |
| Random access | O(n) | O(1) |
| Insert/delete at front | O(1) | O(n) (shift) |
| Cache friendliness | Poor | Good |
Worked example
Building the list [10, 20], prepending 5, then deleting 20:
| Step | Structure | Action |
|---|---|---|
| Start | head -> null | Empty list |
| Insert head 10 | head -> 10 -> null | Repoint head to a new node whose next is the old head (null) |
| Insert tail 20 | head -> 10 -> 20 -> null | Walk to node 10, set its next to a new node 20 |
| Insert head 5 | head -> 5 -> 10 -> 20 -> null | New node 5 points to old head 10; head now points to 5 |
| Delete 20 | head -> 5 -> 10 -> null | Walk to 10, set its next from 20 to null; node 20 is unlinked |
When to use a linked list
| Use it when | Avoid it when |
|---|---|
| You insert or delete at the ends (or at a held node) far more than you index | You need fast random access by position (O(1) indexing) |
| The size changes a lot and you want no resize/copy cost | You iterate tight loops where cache locality dominates performance |
| You're building a queue, stack, or adjacency list | Memory is tight - each node pays an extra pointer per element |
| You need stable references to nodes that survive insertions elsewhere | You mostly read and rarely mutate, so an array is simpler and faster |
Linked List code
A clean, runnable Linked List implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Linked List code in Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Linked List code in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Linked List code in Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Linked List code in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Linked List code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}Linked List FAQ
What is the difference between a linked list and an array?
An array stores elements in one contiguous block, giving
O(1) random access but O(n) inserts/deletes that shift elements. A linked list stores nodes anywhere in memory connected by pointers, giving O(1) inserts/deletes at a known position but O(n) access since you must walk the chain.When should I use a linked list?
Linked lists shine when you frequently insert or remove at the ends (or at a node you already hold a reference to) and rarely need random access - for example, queues, stacks, adjacency lists, and LRU caches. If you need fast indexed access, an array or dynamic array is usually better.
What is the time complexity of a linked list?
Insert or delete at the head is
O(1). Searching, or reaching the tail without a tail pointer, is O(n) because you follow next pointers one by one. There is no O(1) random access - indexing into a linked list is O(n).What is the difference between a singly and doubly linked list?
A singly linked list stores only a
next pointer per node, so you can walk in one direction and deleting a node requires a reference to its predecessor. A doubly linked list adds a prev pointer, enabling backward traversal and O(1) deletion of a held node, at the cost of an extra pointer per node and more bookkeeping on every insert and delete.Why is inserting at the tail O(n) if inserting at the head is O(1)?
Inserting at the head only rewires the
head pointer, which is constant work. Reaching the tail means following next pointers from the head all the way to the end, which is O(n). Keeping a separate tail pointer makes tail insertion O(1) too, which is why real-world lists often track both ends.Do linked lists have O(1) insertion everywhere?
No - that's a common misconception. The insertion itself is
O(1) only once you already hold a pointer to the node you're inserting after. Finding that position by value or index still costs O(n) because you must walk the chain to get there.Related resources
More visualizations
