Design Linked List

Problem Statement

The objective is to design a custom implementation of a linked list, which can be either singly or doubly linked. In a singly linked list, each node contains a value (val) and a reference to the next node (next). For a doubly linked list, each node additionally holds a reference to the previous node (prev). All nodes in the linked list are conveniently indexed starting from 0.

You are required to implement a class MyLinkedList with several functionalities:

• Initialize the linked list (MyLinkedList()).
• Retrieve the value at a specific index in the chain (int get(int index)). If the index is invalid, the function returns -1.
• Insert a value at the beginning of the list (void addAtHead(int val)), making this node the new head.
• Append a value to the end (void addAtTail(int val)).
• Insert a value such that it occupies a given index position (void addAtIndex(int index, int val)). If index is equal to the length of the list, the new node is added to the end. If index is beyond the current bounds, the addition is abandoned.
• Remove the node at a specified index (void deleteAtIndex(int index)), provided the index is valid.

These operations provide a robust set of functionalities typical of a linked list, while the constraints ensure that every aspect of the list management—from adding nodes in various positions to retrieving and deleting nodes—is covered.

Examples

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 and Intuition

When approaching the implementation of a linked list, it’s important to keep the following considerations and steps in mind:

1. Choosing Between Singly or Doubly Linked List:

   • A singly linked list is simpler and uses less memory per node since it only holds a reference to the next node.
   • A doubly linked list allows easier element deletion (particularly near the tail) and bi-directional traversal, which can be advantageous depending on the operations that will be most frequently performed.

2. Implementation Details:

   • For each operation, boundary conditions need special attention, especially with operations that modify the list structure like addAtHead, addAtTail, addAtIndex, and deleteAtIndex.
   • For get(int index), traverse the list from the head up to the specified index. Consider implementing checks for negative or out of bounds index values.
   • When adding nodes (addAtHead, addAtTail, addAtIndex), connectivity between nodes needs to be preserved. For example, inserting at the head requires updating the next property of the new node to the former head.

3. Edge Cases:

   • Adding or deleting nodes when the list is empty.
   • Deleting the only node in the list.
   • Adding a node at the end of the list vs. adding to an empty list with addAtIndex.

By following these guidelines and carefully considering the constraints, the custom MyLinkedList class can effectively replicate and operate as a fully functional linked list.## Problem Statement

The objective is to design a custom implementation of a linked list, which can be either singly or doubly linked. In a singly linked list, each node contains a value (val) and a reference to the next node (next). For a doubly linked list, each node additionally holds a reference to the previous node (prev). All nodes in the linked list are conveniently indexed starting from 0.

You are required to implement a class MyLinkedList with several functionalities:

• Initialize the linked list (MyLinkedList()).
• Retrieve the value at a specific index in the chain (int get(int index)). If the index is invalid, the function returns -1.
• Insert a value at the beginning of the list (void addAtHead(int val)), making this node the new head.
• Append a value to the end (void addAtTail(int val)).
• Insert a value such that it occupies a given index position (void addAtIndex(int index, int val)). If index is equal to the length of the list, the new node is added to the end. If index is beyond the current bounds, the addition is abandoned.
• Remove the node at a specified index (void deleteAtIndex(int index)), provided the index is valid.

These operations provide a robust set of functionalities typical of a linked list, while the constraints ensure that every aspect of the list management—from adding nodes in various positions to retrieving and deleting nodes—is covered.

Examples

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 and Intuition

When approaching the implementation of a linked list, it’s important to keep the following considerations and steps in mind:

1. Choosing Between Singly or Doubly Linked List:

   • A singly linked list is simpler and uses less memory per node since it only holds a reference to the next node.
   • A doubly linked list allows easier element deletion (particularly near the tail) and bi-directional traversal, which can be advantageous depending on the operations that will be most frequently performed.

2. Implementation Details:

   • For each operation, boundary conditions need special attention, especially with operations that modify the list structure like addAtHead, addAtTail, addAtIndex, and deleteAtIndex.
   • For get(int index), traverse the list from the head up to the specified index. Consider implementing checks for negative or out of bounds index values.
   • When adding nodes (addAtHead, addAtTail, addAtIndex), connectivity between nodes needs to be preserved. For example, inserting at the head requires updating the next property of the new node to the former head.

3. Edge Cases:

   • Adding or deleting nodes when the list is empty.
   • Deleting the only node in the list.
   • Adding a node at the end of the list vs. adding to an empty list with addAtIndex.

By following these guidelines and carefully considering the constraints, the custom MyLinkedList class can effectively replicate and operate as a fully functional linked list.

Solutions

public class Node {
  int value;
  Node nextNode;
  Node prevNode;
  Node(int x) { value = x; }
}

class DoubleLinkedList {
  int length;
  Node start, end;

  public DoubleLinkedList() {
    length = 0;
    start = new Node(0);
    end = new Node(0);
    start.nextNode = end;
    end.prevNode = start;
  }

  public int getValue(int index) {
    if (index < 0 || index >= length) return -1;
    Node current = start;
    if (index < length - index)
      for (int i = 0; i <= index; i++) current = current.nextNode;
    else {
      current = end;
      for (int i = 0; i < length - index; i++) current = current.prevNode;
    }
    return current.value;
  }

  public void insertAtHead(int value) {
    Node predecessor = start, successor = start.nextNode;
    length++;
    Node newNode = new Node(value);
    newNode.prevNode = predecessor;
    newNode.nextNode = successor;
    predecessor.nextNode = newNode;
    successor.prevNode = newNode;
  }

  public void insertAtTail(int value) {
    Node successor = end, predecessor = end.prevNode;
    length++;
    Node newNode = new Node(value);
    newNode.prevNode = predecessor;
    newNode.nextNode = successor;
    predecessor.nextNode = newNode;
    successor.prevNode = newNode;
  }

  public void insertAtIndex(int index, int value) {
    if (index > length) return;
    if (index < 0) index = 0;

    Node predecessor, successor;
    if (index < length - index) {
      predecessor = start;
      for (int i = 0; i < index; i++) predecessor = predecessor.nextNode;
      successor = predecessor.nextNode;
    } else {
      successor = end;
      for (int i = 0; i < length - index; i++) successor = successor.prevNode;
      predecessor = successor.prevNode;
    }

    length++;
    Node newNode = new Node(value);
    newNode.prevNode = predecessor;
    newNode.nextNode = successor;
    predecessor.nextNode = newNode;
    successor.prevNode = newNode;
  }

  public void removeAtIndex(int index) {
    if (index < 0 || index >= length) return;

    Node predecessor, successor;
    if (index < length - index) {
      predecessor = start;
      for (int i = 0; i < index; i++) predecessor = predecessor.nextNode;
      successor = predecessor.nextNode.nextNode;
    } else {
      successor = end;
      for (int i = 0; i < length - index - 1; i++) successor = successor.prevNode;
      predecessor = successor.prevNode.prevNode;
    }

    length--;
    predecessor.nextNode = successor;
    successor.prevNode = predecessor;
  }
}