Design Linked List - Solution & Explanation

Problem Overview: Design a data structure that behaves like a linked list. You must implement get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex operations without using built‑in list libraries.

The challenge is not the algorithms themselves but building a clean linked list design. Each operation requires careful pointer updates and edge case handling such as inserting at the head, deleting the first node, or accessing invalid indices. The problem tests your understanding of Linked List structure and basic Design principles.

Approach 1: Singly Linked List Implementation (Time: O(n) per operation, Space: O(n))

This approach uses a classic singly linked list where each node stores a value and a pointer to the next node. Maintain a head pointer and optionally track the list size to simplify index validation. For get(index), iterate from the head until the target position. For insertion or deletion at an index, iterate to the previous node and update pointers accordingly. Operations like addAtHead are constant time because the head pointer is updated directly, but most index-based operations require traversal, resulting in O(n) time.

The key insight is pointer manipulation: inserting means connecting prev.next → newNode and newNode.next → nextNode. Deletion skips a node by linking prev.next → prev.next.next. This approach is straightforward and commonly implemented during interviews because it demonstrates a solid understanding of node traversal and pointer updates.

Approach 2: Doubly Linked List Implementation (Time: O(min(i, n-i)), Space: O(n))

A doubly linked list stores both next and prev pointers in each node. Using sentinel head and tail nodes simplifies edge cases because insertions and deletions always happen between two nodes. The major advantage appears when accessing nodes by index: you can traverse from the head if the index is in the first half, or from the tail if it is in the second half. This reduces traversal to O(min(i, n-i)).

Insertion connects four pointers: prev.next, new.prev, new.next, and next.prev. Deletion reconnects the neighboring nodes directly. Because you maintain both directions, tail insertions become constant time and index access becomes faster for large lists.

Recommended for interviews: Start with the singly linked list implementation. Interviewers want to see that you can manage node traversal and pointer updates correctly. The doubly linked list version demonstrates stronger design thinking and optimization awareness, especially when you explain how bidirectional traversal reduces search time for indices near the tail.