რა არის ერთმხრივი დაკავშირებული სია და როდის გამოიყენებდი ერთს?

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) ჩასმა/წაშლა თავში; იზრდება გადაცემის გარეშე; არ აქვს გაფლანგოვილი ტევადობა.
- **სუსტი მხარეები:** შემთხვევითი წვდომა არ არის; ყველა კვანძი ატარებს მეთითებების ზეწოდებას; ცუდი cache locality (გაფანტული მეხსიერება).

## რატომ არის მნიშვნელოვანი

დაკავშირებული სიები დიდი როლი ასრულებენ როდესაც ხშირად ამატებ ან აშორებ ბოლოებში და იშვიათად თვლითობ შუა რეგიონში — მაგალითად, როგორც stack-ების, queue-ების და მეზობლობის სიების საფუძველი.

მეთითებების მანიპულირების გაგება აქ საფუძველია ხეების, გრაფიკების და მრავალი ინტერვიუს პრობლემის.

ოპერაცია	დრო
ჩასმა/წაშლა თავში	O(1)
წვდომა ინდექსით	O(n)
ძებნა	O(n)