# LeetCode 707: Design Linked List

## Problem Restatement

We need to design a linked list from scratch.

The implementation may use either a singly linked list or a doubly linked list. This guide uses a singly linked list.

A singly linked list node stores two things:

| Field | Meaning |
|---|---|
| `val` | The value stored in the node |
| `next` | A reference to the next node |

The linked list is 0-indexed.

We need to implement the `MyLinkedList` class with these operations:

| Operation | Meaning |
|---|---|
| `get(index)` | Return the value at `index`, or `-1` if invalid |
| `addAtHead(val)` | Insert `val` before the first node |
| `addAtTail(val)` | Append `val` after the last node |
| `addAtIndex(index, val)` | Insert `val` before the node at `index` |
| `deleteAtIndex(index)` | Delete the node at `index` if valid |

For `addAtIndex(index, val)`:

| Case | Behavior |
|---|---|
| `index == length` | Add at the tail |
| `index > length` | Do nothing |
| `index < length` | Insert before the current node at `index` |

## Input and Output

| Method | Input | Output |
|---|---|---|
| `MyLinkedList()` | None | Creates an empty list |
| `get(index)` | Integer index | Node value, or `-1` |
| `addAtHead(val)` | Integer value | None |
| `addAtTail(val)` | Integer value | None |
| `addAtIndex(index, val)` | Integer index and value | None |
| `deleteAtIndex(index)` | Integer index | None |

The class shape is:

```python
class MyLinkedList:

    def __init__(self):
        ...

    def get(self, index: int) -> int:
        ...

    def addAtHead(self, val: int) -> None:
        ...

    def addAtTail(self, val: int) -> None:
        ...

    def addAtIndex(self, index: int, val: int) -> None:
        ...

    def deleteAtIndex(self, index: int) -> None:
        ...
```

## Examples

Example:

```python
myLinkedList = MyLinkedList()
myLinkedList.addAtHead(1)
myLinkedList.addAtTail(3)
myLinkedList.addAtIndex(1, 2)
myLinkedList.get(1)
myLinkedList.deleteAtIndex(1)
myLinkedList.get(1)
```

Step by step:

| Operation | List After Operation | Return |
|---|---|---|
| `addAtHead(1)` | `[1]` | None |
| `addAtTail(3)` | `[1, 3]` | None |
| `addAtIndex(1, 2)` | `[1, 2, 3]` | None |
| `get(1)` | `[1, 2, 3]` | `2` |
| `deleteAtIndex(1)` | `[1, 3]` | None |
| `get(1)` | `[1, 3]` | `3` |

## First Thought: Track Only the Head

A basic singly linked list can be stored with only one pointer:

```python
self.head
```

This works, but operations at index `0` need special handling.

For example, inserting at the head changes `self.head`.

Deleting at the head also changes `self.head`.

These special cases make the code easier to get wrong.

## Key Insight

Use a dummy head node.

The dummy node does not store a real list value. It always sits before the first real node.

```python
dummy -> first -> second -> third
```

With a dummy head, inserting at index `0` becomes the same as inserting after the dummy node.

Deleting index `0` becomes the same as deleting the node after the dummy node.

This removes special cases for the head.

Also keep a size counter:

```python
self.size
```

The size counter lets us check invalid indices quickly.

## Algorithm

