Design Linked List

Medium
2056.

Design Linked List

MediumLinked ListSimulationDesignAmazonMicrosoftGoogle

Design Linked List is a medium coding problem on simulation, asked in Amazon, Google and Microsoft interviews.

Implement your own linked list (singly or doubly linked, without the built-in list type). Positions are 0-indexed. Write the class MyLinkedList:

  • MyLinkedList() creates an empty list.
  • int get(int index) returns the value of the node at position index, or -1 if index is out of range.
  • void addAtHead(int value) inserts a node with value before the first node; it becomes the new head.
  • void addAtTail(int value) appends a node with value after the last node.
  • void addAtIndex(int index, int value) inserts a node with value so that it ends up at position index. If index equals the length it is appended; if index is greater than the length nothing is inserted.
  • void deleteAtIndex(int index) removes the node at position index if it exists.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

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
The list goes [1] → [1,3] → [1,2,3], so position 1 holds 2. Deleting position 1 leaves [1,3], and position 1 now holds 3.

Example 2

Input
["MyLinkedList","get","addAtIndex","addAtIndex","addAtTail","deleteAtIndex","get","get"] [[],[0],[1,9],[0,4],[6],[5],[0],[1]]
Output
[null,-1,null,null,null,null,4,6]
Explanation
An empty list has no position 0. Inserting at index 1 of an empty list is out of range and ignored; index 0 works. After [4,6], deleting position 5 does nothing.

Constraints

  • 0 <= index, value <= 1000
  • At most 2000 calls are made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var MyLinkedList = function() {
    
};

/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    
};

