A linked list stores values in nodes. Each node holds a value and references to neighbors. You access the structure via a head pointer; a tail pointer (optional) makes appends O(1).
next. O(1) at the front; removing in the middle needs the predecessor.prev and next. O(1) at both ends and O(1) delete if you already have the node.tail; DLL & circular differences are noted inline.| Operation | Array list | Singly LL (no tail) | Singly LL (with tail) | Doubly LL (head+tail) | Notes |
|---|---|---|---|---|---|
push_front(x) |
O(n) | O(1) | O(1) | O(1) | Array shifts; lists just relink |
push_back(x) |
Amortized O(1) | O(n) | O(1) | O(1) | Tail pointer gives O(1) appends |
insert_at(i, x) |
O(n) | O(n) | O(n) | O(n) | Traversal needed for LL |
remove_at(i) |
O(n) | O(n) | O(n) | O(n) | Need predecessor for SLL |
find(x) |
O(n) | O(n) | O(n) | O(n) | Linear search in all |
front() |
O(1) | O(1) | O(1) | O(1) | Direct access to head |
back() |
O(1) | O(n) | O(1) | O(1) | No tail in plain SLL |
reverse() |
O(n) | O(n) | O(n) | O(n) | Needs traversal/pointer rewiring |
size() |
O(1) | O(1) | O(1) | O(1) | Maintain a count field |
from dataclasses import dataclass
from typing import Generic, Optional, TypeVar, Iterable, Iterator
T = TypeVar("T")
@dataclass
class _Node(Generic[T]):
val: T
next: Optional["_Node[T]"] = None
class SinglyLinkedList(Generic[T]):
def __init__(self, it: Optional[Iterable[T]] = None, use_tail: bool = True):
self.head: Optional[_Node[T]] = None
self.tail: Optional[_Node[T]] = None if use_tail else None
self._n = 0; self._use_tail = use_tail
if it:
for x in it: self.push_back(x)
def __len__(self) -> int: return self._n
def __iter__(self) -> Iterator[T]:
cur = self.head
while cur:
yield cur.val; cur = cur.next
def push_front(self, x: T) -> None:
self.head = _Node(x, self.head)
if self._n == 0 and self._use_tail: self.tail = self.head
self._n += 1
def push_back(self, x: T) -> None:
n = _Node(x)
if not self.head:
self.head = n;
if self._use_tail: self.tail = n
elif self._use_tail:
self.tail.next = n # type: ignore
self.tail = n
else:
cur = self.head
while cur.next: cur = cur.next
cur.next = n
self._n += 1
def remove_after(self, prev: Optional[_Node[T]]) -> None:
if prev is None:
# remove head
if not self.head: return
self.head = self.head.next
if self._use_tail and self.head is None: self.tail = None
else:
victim = prev.next
if not victim: return
prev.next = victim.next
if self._use_tail and prev.next is None: self.tail = prev
self._n -= 1
@dataclass
class _DNode(Generic[T]):
val: T
prev: Optional["_DNode[T]"] = None
next: Optional["_DNode[T]"] = None
class CircularDLL(Generic[T]):
def __init__(self):
self.sentinel = _DNode[T](val=None) # type: ignore
self.sentinel.prev = self.sentinel.next = self.sentinel
self._n = 0
def __len__(self): return self._n
def _insert_between(self, x: T, a: _DNode[T], b: _DNode[T]):
n = _DNode(x, prev=a, next=b); a.next = n; b.prev = n; self._n += 1
def push_front(self, x: T): self._insert_between(x, self.sentinel, self.sentinel.next) # type: ignore
def push_back(self, x: T): self._insert_between(x, self.sentinel.prev, self.sentinel) # type: ignore
def remove_node(self, n: _DNode[T]):
if n is self.sentinel: return
n.prev.next = n.next; n.next.prev = n.prev # type: ignore
self._n -= 1
Note: Python has no general-purpose built-in linked list. collections.deque is a highly optimized
block-linked deque (amortized O(1) ends), great for queues/stacks but not node-addressable.
Reference cycles are GC’d, but avoid custom __del__ on nodes.
import java.util.*; LinkedList<Integer> L = new LinkedList<>(); L.addFirst(1); L.addLast(2); // O(1) ends L.removeFirst(); L.removeLast();
class CDLL<T> {
static class Node<T> { T v; Node<T> p,n; Node(T v){this.v=v;} }
private final Node<T> s = new Node<>(null); // sentinel
private int n=0;
public CDLL(){ s.p=s.n=s; }
public int size(){ return n; }
public void pushFront(T x){ insertBetween(new Node<>(x), s, s.n); }
public void pushBack(T x){ insertBetween(new Node<>(x), s.p, s); }
public void remove(Node<T> x){ if(x!=s){ x.p.n=x.n; x.n.p=x.p; n--; } }
private void insertBetween(Node<T> x, Node<T> a, Node<T> b){ x.p=a; x.n=b; a.n=x; b.p=x; n++; }
}
LinkedList iterators detect concurrent structural changes.get(i) runs from the closer end; still O(n).ArrayDeque for speed/cache-locality. Use LinkedList if you truly need node-like semantics or frequent middle removals via iterators.#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
// Singly Linked List class
class SinglyLinkedList {
private:
Node* head;
public:
SinglyLinkedList() {
head = nullptr;
}
// Insert at the beginning
void insertAtHead(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}
// Insert at the end
void insertAtTail(int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
// Delete a node by value
void deleteNode(int val) {
if (!head) return;
// If head node is to be deleted
if (head->data == val) {
Node* toDelete = head;
head = head->next;
delete toDelete;
return;
}
Node* temp = head;
while (temp->next && temp->next->data != val) {
temp = temp->next;
}
if (temp->next) {
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
}
}
// Search for a value
bool search(int val) {
Node* temp = head;
while (temp) {
if (temp->data == val) return true;
temp = temp->next;
}
return false;
}
// Display the linked list
void display() {
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
// Destructor to free memory
~SinglyLinkedList() {
Node* temp = head;
while (temp) {
Node* nextNode = temp->next;
delete temp;
temp = nextNode;
}
}
};
#include <iostream>
#include <forward_list>
using namespace std;
int main() {
forward_list<int> sll;
// Insert at front (O(1))
sll.push_front(10);
sll.push_front(20);
sll.push_front(30);
cout << "Singly Linked List: ";
for (int x : sll) cout << x << " -> ";
cout << "NULL\n";
// Insert after a position
auto it = sll.begin();
sll.insert_after(it, 15); // after first element
cout << "After insert_after: ";
for (int x : sll) cout << x << " -> ";
cout << "NULL\n";
// Erase an element
sll.erase_after(it); // removes 15
cout << "After erase_after: ";
for (int x : sll) cout << x << " -> ";
cout << "NULL\n";
return 0;
}
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> dll;
// Insert at back (O(1))
dll.push_back(10);
dll.push_back(20);
dll.push_back(30);
// Insert at front (O(1))
dll.push_front(5);
cout << "Doubly Linked List: ";
for (int x : dll) cout << x << " <-> ";
cout << "NULL\n";
// Insert in the middle
auto it = dll.begin();
advance(it, 2); // move iterator 2 steps
dll.insert(it, 15);
cout << "After insert: ";
for (int x : dll) cout << x << " <-> ";
cout << "NULL\n";
// Remove a value
dll.remove(20);
cout << "After remove(20): ";
for (int x : dll) cout << x << " <-> ";
cout << "NULL\n";
return 0;
}
std::list/forward_list, insert/erase doesn’t invalidate other iterators (except erased). Splice is O(1).std::vector due to poor locality and extra indirections.push_front is O(1) for both SLL and DLL. Which pointers change?push_back O(n)? How does adding a tail make it O(1)?