Singly vs Doubly Linked List | Java Fresher Interview

The difference comes down to how many pointers each node carries. In a singly linked list, every node has a value and a single next pointer, so I can only move forward through the list, and the list keeps track of its head. In a doubly linked list, each node has both a next and a previous pointer, so I can traverse in either direction, and the list usually tracks both the head and the tail. The most important practical consequence of that previous pointer is deletion. If I'm handed a node and asked to delete it, in a doubly linked list it's O of one, because I can immediately reach its predecessor through the prev pointer and relink both sides. In a singly linked list, I don't have a back pointer, so to delete a node I first have to walk from the head to find the node before it, which is O of n. That's a subtlety freshers often miss; they assume deletion is always O of one. The cost of the doubly linked list is memory and bookkeeping: an extra pointer per node, and every insert or delete has to maintain two links instead of one. Java's built-in LinkedList is actually a doubly linked list. Where doubly really shines is something like an LRU cache, which combines a doubly linked list with a HashMap so you can move a node to the front or evict from the back in constant time, and for deques where you add and remove at both ends. If I only need forward traversal and want to save memory, singly is simpler.