Design Linked List solution and explanation
Google
9 more videos on this problem
Design Linked List - Leetcode 707 - PythonNeetCodeIO · 13:50 · 47K views
LeetCode 707: Singly Linked ListHelmyCodeCamp · 17:02 · 2K views
LEETCODE 707 (JAVASCRIPT) | DESIGN LINKED LISTAndy Gala · 19:51 · 2K views
Daily LeetCode Challenge [16]: 707. Design Linked List. (#linkedlist)The Brown Box · 19:20 · 2K views
[DS Design]707 Design Linked ListXIAOLONG · 15:33 · 1K views
LeetCode 707. Design Linked List | Java | Aadil MirMirTechTutorials · 21:30 · 920 views
Design Linked List - LeetCode 707 - PythonAlpha-Code · 26:47 · 791 views
Leetcode 707 : Doubly LinkedList PythonHelmyCodeCamp · 19:44 · 590 views
Leetcode #707: Design Linked ListAlex Tong · 57:58 · 449 views
707. Design Linked List (Leetcode Medium)Programming Live with Larry · 8:17 · 360 views
The problem
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 theMyLinkedListobject.int get(int index)Get the value of theindexthnode in the linked list. If the index is invalid, return-1.void addAtHead(int val)Add a node of valuevalbefore 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 valuevalas the last element of the linked list.void addAtIndex(int index, int val)Add a node of valuevalbefore theindexthnode in the linked list. Ifindexequals the length of the linked list, the node will be appended to the end of the linked list. Ifindexis greater than the length, the node will not be inserted.void deleteAtIndex(int index)Delete theindexthnode 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
2000calls will be made toget,addAtHead,addAtTail,addAtIndexanddeleteAtIndex.
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.
class Node:
def __init__(self, val: int):
self.val = val
self.next = None
class MyLinkedList:
def __init__(self):
self.head = None
def get(self, index: int) -> int:
current = self.head
for i in range(index):
if current is None:
return -1
current = current.next
return current.val if current else -1
def addAtHead(self, val: int) -> None:
node = Node(val)
node.next = self.head
self.head = node
def addAtTail(self, val: int) -> None:
node = Node(val)
if not self.head:
self.head = node
else:
current = self.head
while current.next:
current = current.next
current.next = node
def addAtIndex(self, index: int, val: int) -> None:
if index == 0:
self.addAtHead(val)
return
current = self.head
for i in range(index - 1):
if current is None:
return
current = current.next
if not current: return
node = Node(val)
node.next = current.next
current.next = node
def deleteAtIndex(self, index: int) -> None:
if index == 0:
if self.head:
self.head = self.head.next
return
current = self.head
for i in range(index - 1):
if current is None:
return
current = current.next
if current and current.next:
current.next = current.next.nextclass MyLinkedList {
class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
private Node head;
public MyLinkedList() {
head = null;
}
public int get(int index) {
Node current = head;
for (int i = 0; current != null && i < index; i++) {
current = current.next;
}
return current == null ? -1 : current.val;
}
public void addAtHead(int val) {
Node node = new Node(val);
node.next = head;
head = node;
}
public void addAtTail(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
public void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
Node current = head;
for (int i = 0; current != null && i < index - 1; i++) {
current = current.next;
}
if (current == null) return;
Node node = new Node(val);
node.next = current.next;
current.next = node;
}
public void deleteAtIndex(int index) {
if (index == 0 && head != null) {
head = head.next;
return;
}
Node current = head;
for (int i = 0; current != null && i < index - 1; i++) {
current = current.next;
}
if (current != null && current.next != null) {
current.next = current.next.next;
}
}
}#include <iostream>
class MyLinkedList {
private:
struct Node {
int val;
Node* next;
Node(int _val) : val(_val), next(nullptr) {}
};
Node* head;
public:
MyLinkedList() : head(nullptr) {}
int get(int index) {
Node* current = head;
for (int i = 0; current && i < index; ++i) {
current = current->next;
}
return current ? current->val : -1;
}
void addAtHead(int val) {
Node* node = new Node(val);
node->next = head;
head = node;
}
void addAtTail(int val) {
Node* node = new Node(val);
if (!head) {
head = node;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = node;
}
}
void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
Node* current = head;
for (int i = 0; current && i < index - 1; ++i) {
current = current->next;
}
if (current) {
Node* node = new Node(val);
node->next = current->next;
current->next = node;
}
}
void deleteAtIndex(int index) {
if (index == 0 && head) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
for (int i = 0; current && i < index - 1; ++i) {
current = current->next;
}
if (current && current->next) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
};class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class MyLinkedList {
constructor() {
this.head = null;
}
get(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
if (!current) return -1;
current = current.next;
}
return current ? current.val : -1;
}
addAtHead(val) {
const node = new Node(val);
node.next = this.head;
this.head = node;
}
addAtTail(val) {
const node = new Node(val);
if (!this.head) {
this.head = node;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
addAtIndex(index, val) {
if (index === 0) {
this.addAtHead(val);
return;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
if (!current) return;
current = current.next;
}
if (current) {
const node = new Node(val);
node.next = current.next;
current.next = node;
}
}
deleteAtIndex(index) {
if (index === 0 && this.head) {
this.head = this.head.next;
return;
}
let current = this.head;
for (let i = 0; i < index - 1 && current; i++) {
current = current.next;
}
if (current && current.next) {
current.next = current.next.next;
}
}
}#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node* next;
};
struct MyLinkedList {
struct Node* head;
};
struct MyLinkedList* myLinkedListCreate() {
struct MyLinkedList* obj = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
obj->head = NULL;
return obj;
}
void myLinkedListAddAtHead(struct MyLinkedList* obj, int val) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->next = obj->head;
obj->head = node;
}
void myLinkedListAddAtTail(struct MyLinkedList* obj, int val) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->next = NULL;
if (obj->head == NULL) {
obj->head = node;
} else {
struct Node* current = obj->head;
while (current->next != NULL) {
current = current->next;
}
current->next = node;
}
}
int myLinkedListGet(struct MyLinkedList* obj, int index) {
struct Node* current = obj->head;
int i = 0;
while (current != NULL && i < index) {
current = current->next;
i++;
}
return (current == NULL) ? -1 : current->val;
}
void myLinkedListAddAtIndex(struct MyLinkedList* obj, int index, int val) {
if(index == 0) {
myLinkedListAddAtHead(obj, val);
return;
}
struct Node* current = obj->head;
for(int i = 0; current != NULL && i < index - 1; i++) {
current = current->next;
}
if (current == NULL) return;
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->next = current->next;
current->next = node;
}
void myLinkedListDeleteAtIndex(struct MyLinkedList* obj, int index) {
struct Node* current = obj->head;
if (index == 0 && current != NULL) {
obj->head = current->next;
free(current);
return;
}
struct Node* prev = NULL;
for (int i = 0; current != NULL && i < index; i++) {
prev = current;
current = current->next;
}
if(current == NULL) return;
prev->next = current->next;
free(current);
}
void myLinkedListFree(struct MyLinkedList* obj) {
struct Node* current = obj->head;
while (current != NULL) {
struct Node* next = current->next;
free(current);
current = next;
}
free(obj);
}public class MyLinkedList {
private class Node {
public int val;
public Node next;
public Node(int _val) { val = _val; }
}
private Node head;
public MyLinkedList() {
head = null;
}
public int Get(int index) {
Node current = head;
for (int i = 0; i < index && current != null; i++) {
current = current.next;
}
return current == null ? -1 : current.val;
}
public void AddAtHead(int val) {
Node node = new Node(val);
node.next = head;
head = node;
}
public void AddAtTail(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
}
public void AddAtIndex(int index, int val) {
if (index == 0) {
AddAtHead(val);
return;
}
Node current = head;
for (int i = 0; i < index - 1 && current != null; i++) {
current = current.next;
}
if (current != null) {
Node node = new Node(val);
node.next = current.next;
current.next = node;
}
}
public void DeleteAtIndex(int index) {
if (index == 0 && head != null) {
head = head.next;
return;
}
Node current = head;
for (int i = 0; i < index - 1 && current != null; i++) {
current = current.next;
}
if (current != null && current.next != null) {
current.next = current.next.next;
}
}
}This Python solution uses a class-based approach to represent nodes and the singly linked list. The list starts at the head node and supports operations like adding and removing elements at various positions efficiently.
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.
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.
class Node:
def __init__(self, val: int):
self.val = val
self.next = None
self.prev = None
class MyLinkedList:
def __init__(self):
self.head = None
def get(self, index: int) -> int:
current = self.head
for i in range(index):
if current is None:
return -1
current = current.next
return current.val if current else -1
def addAtHead(self, val: int) -> None:
node = Node(val)
node.next = self.head
if self.head:
self.head.prev = node
self.head = node
def addAtTail(self, val: int) -> None:
node = Node(val)
if not self.head:
self.head = node
else:
current = self.head
while current.next:
current = current.next
current.next = node
node.prev = current
def addAtIndex(self, index: int, val: int) -> None:
if index == 0:
self.addAtHead(val)
return
current = self.head
for i in range(index - 1):
if current is None:
return
current = current.next
if not current: return
node = Node(val)
node.next = current.next
if current.next:
current.next.prev = node
current.next = node
node.prev = current
def deleteAtIndex(self, index: int) -> None:
current = self.head
for i in range(index):
if current is None:
return
current = current.next
if current is None: return
if current.prev:
current.prev.next = current.next
else:
self.head = current.next
if current.next:
current.next.prev = current.prevclass MyLinkedList {
class Node {
int val;
Node next;
Node prev;
Node(int val) { this.val = val; }
}
private Node head;
public MyLinkedList() {
head = null;
}
public int get(int index) {
Node current = head;
for (int i = 0; current != null && i < index; i++) {
current = current.next;
}
return current == null ? -1 : current.val;
}
public void addAtHead(int val) {
Node node = new Node(val);
node.next = head;
if (head != null) head.prev = node;
head = node;
}
public void addAtTail(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
node.prev = current;
}
public void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
Node current = head;
for (int i = 0; current != null && i < index - 1; i++) {
current = current.next;
}
if (current == null) return;
Node node = new Node(val);
node.next = current.next;
if (current.next != null) current.next.prev = node;
current.next = node;
node.prev = current;
}
public void deleteAtIndex(int index) {
Node current = head;
for (int i = 0; current != null && i < index; i++) {
current = current.next;
}
if (current == null) return;
if (current.prev != null) current.prev.next = current.next;
else head = current.next;
if (current.next != null) current.next.prev = current.prev;
}
}#include <iostream>
class MyLinkedList {
private:
struct Node {
int val;
Node* next;
Node* prev;
Node(int _val) : val(_val), next(nullptr), prev(nullptr) {}
};
Node* head;
public:
MyLinkedList() : head(nullptr) {}
int get(int index) {
Node* current = head;
for (int i = 0; current && i < index; ++i) {
current = current->next;
}
return current ? current->val : -1;
}
void addAtHead(int val) {
Node* node = new Node(val);
node->next = head;
if (head) head->prev = node;
head = node;
}
void addAtTail(int val) {
Node* node = new Node(val);
if (!head) {
head = node;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = node;
node->prev = current;
}
}
void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
return;
}
Node* current = head;
for (int i = 0; current && i < index - 1; ++i) {
current = current->next;
}
if (current) {
Node* node = new Node(val);
node->next = current->next;
if (current->next) current->next->prev = node;
current->next = node;
node->prev = current;
}
}
void deleteAtIndex(int index) {
Node* current = head;
for (int i = 0; current && i < index; ++i) {
current = current->next;
}
if (!current) return;
if (current->prev) current->prev->next = current->next;
else head = current->next;
if (current->next) current->next->prev = current->prev;
delete current;
}
};class Node {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
class MyLinkedList {
constructor() {
this.head = null;
}
get(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
if (!current) return -1;
current = current.next;
}
return current ? current.val : -1;
}
addAtHead(val) {
const node = new Node(val);
node.next = this.head;
if (this.head) this.head.prev = node;
this.head = node;
}
addAtTail(val) {
const node = new Node(val);
if (!this.head) {
this.head = node;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
}
addAtIndex(index, val) {
if (index === 0) {
this.addAtHead(val);
return;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
if (!current) return;
current = current.next;
}
if (current) {
const node = new Node(val);
node.next = current.next;
if (current.next) current.next.prev = node;
current.next = node;
node.prev = current;
}
}
deleteAtIndex(index) {
let current = this.head;
for (let i = 0; i < index && current; i++) {
current = current.next;
}
if (!current) return;
if (current.prev) current.prev.next = current.next;
else this.head = current.next;
if (current.next) current.next.prev = current.prev;
}
}#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node* next;
struct Node* prev;
};
struct MyLinkedList {
struct Node* head;
};
struct MyLinkedList* myLinkedListCreate() {
struct MyLinkedList* obj = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
obj->head = NULL;
return obj;
}
void myLinkedListAddAtHead(struct MyLinkedList* obj, int val) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->next = obj->head;
node->prev = NULL;
if (obj->head != NULL) {
obj->head->prev = node;
}
obj->head = node;
}
void myLinkedListAddAtTail(struct MyLinkedList* obj, int val) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->next = NULL;
if (obj->head == NULL) {
node->prev = NULL;
obj->head = node;
} else {
struct Node* current = obj->head;
while (current->next != NULL) {
current = current->next;
}
current->next = node;
node->prev = current;
}
}
int myLinkedListGet(struct MyLinkedList* obj, int index) {
struct Node* current = obj->head;
int i = 0;
while (current != NULL && i < index) {
current = current->next;
i++;
}
return (current == NULL) ? -1 : current->val;
}
void myLinkedListAddAtIndex(struct MyLinkedList* obj, int index, int val) {
if (index == 0) {
myLinkedListAddAtHead(obj, val);
return;
}
struct Node* current = obj->head;
for (int i = 0; current != NULL && i < index - 1; i++) {
current = current->next;
}
if (current == NULL) return;
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->next = current->next;
if (current->next != NULL) {
current->next->prev = node;
}
current->next = node;
node->prev = current;
}
void myLinkedListDeleteAtIndex(struct MyLinkedList* obj, int index) {
struct Node* current = obj->head;
int i;
for (i = 0; current != NULL && i < index; i++) {
current = current->next;
}
if (current == NULL) return;
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
obj->head = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
}
void myLinkedListFree(struct MyLinkedList* obj) {
struct Node* current = obj->head;
while (current != NULL) {
struct Node* next = current->next;
free(current);
current = next;
}
free(obj);
}public class MyLinkedList {
private class Node {
public int val;
public Node next;
public Node prev;
public Node(int _val) { val = _val; }
}
private Node head;
public MyLinkedList() {
head = null;
}
public int Get(int index) {
Node current = head;
for (int i = 0; i < index && current != null; i++) {
current = current.next;
}
return current == null ? -1 : current.val;
}
public void AddAtHead(int val) {
Node node = new Node(val);
node.next = head;
if (head != null) head.prev = node;
head = node;
}
public void AddAtTail(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
node.prev = current;
}
}
public void AddAtIndex(int index, int val) {
if (index == 0) {
AddAtHead(val);
return;
}
Node current = head;
for (int i = 0; i < index - 1 && current != null; i++) {
current = current.next;
}
if (current != null) {
Node node = new Node(val);
node.next = current.next;
if (current.next != null) current.next.prev = node;
current.next = node;
node.prev = current;
}
}
public void DeleteAtIndex(int index) {
Node current = head;
for (int i = 0; current != null && i < index; i++) {
current = current.next;
}
if (current != null) {
if (current.prev != null) current.prev.next = current.next;
else head = current.next;
if (current.next != null) current.next.prev = current.prev;
}
}
}The Python solution features a doubly linked list implementation where each node contains pointers to both previous and next nodes, improving operations for changes at arbitrary indices.
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.
Approach 3: Default Approach
class LinkNode {
public val: number;
public next: LinkNode;
constructor(val: number, next: LinkNode = null) {
this.val = val;
this.next = next;
}
}
class MyLinkedList {
public head: LinkNode;
constructor() {
this.head = null;
}
get(index: number): number {
if (this.head == null) {
return -1;
}
let cur = this.head;
let idxCur = 0;
while (idxCur < index) {
if (cur.next == null) {
return -1;
}
cur = cur.next;
idxCur++;
}
return cur.val;
}
addAtHead(val: number): void {
this.head = new LinkNode(val, this.head);
}
addAtTail(val: number): void {
const newNode = new LinkNode(val);
if (this.head == null) {
this.head = newNode;
return;
}
let cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
addAtIndex(index: number, val: number): void {
if (index <= 0) {
return this.addAtHead(val);
}
const dummy = new LinkNode(0, this.head);
let cur = dummy;
let idxCur = 0;
while (idxCur < index) {
if (cur.next == null) {
return;
}
cur = cur.next;
idxCur++;
}
cur.next = new LinkNode(val, cur.next || null);
}
deleteAtIndex(index: number): void {
if (index == 0) {
this.head = (this.head || {}).next;
return;
}
const dummy = new LinkNode(0, this.head);
let cur = dummy;
let idxCur = 0;
while (idxCur < index) {
if (cur.next == null) {
return;
}
cur = cur.next;
idxCur++;
}
cur.next = (cur.next || {}).next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/type MyLinkedList struct {
dummy *ListNode
cnt int
}
func Constructor() MyLinkedList {
return MyLinkedList{&ListNode{}, 0}
}
func (this *MyLinkedList) Get(index int) int {
if index < 0 || index >= this.cnt {
return -1
}
cur := this.dummy.Next
for ; index > 0; index-- {
cur = cur.Next
}
return cur.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.cnt, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index > this.cnt {
return
}
pre := this.dummy
for ; index > 0; index-- {
pre = pre.Next
}
pre.Next = &ListNode{val, pre.Next}
this.cnt++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.cnt {
return
}
pre := this.dummy
for ; index > 0; index-- {
pre = pre.Next
}
t := pre.Next
pre.Next = t.Next
t.Next = nil
this.cnt--
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Get(index);
* obj.AddAtHead(val);
* obj.AddAtTail(val);
* obj.AddAtIndex(index,val);
* obj.DeleteAtIndex(index);
*/#[derive(Default)]
struct MyLinkedList {
head: Option<Box<ListNode>>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyLinkedList {
fn new() -> Self {
Default::default()
}
fn get(&self, mut index: i32) -> i32 {
if self.head.is_none() {
return -1;
}
let mut cur = self.head.as_ref().unwrap();
while index > 0 {
match cur.next {
None => {
return -1;
}
Some(ref next) => {
cur = next;
index -= 1;
}
}
}
cur.val
}
fn add_at_head(&mut self, val: i32) {
self.head = Some(Box::new(ListNode {
val,
next: self.head.take(),
}));
}
fn add_at_tail(&mut self, val: i32) {
let new_node = Some(Box::new(ListNode { val, next: None }));
if self.head.is_none() {
self.head = new_node;
return;
}
let mut cur = self.head.as_mut().unwrap();
while let Some(ref mut next) = cur.next {
cur = next;
}
cur.next = new_node;
}
fn add_at_index(&mut self, mut index: i32, val: i32) {
let mut dummy = Box::new(ListNode {
val: 0,
next: self.head.take(),
});
let mut cur = &mut dummy;
while index > 0 {
if cur.next.is_none() {
return;
}
cur = cur.next.as_mut().unwrap();
index -= 1;
}
cur.next = Some(Box::new(ListNode {
val,
next: cur.next.take(),
}));
self.head = dummy.next;
}
fn delete_at_index(&mut self, mut index: i32) {
let mut dummy = Box::new(ListNode {
val: 0,
next: self.head.take(),
});
let mut cur = &mut dummy;
while index > 0 {
if let Some(ref mut next) = cur.next {
cur = next;
}
index -= 1;
}
cur.next = cur.next.take().and_then(|n| n.next);
self.head = dummy.next;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Singly Linked List Implementation | Time Complexity: |
| Doubly Linked List Implementation | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Singly Linked List Implementation | O(n) per indexed operation | O(n) | Standard implementation when simplicity matters and traversal from head is acceptable |
| Doubly Linked List with Sentinels | O(min(i, n-i)) | O(n) | Better for frequent index operations and when traversal from both ends improves performance |
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.