Czym jest singly linked list i kiedy byś go użył?

Question

IT Interview Practice · Accepted Answer

A **singly linked list** is a chain of **nodes**, where each node holds a value and a pointer to the **next** node. Unlike an array, the nodes are not contiguous — they can live anywhere in memory, connected by references.

## Struktura

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## Przykład

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

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## Złożoność

| Operacja | Czas |
|---|---|
| Insert/delete at head | O(1) |
| Access by index | O(n) |
| Search | O(n) |

## Kompromisy

- **Zalety:** O(1) insert/delete at the front; grows without reallocating; no wasted capacity.
- **Wady:** no random access; every node carries pointer overhead; poor cache locality (scattered memory).

## Dlaczego to ważne

Linked lists shine when you frequently add or remove at the ends and rarely index into the middle — for example, as the backbone of stacks, queues, and adjacency lists.

Understanding pointer manipulation here is foundational for trees, graphs, and many interview problems.

Struktura

Przykład

Złożoność

Kompromisy

Dlaczego to ważne

Powiązane pytania