# فصل ۰۶ — پیوند به‌جای پیوستگی: `linked list`

<div dir="rtl">

# فصل ۰۶ — پیوند به‌جای پیوستگی: `linked list`

## در این فصل چه یاد می‌گیری

هر بار که هزینهٔ جابه‌جایی را دیدیم، یک فکر پیش آمد: **اگر خانه‌ها لازم نبود کنارِ هم باشند، هیچ‌کدام از این جابه‌جایی‌ها لازم نمی‌شد.**

این فصل آن ظرف را می‌سازد. `linked list` هیچ نوارِ پیوسته‌ای ندارد؛ هر عضو یک **گره** است که مقدارش را نگه می‌دارد و یک **ارجاع به گرهٔ بعدی**. درج در جایی که ارجاعش را داری، `O(1)` است — بدونِ هیچ جابه‌جایی.

**بعد اندازه‌اش می‌گیریم و نتیجه منفی درمی‌آید.** روی کاری که `linked list` قرار است در آن برنده باشد، `list` بیش از چهل برابر سریع‌تر است. **این نتیجه را همان‌قدر پررنگ گزارش می‌کنیم که یک نتیجهٔ مثبت را**، چون همان‌قدر واقعی است — و دلیلش `Big-O` نیست: هر قدمِ زنجیر یک دورِ حلقهٔ پایتون است و `list` همان کار را یکجا انجام می‌دهد.

![زنجیری از مهره‌های پراکنده روی میز در برابرِ یک ریلِ فشردهٔ پیوسته](/lesson-assets/t2-s06-linked-list/prompt/01-image-chain-versus-rail.png)

آخر این فصل می‌توانی:

- یک `linked list` را از صفر بسازی، فقط با `list`های دوخانه‌ای
- بگویی درجِ `O(1)` دقیقاً کِی ممکن است و چه چیزی را فرض می‌گیرد
- **هزینهٔ رسیدن** به جای درج را از **هزینهٔ خودِ درج** جدا کنی
- یک نتیجهٔ منفی را کامل و بدونِ لاپوشانی گزارش کنی

## قبل از شروع

**از فصلِ ۱:** نزدیکیِ داده‌ها در حافظه و ضریبی که برایش اندازه گرفتیم. **از فصلِ ۴:** هزینهٔ جابه‌جایی در `list`.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | حدودِ یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-2-arrays-and-lists/session-06-linked-list.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. کوچک‌ترین نسخهٔ ممکن، با دست

یک گره فقط دو چیز لازم دارد: **مقدار**، و **ارجاع به گرهٔ بعدی**. برای همین یک `list` دوخانه‌ای کافی است. آخرین گره به‌جای گرهٔ بعدی `None` دارد.

</div>

```python
VALUE, NEXT = 0, 1


def linked_from(values):
    """از انتها به ابتدا زنجیر را می‌بندد و سرِ زنجیر را برمی‌گرداند."""
    head = None
    for v in reversed(values):
        head = [v, head]
    return head


def to_list(head):
    """زنجیر را از سر تا ته دنبال می‌کند."""
    out = []
    node = head
    while node is not None:
        out.append(node[VALUE])
        node = node[NEXT]
    return out


small = linked_from([10, 20, 30])
print("خودِ ساختار:", small)
print("پیمایشش    :", to_list(small))
print("گرهٔ اول    :", small[VALUE], "· گرهٔ دوم:", small[NEXT][VALUE],
      "· گرهٔ سوم:", small[NEXT][NEXT][VALUE])
print("بعد از سوم :", small[NEXT][NEXT][NEXT])
```

```text
خودِ ساختار: [10, [20, [30, None]]]
پیمایشش    : [10, 20, 30]
گرهٔ اول    : 10 · گرهٔ دوم: 20 · گرهٔ سوم: 30
بعد از سوم : None
```

<div dir="rtl">

**سه گره، هر کدام دو خانه، و تنها چیزی که آن‌ها را به هم وصل می‌کند یک ارجاع است.** هیچ نوارِ پیوسته‌ای در کار نیست؛ سه گره می‌توانند هر جای حافظه باشند.

**و همین‌جا دو خاصیتِ متضاد پیدا می‌شود.** خاصیتِ خوب: درج در ابتدا فقط یک گرهٔ تازه است که به سرِ فعلی وصل می‌شود — هیچ چیزی جابه‌جا نمی‌شود. خاصیتِ بد: برای رسیدن به گرهٔ صدم باید از نود و نُه گرهٔ قبلی رد شوی. **در `list` رفتن به خانهٔ صدم یک ضرب و یک جمع بود.**