Use a node class:

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
```

The linked list stores:

```python
self.dummy
self.size
```

For `get(index)`:

1. If `index < 0` or `index >= size`, return `-1`.
2. Start at the first real node.
3. Move forward `index` times.
4. Return the node value.

For `addAtHead(val)`:

1. Insert at index `0`.

For `addAtTail(val)`:

1. Insert at index `size`.

For `addAtIndex(index, val)`:

1. If `index > size`, do nothing.
2. If `index < 0`, treat it like `0`.
3. Move to the node before the insertion position.
4. Link the new node into the list.
5. Increase `size`.

For `deleteAtIndex(index)`:

1. If `index < 0` or `index >= size`, do nothing.
2. Move to the node before the target.
3. Skip the target node.
4. Decrease `size`.

## Correctness

The list stores all real nodes after the dummy head. The dummy head is never returned by `get` and is never counted in `size`.

For `get(index)`, the method first rejects every invalid index. For a valid index, starting from the first real node and moving forward `index` times reaches exactly the node at that 0-based position. Returning that node's value is therefore correct.

For `addAtIndex(index, val)`, if `index > size`, the requested position is beyond the end of the list, so doing nothing follows the required behavior. If `index == size`, the method moves to the current last node and inserts after it, so the new value is appended. If `0 <= index < size`, the method moves to the node just before the current node at `index`, then rewires pointers so the new node points to the old node at `index`, and the previous node points to the new node. Thus the new value is inserted before the old node at `index`.

For `addAtHead` and `addAtTail`, both call `addAtIndex` with indices `0` and `size`, so they are correct by the same reasoning.

For `deleteAtIndex(index)`, invalid indices are ignored. For a valid index, the method moves to the node before the target and changes its `next` pointer to skip the target. This removes exactly the node at `index` while preserving the order of all other nodes.

After every insertion, `size` increases by one. After every valid deletion, `size` decreases by one. Therefore `size` always matches the number of real nodes in the list.

## Complexity

Let `n` be the current list length.

| Operation | Time | Space | Why |
|---|---|---|---|
| `get(index)` | `O(index)` | `O(1)` | Traverse to the requested node |
| `addAtHead(val)` | `O(1)` | `O(1)` | Insert after dummy |
| `addAtTail(val)` | `O(n)` | `O(1)` | Traverse to the tail |
| `addAtIndex(index, val)` | `O(index)` | `O(1)` | Traverse to the previous node |
| `deleteAtIndex(index)` | `O(index)` | `O(1)` | Traverse to the previous node |

The list itself uses `O(n)` storage for its nodes.

## Implementation

```python
class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next

class MyLinkedList:

    def __init__(self):
        self.dummy = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        cur = self.dummy.next

        for _ in range(index):
            cur = cur.next

        return cur.val

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

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

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return

        if index < 0:
            index = 0

        prev = self.dummy

        for _ in range(index):
            prev = prev.next

        node = ListNode(val)
        node.next = prev.next
        prev.next = node

        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        prev = self.dummy

        for _ in range(index):
            prev = prev.next

        prev.next = prev.next.next
        self.size -= 1
```

## Code Explanation

The node class stores a value and a pointer to the next node:

```python
class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next
```

The linked list starts with a dummy node and size `0`:

```python
self.dummy = ListNode()
self.size = 0
```

The `get` method rejects invalid indices:

```python
if index < 0 or index >= self.size:
    return -1
```

Then it starts at the first real node:

```python
cur = self.dummy.next
```

Moving forward `index` times reaches the requested node:

```python
for _ in range(index):
    cur = cur.next
```

`addAtHead` and `addAtTail` reuse the general insertion method:

```python
def addAtHead(self, val: int) -> None:
    self.addAtIndex(0, val)

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

For insertion, an index greater than the size is invalid:

```python
if index > self.size:
    return
```

A negative index is treated as insertion at the head:

```python
if index < 0:
    index = 0
```

We move to the node before the insertion point:

```python
prev = self.dummy

for _ in range(index):
    prev = prev.next
```

Then we link the new node into the list:

```python
node = ListNode(val)
node.next = prev.next
prev.next = node
```

For deletion, invalid indices are ignored:

```python
if index < 0 or index >= self.size:
    return
```

Then we move to the previous node and skip the target:

```python
prev.next = prev.next.next
```

## Testing

```python
def to_list(linked_list):
    values = []
    cur = linked_list.dummy.next

    while cur:
        values.append(cur.val)
        cur = cur.next

    return values

def test_my_linked_list():
    linked = MyLinkedList()

    linked.addAtHead(1)
    assert to_list(linked) == [1]

    linked.addAtTail(3)
    assert to_list(linked) == [1, 3]

    linked.addAtIndex(1, 2)
    assert to_list(linked) == [1, 2, 3]

    assert linked.get(1) == 2

    linked.deleteAtIndex(1)
    assert to_list(linked) == [1, 3]

    assert linked.get(1) == 3

    linked.addAtIndex(10, 9)
    assert to_list(linked) == [1, 3]

    linked.deleteAtIndex(10)
    assert to_list(linked) == [1, 3]

    linked.addAtIndex(0, 5)
    assert to_list(linked) == [5, 1, 3]

    linked.deleteAtIndex(0)
    assert to_list(linked) == [1, 3]

    print("all tests passed")

test_my_linked_list()
```

Test coverage:

| Test | Why |
|---|---|
| Add at head | Confirms insertion at index `0` |
| Add at tail | Confirms append behavior |
| Add in middle | Confirms pointer rewiring |
| Get valid index | Confirms traversal |
| Delete middle | Confirms removal |
| Invalid add index | Confirms no insertion |
| Invalid delete index | Confirms no deletion |
| Delete head | Confirms dummy node handles head removal |