- Internally implemented as doubly linked list
- Duplicates are allowed
- Heterogeneous methods are allowed
- Null insertion is possible
- Implements Serializable and Clonable Interface but not Random Acces
- Best Chose – Frequent Operation is insertion in the middle
- Worst Chose – Frequent Operation is retrieval from middle
LinkedList Class-specific methods :
- Usually, we can use linkedlist to develop stack and queues, to provide support for this requirement linked list provides following methods :
- void addFirst(Object o)
- void addLast(Object o)
- Object getFirst()
- Object getLast()
- Object removeFirst()
- Object removeLast()
The Problem of Linked-List
Unlike array, which is a cache-friendly data structure because its elements are placed right next to each other, elements of linked-list can be placed anywhere in the memory. So when iterating through linked-list, it will cause a lot of cache miss (since we can’t make use of locality of reference), and introduce lots of performance overheads.
Complexity of Linked List
| Linked List | Time Complexity | Space Complexity |
| Adding Element | O(1) | |
| Removing Element | O(n/2), from start or end would be O(1) | |
| Iterating Elements | O(n) | |
| Retreving Element at Position | O(n/2) |