Time Complexity of Data Structures

Random Access ADT

Data Structure	Access	Search	Insertion/begin/end	Deletion/begin/end	Concat	Space
Array	\(O(1)\)	\(O(n)\)	\(O(n)\) / \(O(N)\) / \(O(1)\)	\(O(N)\) / \(O(N)\) / \(O(1)\)	\(O(n)\)	\(O(n)\)
Catenable Sorted Lists	\(O(log N)\)	\(O(\log {}N)\)	\(O(log N)\) / \(O(1)\) / \(O(1)\)	\(O(log N)\) / \(O(1)\) / \(O(1)\)	\(O(1)\)	\(O(n)\)
RRB Trees	\(O(log N)\)	\(O(log N)\)	\(O(log N)\) / \(O(1)\) / \(O(1)\)	\(O(log N)\) / \(O(1)\) / \(O(1)\)	\(O(log N)\)	\(O(n)\)
Singly Linked List	\(O(N)\)	\(O(N)\)	\(O(N)\) / \(O(1)\) / \(O(1)\)	\(O(N)\) / \(O(1)\) / \(O(1)\)	\(O(1)\)	\(O(N)\)
Doubly Linked List	\(O(N)\)	\(O(N)\)	\(O(N)\) / \(O(1)\) / \(O(1)\)	\(O(N)\) / \(O(1)\) / \(O(1)\)	\(O(1)\)	\(O(N)\)
Hash List	\(O(1)\)	\(O(1)\)	\(O(1)\) / \(O(1)\) / \(O(1)\)	\(O(1)\) / \(O(1)\) / \(O(1)\)	\(O(N)\)	\(O(N)\)

Data Structure	Access	Search	Insertion/ at End	Deletion/ at end	Concat	Space
Array	\(O(1)\)	\(O(n)\)	\(O(n)\) / \(O(1)\)	\(O(n)\) / \(O(1)\)	\(O(n)\)	\(O(n)\)
Catenable Sorted Lists	\(O(log N)\)	\(O(log N)\)	\(O(log N)\) / \(O(1)\)	\(O(log N)\) / \(O(1)\)	\(O(1)\)	\(O(n)\)
RRB Trees	\(O(log N)\)	\(O(log N)\)	\(O(log N)\) / \(O(1)\)	\(O(log N)\) / \(O(1)\)	\(O(log N)\)	\(O(n)\)