Review of SinglyLinkedList and DoublyLinkedList :
1. Both of them not able to access the data at random position in constant time.
2. Both of them are able to add a node at the beginning of the list or add a node after a given node in O(1) time.
3. Both of them are able to delete first node in O(1) time.
But it is little different in deleting the given node (Including the last node).
-> In a singly linked list , it is not able to get the previous node in constant time , we have to spend O(N) time to find out the previous node before deleting the given node.
-> In a doubly linked list , it is much easier because we delete a node using the prev reference field in O(1) time.
Time comparison
1. Both of them not able to access the data at random position in constant time.
2. Both of them are able to add a node at the beginning of the list or add a node after a given node in O(1) time.
3. Both of them are able to delete first node in O(1) time.
But it is little different in deleting the given node (Including the last node).
-> In a singly linked list , it is not able to get the previous node in constant time , we have to spend O(N) time to find out the previous node before deleting the given node.
-> In a doubly linked list , it is much easier because we delete a node using the prev reference field in O(1) time.
Time comparison
Conclusion :
If you want to delete or add a node in a linked list will be the better choice.
If you want to access an element in an array in constant time then array will be best.
No comments:
Post a Comment