Technical Interview Screen
Which is better - singly linked list or doubly linked list? What are the pros and cons of using each? In a Singly Linked List each node has pointer just to the next node and hence can be traversed in only one direction whereas in a Doubly Linked List, each node has pointers to both previous and next nodes , hence can be traversed in both directions.While this kind of traversal makes deletion of nodes easier from a doubly linked list , because we now don’t have to traverse from head and keep track of previous node but it consumes more memory since it now has to store two pointers as compared to one in case of Singly Linked List. function remove_node_singlyLinkedList(head, node) tempnode = head while (tempnode->next != node) tempnode = tempnode->next tempnode->next = node->next end function Time Complexity - O(N) function remove_node_doublyLinkedList(node) node->prev->next = node->next node->next->prev = nod
Comments