## ۲. کاری که قرار است در آن برنده باشد

افزودن به ابتدا در `list` بدترین حالت بود. **در `linked list` بهترین حالت است.**

> 🤔 **اول حدس بزن:** ستونِ نسبتِ `linked list` را حدس بزن، و بعد حدس بزن نسبت به `list.insert(0, x)` چند برابر سریع‌تر می‌شود.

</div>

```python
from collections import deque


def push_front_linked(n):
    head = None
    for i in range(n):
        head = [i, head]
    return head


def push_front_list(n):
    out = []
    for i in range(n):
        out.insert(0, i)
    return out


def push_front_deque(n):
    out = deque()
    for i in range(n):
        out.appendleft(i)
    return out


print("هر سه یک ترتیب می‌دهند؟",
      to_list(push_front_linked(500)) == push_front_list(500)
      == list(push_front_deque(500)))

FRONT = [10_000, 20_000, 40_000, 80_000]
print("\n— linked list")
table([(n, 1000 * clock(lambda k=n: push_front_linked(k), repeat=3)) for n in FRONT],
      "زمان (ms)", ",.2f")
print("\n— list.insert(0, x)")
table([(n, 1000 * clock(lambda k=n: push_front_list(k), repeat=2)) for n in FRONT],
      "زمان (ms)", ",.2f")
print("\n— deque.appendleft")
table([(n, 1000 * clock(lambda k=n: push_front_deque(k), repeat=3)) for n in FRONT],
      "زمان (ms)", ",.2f")
```

```text-approx
هر سه یک ترتیب می‌دهند؟ True

— linked list
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.75                   —
    20,000              1.58                2.12
    40,000              4.44                2.81
    80,000             11.87                2.67

— list.insert(0, x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000             23.02                   —
    20,000             88.53                3.85
    40,000            368.27                4.16
    80,000          1,472.19                4.00

— deque.appendleft
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.33                   —
    20,000              0.69                2.06
    40,000              1.55                2.26
    80,000              2.66                1.71
```

<div dir="rtl">

**`linked list` همان‌طور که وعده داده شده بود از `list.insert(0, x)` می‌برد — و با فاصلهٔ خیلی زیاد**، چون ستونِ یکی حولِ `2` می‌گردد و دیگری نزدیکِ `4` است.

ستونِ `linked list` بینِ `2` و `3` می‌لرزد و این لرزش خودش یک واقعیت است: **هشتاد هزار گرهٔ تازه ساختن، کارِ حافظه است و مثلِ یک عملِ ساده رفتار نمی‌کند.** جدولِ `deque` که هیچ گرهٔ جدایی نمی‌سازد، خیلی صاف‌تر است.

**ولی جدولِ سوم را هم ببین:** `deque` همان کار را با ستونِ نسبتِ `2` و **زمانِ کمتری** انجام می‌دهد. یعنی حتی در بهترین میدانِ `linked list`، ظرفِ استانداردِ پایتون جلوتر است.

## ۳. نتیجهٔ منفی: درج در وسط

بهترین حالتِ `linked list` وقتی است که **ارجاعِ گرهٔ قبل از محلِ درج را داشته باشی**. آن‌وقت درج دو خط است و به `n` هیچ ربطی ندارد.

**سؤال این است: آن ارجاع را از کجا می‌آوری؟**

> 🤔 **اول حدس بزن:** می‌خواهیم دویست بار در **وسطِ** یک دنبالهٔ `n`تایی درج کنیم. `list` باید هر بار نصفِ داده را جابه‌جا کند و `linked list` باید هر بار تا وسط راه برود. **هر دو `O(n)` هستند.** بنویس کدامشان و چند برابر برنده می‌شود.

</div>

```python
K = 200


def middle_insert_list(values, k=K):
    out = list(values)
    for i in range(k):
        out.insert(len(out) // 2, -i)
    return out


def middle_insert_linked(head, length, k=K):
    for i in range(k):
        node = head
        for _ in range(length // 2 - 1):      # هزینهٔ رسیدن
            node = node[NEXT]
        node[NEXT] = [-i, node[NEXT]]         # هزینهٔ خودِ درج
        length += 1
    return head


base = list(range(1_000))
print("دو نسخه یک جواب می‌دهند؟",
      middle_insert_list(base) == to_list(middle_insert_linked(linked_from(base), 1_000)))

MID = [20_000, 40_000, 80_000, 160_000]
sources = {n: list(range(n)) for n in MID}
print("\n— list.insert(وسط, x)")
table([(n, 1000 * clock(lambda v=sources[n]: middle_insert_list(v), repeat=2))
       for n in MID], "زمان (ms)", ",.2f")
print("\n— linked list")
table([(n, 1000 * clock(lambda v=sources[n], k=n:
                        middle_insert_linked(linked_from(v), k), repeat=2))
       for n in MID], "زمان (ms)", ",.2f")
```

