Τι είναι μια ενιαία συνδεδεμένη λίστα και πότε θα τη χρησιμοποιούσατε;

Question

Accepted Answer

Μια **ενιαία συνδεδεμένη λίστα** είναι μια αλυσίδα **κόμβων**, όπου κάθε κόμβος περιέχει μια τιμή και έναν δείκτη στον **επόμενο** κόμβο. Σε αντίθεση με ένα πίνακα, οι κόμβοι δεν είναι συνεχόμενοι — μπορούν να βρίσκονται οπουδήποτε στη μνήμη, συνδεδεμένοι μέσω αναφορών.

## Δομή

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

## Παράδειγμα

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

## Πολυπλοκότητα

| Λειτουργία | Χρόνος |
|---|---|
| Εισαγωγή/διαγραφή στην αρχή | O(1) |
| Πρόσβαση κατά ευρετήριο | O(n) |
| Αναζήτηση | O(n) |

## Συμβιβασμοί

- **Δυνάμεις:** O(1) εισαγωγή/διαγραφή στην αρχή; αύξηση χωρίς επανακατανομή; καμία σπατάλη χωρητικότητας.
- **Αδυναμίες:** καμία τυχαία πρόσβαση; κάθε κόμβος έχει επιβάρυνση δείκτη; κακή τοπικότητα κρυφής μνήμης (διάσπαρτη μνήμη).

## Γιατί έχει σημασία

Οι συνδεδεμένες λίστες λάμπουν όταν συχνά προσθέτετε ή αφαιρείτε στα άκρα και σπάνια δημιουργείτε ευρετήριο στη μέση — για παράδειγμα, ως η ράχη στοιβών, ουρών και λιστών γειτονίας.

Η κατανόηση του χειρισμού δεικτών εδώ είναι θεμελιώδης για δέντρα, γραφήματα και πολλά προβλήματα συνέντευξης.

Λειτουργία	Χρόνος
Εισαγωγή/διαγραφή στην αρχή	O(1)
Πρόσβαση κατά ευρετήριο	O(n)
Αναζήτηση	O(n)