/**
 * @param {number} value
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(value) {
    
};

/**
 * @param {number} value
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(value) {
    
};

/**
 * @param {number} index
 * @param {number} value
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, value) {
    
};

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    
};

Sign in to run your own test cases

Sign in

Design Linked List — Solution in Python, Java & C++

Design Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on simulation.

Design Linked List is a medium coding problem on simulation, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Simulation
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Implement your own linked list (singly or doubly linked, without the built-in list type). Positions are 0-indexed. Write the class MyLinkedList:

  • MyLinkedList() creates an empty list.
  • int get(int index) returns the value of the node at position index, or -1 if index is out of range.
  • void addAtHead(int value) inserts a node with value before the first node; it becomes the new head.
  • void addAtTail(int value) appends a node with value after the last node.
  • void addAtIndex(int index, int value) inserts a node with value so that it ends up at position index. If index equals the length it is appended; if index is greater than the length nothing is inserted.
  • void deleteAtIndex(int index) removes the node at position index if it exists.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

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: The list goes [1] → [1,3] → [1,2,3], so position 1 holds 2. Deleting position 1 leaves [1,3], and position 1 now holds 3.

Example 2

Input: ["MyLinkedList","get","addAtIndex","addAtIndex","addAtTail","deleteAtIndex","get","get"]
[[],[0],[1,9],[0,4],[6],[5],[0],[1]]
Output: [null,-1,null,null,null,null,4,6]
Explanation: An empty list has no position 0. Inserting at index 1 of an empty list is out of range and ignored; index 0 works. After [4,6], deleting position 5 does nothing.

Constraints

  • 0 <= index, value <= 1000
  • At most 2000 calls are made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex

Hints for Design Linked List

  1. Hint 1

    Every operation needs to reach a position, so they all share one walk: from the head, follow next pointers index times.

  2. Hint 2

    Inserting or deleting at position index changes the node before it. A dummy (sentinel) node in front of the head means every position has a node before it, the head included.

  3. Hint 3

    Keep the length in a counter, so out-of-range indexes are rejected before walking.

How to solve Design Linked List

A singly linked list with a dummy node before the head and a size counter. To act at position i, walk i steps from the dummy to reach the node just before it; inserting and deleting then rewire one next pointer.

Approach

  1. Keep dummy (its next is the head) and size.
  2. get(i): if i >= size return -1; otherwise walk i + 1 steps from dummy and return that node's value.
  3. addAtIndex(i, v): if i > size do nothing. Otherwise walk i steps from dummy to node p, create a node with next = p.next, set p.next to it, increment size.
  4. addAtHead(v) is addAtIndex(0, v); addAtTail(v) is addAtIndex(size, v).
  5. deleteAtIndex(i): if i >= size do nothing. Otherwise walk i steps to p, set p.next = p.next.next, decrement size.

Why it works

After i steps from the dummy you stand on the node before position i (the dummy itself for i = 0), so splicing a node in after it puts the new node exactly at position i, and unlinking its successor removes exactly position i. The size check makes the walk never run off the end.

Complexity

  • Time — O(i) for an operation at position i (O(1) at the head); O(n) for addAtTail without a tail pointer
  • Space — O(n)

Pitfalls

  • addAtIndex with index == size appends; only index > size is ignored.
  • Without a dummy node, inserting or deleting at position 0 needs separate head-handling code — the usual source of bugs.
  • Update the size on every successful insert and delete, and only then.

Reference solution

Python

class Node:
    __slots__ = ("value", "next")

    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

class MyLinkedList:

    def __init__(self):
        self.dummy = Node(0)  # dummy.next is the head
        self.size = 0

    def _before(self, index):
        p = self.dummy
        for _ in range(index):
            p = p.next
        return p

    def get(self, index: int) -> int:
        if index >= self.size:
            return -1
        return self._before(index).next.value

    def addAtHead(self, value: int) -> None:
        self.addAtIndex(0, value)

    def addAtTail(self, value: int) -> None:
        self.addAtIndex(self.size, value)

    def addAtIndex(self, index: int, value: int) -> None:
        if index > self.size:
            return
        p = self._before(index)
        p.next = Node(value, p.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.size:
            return
        p = self._before(index)
        p.next = p.next.next
        self.size -= 1

Java

class MyLinkedList {
    private static class Node {
        int value;
        Node next;
        Node(int value, Node next) { this.value = value; this.next = next; }
    }

    private Node dummy = new Node(0, null); // dummy.next is the head
    private int size = 0;

    public MyLinkedList() {
    }

    private Node before(int index) {
        Node p = dummy;
        for (int i = 0; i < index; i++) p = p.next;
        return p;
    }

    public int get(int index) {
        if (index >= size) return -1;
        return before(index).next.value;
    }

    public void addAtHead(int value) {
        addAtIndex(0, value);
    }

    public void addAtTail(int value) {
        addAtIndex(size, value);
    }

    public void addAtIndex(int index, int value) {
        if (index > size) return;
        Node p = before(index);
        p.next = new Node(value, p.next);
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index >= size) return;
        Node p = before(index);
        p.next = p.next.next;
        size--;
    }
}

C++

class MyLinkedList {
    struct Node {
        int value;
        Node* next;
    };
    Node* dummy = new Node{0, nullptr}; // dummy->next is the head
    int size = 0;

    Node* before(int index) {
        Node* p = dummy;
        for (int i = 0; i < index; i++) p = p->next;
        return p;
    }
public:
    MyLinkedList() {}

    ~MyLinkedList() {
        while (dummy) { Node* next = dummy->next; delete dummy; dummy = next; }
    }

    int get(int index) {
        if (index >= size) return -1;
        return before(index)->next->value;
    }

    void addAtHead(int value) {
        addAtIndex(0, value);
    }

    void addAtTail(int value) {
        addAtIndex(size, value);
    }

    void addAtIndex(int index, int value) {
        if (index > size) return;
        Node* p = before(index);
        p->next = new Node{value, p->next};
        size++;
    }

    void deleteAtIndex(int index) {
        if (index >= size) return;
        Node* p = before(index);
        Node* dead = p->next;
        p->next = dead->next;
        delete dead;
        size--;
    }
};

JavaScript

var MyLinkedList = function() {
    this.dummy = { value: 0, next: null }; // dummy.next is the head
    this.size = 0;
};

MyLinkedList.prototype.before = function(index) {
    var p = this.dummy;
    for (var i = 0; i < index; i++) p = p.next;
    return p;
};

MyLinkedList.prototype.get = function(index) {
    if (index >= this.size) return -1;
    return this.before(index).next.value;
};

MyLinkedList.prototype.addAtHead = function(value) {
    this.addAtIndex(0, value);
};

MyLinkedList.prototype.addAtTail = function(value) {
    this.addAtIndex(this.size, value);
};

MyLinkedList.prototype.addAtIndex = function(index, value) {
    if (index > this.size) return;
    var p = this.before(index);
    p.next = { value: value, next: p.next };
    this.size++;
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
    if (index >= this.size) return;
    var p = this.before(index);
    p.next = p.next.next;
    this.size--;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 137 simulation problems · the whole catalogue