```text-approx
دو نسخه یک جواب می‌دهند؟ True

— list.insert(وسط, x)
         n         زمان (ms)     نسبت به سطر قبل
    20,000              0.94                   —
    40,000              1.84                1.96
    80,000              4.05                2.20
   160,000              8.31                2.05

— linked list
         n         زمان (ms)     نسبت به سطر قبل
    20,000             47.37                   —
    40,000             91.81                1.94
    80,000            188.74                2.06
   160,000            411.45                2.18
```

<div dir="rtl">

**هر دو ستونِ نسبت نزدیکِ `2` هستند — یعنی از نظرِ `Big-O` این دو ظرف در این کار برابرند.** و `linked list` ده‌ها برابر کندتر است.

**این نتیجهٔ اصلیِ فصل است و هیچ ستارهٔ کنارش نیست:** روی همان کاری که کتاب‌های درسی برای `linked list` مثال می‌زنند، در پایتون و در این بازهٔ `n`، **`linked list` می‌بازد.**

بیایید دقیق‌تر بگوییم کجا می‌بازد، چون «کندتر است» یک گزارشِ ناقص است.

</div>

```python
n = 160_000
values = sources[n]
head = linked_from(values)
t_reach = clock(lambda: middle_insert_linked(linked_from(values), n), repeat=2)
t_build = clock(lambda: linked_from(values), repeat=2)
t_list = clock(lambda: middle_insert_list(values), repeat=2)
print(f"n = {n:,} · {K} درج در وسط\n")
print(f"list.insert(وسط, x)              : {1000 * t_list:9.2f} ms")
print(f"linked list (با ساختنِ زنجیر)     : {1000 * t_reach:9.2f} ms")
print(f"  از آن، فقط ساختنِ زنجیر         : {1000 * t_build:9.2f} ms")
print(f"  پس خودِ {K} درج                 : {1000 * (t_reach - t_build):9.2f} ms")
print(f"\nنسبتِ درج‌ها به list             : {(t_reach - t_build) / t_list:9.1f} برابر")
print(f"هر درج در linked list            : "
      f"{1e6 * (t_reach - t_build) / K:9.1f} µs")
print(f"هر درج در list                   : {1e6 * t_list / K:9.1f} µs")
```

```text-approx
n = 160,000 · 200 درج در وسط

list.insert(وسط, x)              :     17.54 ms
linked list (با ساختنِ زنجیر)     :    407.45 ms
  از آن، فقط ساختنِ زنجیر         :     47.58 ms
  پس خودِ 200 درج                 :    359.87 ms

نسبتِ درج‌ها به list             :      20.5 برابر
هر درج در linked list            :    1799.3 µs
هر درج در list                   :      87.7 µs
```

<div dir="rtl">

**ده‌ها برابر، و کلِ اختلاف در «هزینهٔ رسیدن» است، نه در «هزینهٔ درج».**

خودِ درج در `linked list` واقعاً دو خط است. **ولی برای رسیدن به گرهٔ وسط، هشتاد هزار بار باید `node = node[NEXT]` اجرا شود** — هشتاد هزار پرشِ حافظه که هر کدام ممکن است جای کاملاً دیگری از حافظه باشد. `list` هم همان‌قدر خانه را لمس می‌کند، ولی این کار را با یک انتقالِ پیوسته انجام می‌دهد که سخت‌افزار برایش ساخته شده.

**ضریبِ فصلِ ۱ فقط بخشِ کوچکی از این فاصله است.** روی همین ماشین، هشتاد هزار قدم روی زنجیری که گره‌هایش به‌ترتیب ساخته شده‌اند به‌اندازهٔ یک حلقهٔ پایتونی روی همان تعداد خانهٔ `list` طول کشید، و با به‌هم‌ریختنِ جای گره‌ها در حافظه حدودِ دو و نیم برابر شد. **بیشترِ فاصله از جای دیگری می‌آید:** هر قدمِ زنجیر یک دورِ حلقهٔ پایتون است، و `insert` آن هشتاد هزار خانه را با یک انتقالِ یکجا در کدِ کامپایل‌شده جابه‌جا می‌کند.

