This problem asks you to design and implement your own linked list from scratch, either as a singly linked list or a doubly linked list, depending on your choice. Here’s a simplified explanation of the requirements:
- Constructor (MyLinkedList):
- get(int index)
- addAtHead(int val)
- addAtTail(int val)
- addAtIndex(int index, int val)
- deleteAtIndex(int index)
Tradeoffs Between Singly and Doubly Linked List
1. Singly Linked List:
• Simpler to implement.
• Requires less memory because each node only stores next.
• Cannot traverse backward.
class SinglyLinkedList {
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
private Node head;
public SinglyLinkedList() {
this.head = null;
}
public void addAtHead(int val) {
Node newNode = new Node(val);
newNode.next = head;
head = newNode;
}
public void addAtTail(int val) {
if (head == null) {
head = new Node(val);
return;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = new Node(val);
}
public void deleteAtIndex(int index) {
if (index == 0 && head != null) {
head = head.next;
return;
}
Node curr = head;
for (int i = 0; i < index - 1 && curr != null; i++) {
curr = curr.next;
}
if (curr == null || curr.next == null) return;
curr.next = curr.next.next;
}
}Line-By-Line Walkthrough
Step 1: Create Node
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}- A linked list is made up of nodes, each storing a value and a pointer to the next node.
Step 2: State
private Node head;
private int size;- The head allows the list to keep track of its starting point for traversals and operations.
Step 3: Constructor
public SinglyLinkedList() {
this.head = null;
this.size = 0;
}- Initializes an empty linked list
- Sets head to null and size to 0;
Step 4: Get
public int get(int index) {
if (index < 0 || index >= size) return -1;
Node curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.value;
}if(index < 0 || index >= size)- Validates the index and prevents invalid memory access.
Node curr = head;- Start traversal at the head of the linked list.
for(int i = 0; i < index; i++)- Traverses the list until the desired index.
Step 5: Add At Head
public void addAtHead(int val) {
Node newNode = new Node(val);
newNode.next = head;
head = newNode;
size++;
}Node newNode = new Node(val);- Creates a new node with the given value
newNode.next = head;- Links the new node to the current head
head = newNode;- Updates the head to point to the new node.
size++- Increment our state so that we can access it later.
Step 5: Add At Tail
public void addAtTail(int val) {
if (head == null) {
head = new Node(val);
} else {
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = new Node(val);
}
size++;
}if(head == null)- Handles edge case where the list is empty
Node curr = head- Assign new pointer so that we don’t manipulate the actual head.
while(curr.next != null)- Traverses the list to find the last ndoe
curr.next = new Node(val)- Adds the new node at the end of the list.
Step 6: AddAtIndex
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
if (index == 0) {
addAtHead(val);
} else {
Node curr = head;
for (int i = 0; i < index - 1; i++) {
curr = curr.next;
}
Node newNode = new Node(val);
newNode.next = curr.next;
curr.next = newNode;
size++;
}
}if(index < 0 || index > size)- Validates the index
if(index == 0)- Add to head
for(int i = 0; i < index - 1; i++)- Traverses to the node just before the target index
newNode.next = curr.next; curr.next = newNode;- Inserts the new node at the desired position.
Step 7: Delete At Index
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
if (index == 0) {
head = head.next;
} else {
Node curr = head;
for (int i = 0; i < index - 1; i++) {
curr = curr.next;
}
curr.next = curr.next.next;
}
size--;
}if(index < 0 || index >= size)- Validates the index. If invalid, do nothing.
if(index == 0)- Special case: Adding at the head.
for(int i = 0; i < index - 1; i++)- Traverses to the node just before the target index.
curr.next = curr.next.next;- Inserts the new node at the desired position
Doubly-Linked List
2. Doubly Linked List:
• Allows bi-directional traversal, making some operations (e.g., deletion) faster.
• Uses more memory because each node stores prev and next.
• Slightly more complex to manage pointers during insertion and deletion.
class DoublyLinkedList {
class Node {
int value;
Node prev, next;
Node(int value) {
this.value = value;
}
}
private Node head, tail;
private int size;
public DoublyLinkedList() {
this.head = new Node(0); // Dummy head
this.tail = new Node(0); // Dummy tail
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
}
public int get(int index) {
if (index < 0 || index >= size) return -1;
Node curr = head.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.value;
}
public void addAtHead(int val) {
Node newNode = new Node(val);
Node next = head.next;
newNode.next = next;
newNode.prev = head;
head.next = newNode;
next.prev = newNode;
size++;
}
public void addAtTail(int val) {
Node newNode = new Node(val);
Node prev = tail.prev;
newNode.prev = prev;
newNode.next = tail;
prev.next = newNode;
tail.prev = newNode;
size++;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
Node curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
Node newNode = new Node(val);
Node next = curr.next;
newNode.prev = curr;
newNode.next = next;
curr.next = newNode;
next.prev = newNode;
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
Node prev = curr;
Node next = curr.next.next;
prev.next = next;
if (next != null) {
next.prev = prev;
}
size--;
}
}Line-By-Line Explanation
Step 1: Create Node
class Node {
int value;
Node prev, next;
Node(int value) {
this.value = value;
}
}- Represents an individual node in the list
- Each node contains:
- value: The data stored in the node.
- prev: A reference to the previous node.
- next: A reference to the next node.
Step 2: State
private Node head, tail;
private int size;- head: Dummy node representing the start of the list.
- tail: Dummy node representing the end of the list.
- size: Help validate indices and improves efficiency when checking the list’s length.
Step 3: Constructor
public DoublyLinkedList() {
this.head = new Node(0); // Dummy head
this.tail = new Node(0); // Dummy tail
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
}- Dummy nodes simplify operations (adding or removing nodes) by eliminating the need for special cases when the list is empty or has one element
Step 4: Get
public int get(int index) {
if (index < 0 || index >= size) return -1;
Node curr = head.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.value;
}if(index < 0 || index >= size)- Validates the index
Node curr = head.next;- Starts traversal from the first real node (after the dummy head).
for(int i = 0; i < index; i++)- Traverses the list until the desired index is reached.
Step 5: Add at head
public void addAtHead(int val) {
Node newNode = new Node(val);
Node next = head.next;
newNode.next = next;
newNode.prev = head;
head.next = newNode;
next.prev = newNode;
size++;
}Node newNode = new Node(val)- Creates a new node with the given value.
Node next = head.next;- Stores a reference to the current first node.
- Link Updates
- newNode.next = next: Points the new node to the current first node.
- newNode.prev = head: Points the new node back to the dummy head.
- head.next = newNode: Updates the dummy head to point to the new node.
- next.prev = newNode: Updates the old first node to point back to the new node.
- size++: Increments the size of the list.
Step 6: Add at tail
public void addAtTail(int val) {
Node newNode = new Node(val);
Node prev = tail.prev;
newNode.prev = prev;
newNode.next = tail;
prev.next = newNode;
tail.prev = newNode;
size++;
}Node newNode = new Node(val);- Creates a new node with the given value.
Node prev = tail.prev;- Retrieves the current last node.
- Link Updates:
- newNode.prev = prev: Points the new node back to the current last node.
- newNode.next = tail: Points the new node forward to the dummy tail.
- prev.next = newNode: Updates the last node to point to the new node.
- tail.prev = newNode: Updates the dummy tail to point back to the new node.
- size++
- Increments the size of the list.
Step 7: Add At Index
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
Node curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
Node newNode = new Node(val);
Node next = curr.next;
newNode.prev = curr;
newNode.next = next;
curr.next = newNode;
next.prev = newNode;
size++;
}if(index < 0 || index > size)- Validates the index
Node curr = head;- Assigns pointer so that the head is not directly manipulated during traversal
Node newNode = new Node(val)- Creates the new node.
- Link Updates:
- Same as in addAtHead or addAtTail, but generalized for any position.
Step 8: Delete At Index
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
Node prev = curr;
Node next = curr.next.next;
prev.next = next;
if (next != null) {
next.prev = prev;
}
size--;
}if(index < 0 || index > size)- Validates the index
Node curr = head;- Assigns pointer so that the head is not directly manipulated during traversal
Node newNode = new Node(val)- Creates the new node.
- Link Updates:
- prev.next = next skips the target node.
- next.prev = prev updates the back pointer
Why This Code Works
• Use singly linked lists when memory efficiency and simple operations are priorities.
• Use doubly linked lists when you need fast insertions/deletions at both ends or bi-directional navigation.
Both implementations demonstrate a clear understanding of data structure fundamentals and strike a balance between performance, clarity, and adaptability, making them excellent solutions for LeetCode and real-world scenarios alike.
