> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Design Linked List Python Solution with Tests

> Tested Python solution for LeetCode 707 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 707, [Medium](/catalog/medium). Topics: [Linked List](/catalog/topics/linked-list), [Design](/catalog/topics/design). [View on LeetCode](https://leetcode.com/problems/design-linked-list/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 707   # by problem number
lcpy gen -s design_linked_list   # by problem name
```

## 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 the `MyLinkedList` object.
* `int get(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.

### Examples

```
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.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_linked_list/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_linked_list/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class _Node:
    __slots__ = ("next", "val")

    def __init__(self, val: int = 0, next: "_Node | None" = None) -> None:
        self.val = val
        self.next = next


class MyLinkedList:
    # Singly linked list with a sentinel head node
    # Time: get/add_at_index/delete_at_index O(index), add_at_head O(1), add_at_tail O(n)
    # Space: O(n)
    def __init__(self) -> None:
        self._head = _Node()  # sentinel
        self._size = 0

    def _node_before(self, index: int) -> _Node | None:
        """Return the node preceding position index, or None if invalid."""
        if index < 0 or index > self._size:
            return None
        node = self._head
        for _ in range(index):
            if node.next is not None:
                node = node.next
        return node

    def get(self, index: int) -> int:
        prev = self._node_before(index)
        if prev is None or prev.next is None:
            return -1
        return prev.next.val

    def add_at_head(self, val: int) -> None:
        self._head.next = _Node(val, self._head.next)
        self._size += 1

    def add_at_tail(self, val: int) -> None:
        node = self._head
        while node.next is not None:
            node = node.next
        node.next = _Node(val)
        self._size += 1

    def add_at_index(self, index: int, val: int) -> None:
        if index < 0 or index > self._size:
            return
        prev = self._node_before(index)
        if prev is not None:
            prev.next = _Node(val, prev.next)
            self._size += 1

    def delete_at_index(self, index: int) -> None:
        prev = self._node_before(index)
        if prev is not None and prev.next is not None:
            prev.next = prev.next.next
            self._size -= 1
```

## Complexity

| Time | Space |
| - | - |
| get/add\_at\_index/delete\_at\_index O(index), add\_at\_head O(1), add\_at\_tail O(n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.