> ⚠️ **مواظب باش:** این نتیجه **`n`ِ خودش را دارد**. ادعای ما این است: در پایتون، در بازهٔ ۲۰٬۰۰۰ تا ۱۶۰٬۰۰۰، برای درج در وسط. **در زبانی که گره‌ها را می‌شود پشتِ سرِ هم چید، یا وقتی همان ارجاع از قبل دستت است، جواب می‌تواند فرق کند.** ولی هیچ‌کدام از این‌ها مجوزِ نوشتنِ «`linked list` برای درج بهتر است» بدونِ جدول نیست.

## ۴. دو اندازه‌گیریِ دیگر، برای کامل شدنِ گزارش

</div>

```python
def linked_sum(head):
    total = 0
    node = head
    while node is not None:
        total += node[VALUE]
        node = node[NEXT]
    return total


def list_sum(values):
    total = 0
    for v in values:
        total += v
    return total


n = 160_000
head = linked_from(sources[n])
print("جوابِ دو نسخه یکی است؟", linked_sum(head) == list_sum(sources[n]))
t_l = clock(lambda: list_sum(sources[n]), repeat=3)
t_k = clock(lambda: linked_sum(head), repeat=3)
print(f"\nپیمایشِ کامل — list       : {1000 * t_l:7.2f} ms")
print(f"پیمایشِ کامل — linked list: {1000 * t_k:7.2f} ms   ({t_k / t_l:.2f} برابر)")

node_bytes = sys.getsizeof([0, None])
print(f"\nحافظهٔ خودِ ظرف — list       : {sys.getsizeof(sources[n]):>10,} بایت")
print(f"حافظهٔ گره‌ها — linked list  : {node_bytes * n:>10,} بایت"
      f"   ({node_bytes * n / sys.getsizeof(sources[n]):.1f} برابر)")
```

```text-approx
جوابِ دو نسخه یکی است؟ True

پیمایشِ کامل — list       :    4.45 ms
پیمایشِ کامل — linked list:    7.72 ms   (1.74 برابر)

حافظهٔ خودِ ظرف — list       :  1,280,056 بایت
حافظهٔ گره‌ها — linked list  : 11,520,000 بایت   (9.0 برابر)
```

<div dir="rtl">

**پیمایش کندتر است و حافظه چند برابر.** گرهٔ ما دو خانه دارد ولی هر گره خودش یک `list` کامل با سربارِ خودش است — و همان سربار در چند برابر شدنِ حافظه دیده می‌شود.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `linked list` دستی با `list` و `deque`، روی سه کارِ متفاوت، با خروجیِ برابرِ تأییدشده در هر سه. **در کدام بازهٔ `n`؟** ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ برای درج در ابتدا و ۲۰٬۰۰۰ تا ۱۶۰٬۰۰۰ برای درج در وسط و پیمایش. **با چند تکرار، و کمینه یا میانگین؟** دو یا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه — و در جدولِ تفکیکی، هزینهٔ ساختنِ زنجیر جدا اندازه گرفته و کم شد، چون بخشی از کارِ سنجیده‌شده نبود.

## ۵. پس `linked list` به چه دردی می‌خورد؟

سه جواب، و هر سه صادقانه:

1. **به‌عنوان یک ظرفِ عمومی در پایتون، به هیچ دردی.** `list` و `deque` تقریباً همیشه بهترند و کدشان به زبانِ سطحِ پایین‌تری نوشته شده.
2. **به‌عنوان یک ایدهٔ ساختاری، به دردِ خیلی چیزها.** ترمِ ۵ همین دوره درخت و گراف می‌سازد و هر دو **دقیقاً همین شکل‌اند**: گره‌هایی که با ارجاع به هم وصل شده‌اند. اگر این فصل را فهمیده باشی، آن‌جا هیچ چیزِ تازه‌ای در نحوهٔ ساخت نیست.
3. **به‌عنوان یک درسِ روش‌شناسی، به بهترین درد:** یک ساختار می‌تواند از نظرِ `Big-O` بهتر باشد و در عمل ببازد. **این دقیقاً همان چیزی است که فصلِ ۹ ترمِ ۱ با نقطهٔ تقاطع نشان داد، این بار بدونِ هیچ نقطهٔ تقاطعی** — چون در کلِ بازهٔ آزمایش‌شده، برنده عوض نشد.

