Why LinkedList is Faster than ArrayList?
Adding Element in middle of ArrayList requires reshuffling of other elements.Whereas in Linked list only two nodes(Nodes between which the element is added) needs to be changed.
Types of LinkedList?
- singly linked list
- doubly-linked list
- Circular linked list
| singly linked list | doubly-linked list |
|---|---|
| Pros:Simple in implementation, requires relatively lesser memory for storage, assuming you need to delete/insert (at) next node – deletion/insertion is faster. | Can be iterated in forward as well as reverse direction. In case of needing to delete previous node, there is no need to traverse from head node, as the node to be deleted can be found from ‘.previous’ pointer. |
| Cons:Cannot be iterated in reverse, need to maintain a handle to the head node of the list else, the list will be lost in memory. If you’re deleting previous node or inserting at previous node, you will need to traverse list from head to previous node to be able to carry out those operations – O(N) time | Relatively complex to implement, requires more memory for storage (1 ‘.previous’ pointer per node). Insertions and deletions are relatively more time consuming (assigning/reassigning ‘.previous’ pointer for neighbor nodes) |
Time complexity of a linked list
| Operation | Metrics |
|---|---|
| Indexing | O(n) |
| Inserting / Deleting at end | O(1) or O(n) |
| Inserting / Deleting in middle | O(1) with iterator O(n) with out |
The time complexity for the Inserting at the end depends if you have the location of the last node, if you do, it would be O(1) other wise you will have to search through the linked list and the time complexity would jump to O(n).