What is the time complexity of singly linked list?

Best case O(1) head insert. Average case O(n) search. Worst case O(n). Space complexity is O(n).

Singly linked list

easy

Insert at the front without shifting a single element - then search for a value and count the hops. That trade is the entire reason linked lists exist, and the entire reason arrays usually win anyway.

Best O(1) head insertAverage O(n) searchWorst O(n)Space O(n)

Loading the singly linked list engine…

Where to go next

Doubly linked list

easy

A back pointer buys O(1) deletion.

Reverse a linked list

medium

Three pointers, and the order of four lines is everything.

Arrays and memory layout

easy

Why indexing is O(1) and inserting at the front is not.