Skip to main content
Talentd

Design Linked List - Solution & Explanation

MediumLinked ListDesign28 min readAsked at: Amazon, Microsoft, Apple +3
Practice this problem

Problem Statement

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

  • MyLinkedList() Initializes the MyLinkedList object.
  • int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
  • void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • void addAtTail(int val) Append a node of value val as the last element of the linked list.
  • void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
  • void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

 

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

 

Constraints:

  • 0 <= index, val <= 1000
  • Please do not use the built-in LinkedList library.
  • At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Approach Overview

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.

Approach 1: Singly Linked List Implementation

In this approach, you will design a singly linked list where each node has a value and a pointer to the next node. This type of list is simple and efficient for certain operations, especially when traversing only forwards is sufficient.

The above code implements a singly linked list in C. It provides functions to add nodes at the head, tail, a specific index, get the value at an index, and delete a node at an index. The linked list maintains a head pointer and nodes are dynamically allocated using malloc.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.

Try this approach in the editor →

Approach 2: Doubly Linked List Implementation

This approach designs a doubly linked list, allowing traversal both forwards and backwards. Each node maintains a reference to both the next and previous node, facilitating operations such as adding or removing nodes from either end more efficiently.

The C implementation of a doubly linked list adds a prev pointer to each node, enabling two-way node traversal and efficient deletion and insertion operations from both ends.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Singly Linked List Implementation

Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.

Doubly Linked List Implementation

Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Singly Linked List ImplementationO(n) per indexed operationO(n)Standard implementation when simplicity matters and traversal from head is acceptable
Doubly Linked List with SentinelsO(min(i, n-i))O(n)Better for frequent index operations and when traversal from both ends improves performance

Video Solution

Design Linked List - Leetcode 707 - Python • NeetCodeIO • 47,673 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Linked List easy or hard?
Design Linked List is considered a medium difficulty problem. The logic is straightforward, but many candidates make mistakes with pointer updates, index validation, or edge cases such as inserting at index 0 or deleting the last node.
Design Linked List Python/Java solution
Python and Java solutions typically define a Node class containing value and pointer fields. The main LinkedList class maintains the head pointer and implements get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex methods. Both languages follow the same pointer update logic, leading to O(n) time for indexed operations.
How to solve Design Linked List in O(n)?
Use a node-based linked list where each node stores a value and a pointer to the next node. Traverse the list to locate the position for get, insertion, or deletion operations. Update pointers carefully when inserting or removing nodes. This guarantees O(n) traversal time and O(1) pointer updates once the position is found.
What is the best approach for Design Linked List?
The most common solution is implementing a singly linked list with a head pointer and optional size tracking. Each operation such as get, addAtIndex, and deleteAtIndex traverses the list to the required node, resulting in O(n) time complexity. A doubly linked list with head and tail sentinels is often considered a cleaner and more optimized design because it allows traversal from either end.
Is Design Linked List asked at Google/Amazon/Meta?
Linked list design problems frequently appear in interviews at companies such as Amazon, Google, and Meta. While the exact LeetCode problem may not appear verbatim, interviewers often ask candidates to implement a linked list or modify one with operations like insert, delete, or reverse.
What data structure is used in Design Linked List?
The problem uses a linked list data structure composed of nodes connected by pointers. Each node typically stores a value and a reference to the next node, and in doubly linked lists it also stores a reference to the previous node.
What is the time complexity of Design Linked List?
Most operations run in O(n) time because the list must be traversed to reach a specific index. addAtHead runs in O(1) since it directly updates the head pointer. With a doubly linked list and tail pointer, traversal can be optimized to O(min(i, n-i)) depending on whether the search starts from the head or tail.

Ready to solve this problem?

Practice Design Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Skiplist