Linked List
A Linked List is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.
- Singly-linked list: linked list in which each node points to the next node and the last node points to null
- Doubly-linked list: linked list in which each node has two pointers, p and n, such that p points to the previous node and n points to the next node; the last node's n pointer points to null
- Circular-linked list: linked list in which each node points to the next node and the last node points back to the first node
Time Complexity:
- Access: O(n)
- Search: O(n)
- Insert: O(1)
- Remove: O(1)