> ✅ **چک کن:** `middle_insert_linked` را طوری تغییر بده که به‌جای وسط، **در ابتدا** درج کند (حلقهٔ رسیدن را کاملاً بردار). **زمانش باید به تقریباً صفر برسد و از `list` ببرد.** اگر نبرد، حلقهٔ رسیدن هنوز جایی مانده — و همان یک حلقه تفاوتِ برنده و بازنده است.

> 🔧 **اگر کار نکرد:** پرتکرارترین خطای کار با زنجیر این است که یک قدم زیادی جلو بروی:

</div>

```python
try:
    node = linked_from([1, 2, 3])
    for _ in range(4):
        node = node[NEXT]
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: 'NoneType' object is not subscriptable
```

<div dir="rtl">

`None` گرهٔ آخر است و خانه ندارد. **در `list` همین اشتباه `IndexError` می‌داد و می‌گفت اندیس بیرون از بازه است؛ در زنجیر پیام از نوعِ داده حرف می‌زند، نه از طول.** دلیلش این است که زنجیر اصلاً طولش را نمی‌داند — برای دانستنِ `len` باید کلِ زنجیر را بشمارد، که خودش `O(n)` است.

> 🤖 **از دستیارت بپرس:** «مزیتِ `linked list` نسبت به آرایه چیست؟» بعد **جدولِ بخشِ ۳ را جلویش بگذار و بپرس:** «پس چرا در این اندازه‌گیری `list` چهل برابر سریع‌تر است؟» — جوابِ درست باید دو چیز را از هم جدا کند: مرتبهٔ رشد، و ثابتی که از فاصلهٔ حلقهٔ پایتون با انتقالِ یکجا می‌آید و کمی هم از نزدیکیِ داده‌ها در حافظه.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| linked list | لینکد لیست | دنباله‌ای از گره‌ها که هر کدام ارجاعِ گرهٔ بعدی را دارد |
| node | نُود | یک عضوِ زنجیر: مقدار به‌علاوهٔ ارجاعِ بعدی |
| pointer chasing | پوینتر چیسینگ | رفتن از گره به گره با دنبال کردنِ ارجاع‌ها |
| negative result | نگتیو ریزالت | نتیجه‌ای که خلافِ انتظار درمی‌آید و باید کامل گزارش شود |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: درجِ `O(1)` در `linked list` چه چیزی را فرض می‌گیرد که در عمل معمولاً نداری؟

**تمرینِ اجباری:** تابعی بنویس که مقدارِ گرهٔ شمارهٔ `i` را از یک زنجیر برگرداند. حالا **همان آزمایشِ بخشِ ۱ فصلِ ۱ را تکرار کن**: خانهٔ اول، وسط و آخر را در چهار اندازهٔ دوبرابرشونده بخوان و برای هر سه یک جدول بگیر. **سؤالِ اصلی: ستونِ نسبتِ کدام جدول‌ها `1.00` است و کدام‌ها نه؟** جوابت را کنارِ جدول‌های فصلِ ۱ بگذار و در یک جمله بگو کدام خاصیتِ آرایه این‌جا از دست رفته.

**تمرینِ ستاره‌دار ⭐:** زنجیرِ ما فقط رو به جلو می‌رود. نسخه‌ای بساز که هر گره ارجاعِ گرهٔ **قبلی** را هم داشته باشد (سه خانه به‌جای دو). **قبل از هر اندازه‌گیری پیش‌بینی کن:** حافظه چند درصد بیشتر می‌شود، و آیا هزینهٔ درج در وسط کم می‌شود یا نه. بعد هر دو را اندازه بگیر. **اگر پیش‌بینیِ دومت غلط بود، بنویس چه چیزی را دربارهٔ «هزینهٔ رسیدن» جا انداخته بودی** — و اگر درست بود، بنویس این ساختارِ گران‌تر اصلاً به چه دردی می‌خورد.

## در فصل بعد

`deque` تا اینجا دو بار برنده شده و ما هنوز نگفته‌ایم چیست.

**فصلِ بعد دو انضباطِ کلاسیک را روی همان داده می‌گذارد:** `stack` که آخرین ورودی را اول برمی‌دارد، و `queue` که اولین ورودی را اول. یکی از این دو با `list` عالی کار می‌کند و دیگری با `list` یک فاجعهٔ درجه‌دو است — و همان‌جا با عدد می‌بینی که `popleft` در برابرِ `pop(0)` در `n = 80,000` چند ده برابر فاصله دارد.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s06-linked-list (یادستان, Yaadestan)
