ساختارهای داده ابتدایی: پشته‌ها، صف‌ها، لیست‌های پیوندی، و درخت‌ها

چرا ساختارهای ابتدایی اهمیت دارند

هر ساختار داده پیشرفته‌ای که بعداً در این مجموعه پوشش داده می‌شود — جداول هش، درخت‌های متوازن، گراف‌ها — در نهایت از یک مجموعه کوچک از ساختارهای ابتدایی ساخته می‌شود: آرایه‌ها، لیست‌های پیوندی، و انتزاعات لایه‌شده روی آن‌ها. درک عمیق این پایه‌ها، شامل پیچیدگی زمانی دقیق‌شان برای هر عملیات، پیش از حرکت به هر چیز پیچیده‌تری ضروری است.

پشته‌ها: دسترسی آخرین-ورودی-اولین-خروجی

یک Stack (پشته) یک نوع داده انتزاعی است که درج و حذف را با پیروی از سیاست LIFO (Last-In, First-Out) پشتیبانی می‌کند: آخرین عنصر درج‌شده همیشه اولین عنصری است که حذف می‌شود. دو عملیات اصلی PUSH (درج) و POP (حذف و بازگرداندن اخیرترین عنصر) هستند.

STACK-EMPTY(S):
  top == 0 را برگردان

PUSH(S, x):
  top = top + 1
  S[top] = x

POP(S):
  اگر STACK-EMPTY(S):
      خطا "underflow"
  در غیر این صورت:
      top = top - 1
      S[top + 1] را برگردان

با پیاده‌سازی توسط یک آرایه و یک ایندکس ساده top، هر عملیات پشته در زمان O(1) اجرا می‌شود. پشته‌ها در سراسر علوم کامپیوتر ظاهر می‌شوند: مدیریت فراخوانی تابع (call stack)، ارزیابی عبارت، عملکرد undo در نرم‌افزار، و پیمایش جستجوی عمق‌اول، که بعداً در این مجموعه پوشش داده می‌شود.

صف‌ها: دسترسی اولین-ورودی-اولین-خروجی

یک Queue (صف) از انضباط مخالف، FIFO (First-In, First-Out)، پیروی می‌کند: زودترین عنصر درج‌شده اولین عنصری است که حذف می‌شود. دو عملیات اصلی ENQUEUE (درج در انتها) و DEQUEUE (حذف از ابتدا) هستند.

پیاده‌سازی کارآمد یک صف با یک آرایه با اندازه ثابت نیازمند یک رویکرد Circular Buffer (بافر دایره‌ای) است، با استفاده از ایندکس‌های جداگانه head و tail که در انتهای آرایه دور می‌زنند.

ENQUEUE(Q, x):
  Q[tail] = x
  اگر tail == Q.length:
      tail = 1
  در غیر این صورت:
      tail = tail + 1

DEQUEUE(Q):
  x = Q[head]
  اگر head == Q.length:
      head = 1
  در غیر این صورت:
      head = head + 1
  x را برگردان

مانند پشته‌ها، هر دو عملیات صف در زمان O(1) اجرا می‌شوند. صف‌ها برای جستجوی سطح‌اول که بعداً در این مجموعه پوشش داده می‌شود، زمان‌بندی وظیفه، و هر سناریویی که نیازمند پردازش به ترتیب دقیق رسیدن آیتم‌هاست ضروری هستند.

لیست‌های پیوندی: توالی‌های انعطاف‌پذیر مبتنی بر اشاره‌گر

برخلاف آرایه‌ها، که نیازمند حافظه پیوسته هستند و اندازه ثابتی دارند، یک Linked List (لیست پیوندی) عناصر را در گره‌های به‌طور جداگانه تخصیص‌یافته که با اشاره‌گرها متصل شده‌اند ذخیره می‌کند، که درج و حذف کارآمد را در هرجای توالی بدون جابه‌جایی سایر عناصر امکان‌پذیر می‌کند.

لیست‌های پیوندی تکی

هر گره در یک Singly Linked List (لیست پیوندی تکی) یک مقدار و یک اشاره‌گر به گره بعدی ذخیره می‌کند، با اشاره‌گر آخرین گره که به یک مقدار null خاص تنظیم شده است.

ساختار هر گره:
  key
  next  (اشاره‌گر به گره بعدی، یا NIL اگر آخرین باشد)

LIST-SEARCH(L, k):
  x = L.head
  تا زمانی که x ≠ NIL و x.key ≠ k:
      x = x.next
  x را برگردان

جستجو در بدترین‌حالت زمان O(n) می‌گیرد، چون ممکن است نیازمند پیمایش کل لیست باشد. درج در ابتدا زمان O(1) می‌گیرد، اما درج در یک موقعیت دلخواه نیازمند یافتن آن موقعیت ابتدا است، که در کل زمان O(n) می‌گیرد مگر اینکه یک اشاره‌گر مستقیم به مکان هدف از قبل در دسترس باشد.

لیست‌های پیوندی دوگانه

یک Doubly Linked List (لیست پیوندی دوگانه) یک اشاره‌گر دوم به هر گره اضافه می‌کند، که به گره قبلی و همچنین بعدی ارجاع می‌دهد. این اشاره‌گر اضافه، حذف را به‌طور قابل‌توجهی کارآمدتر می‌کند وقتی یک اشاره‌گر به خود گره از قبل در دسترس باشد.

ساختار هر گره:
  key
  next  (اشاره‌گر به گره بعدی)
  prev  (اشاره‌گر به گره قبلی)

LIST-DELETE(L, x):
  اگر x.prev ≠ NIL:
      x.prev.next = x.next
  در غیر این صورت:
      L.head = x.next
  اگر x.next ≠ NIL:
      x.next.prev = x.prev

با داشتن یک اشاره‌گر مستقیم به گره x، حذف در زمان O(1) اجرا می‌شود، چون نه گره قبلی و نه بعدی نیازی به مکان‌یابی با جستجو ندارند — آن‌ها مستقیماً از طریق اشاره‌گرهای خود x قابل‌دسترسی‌اند. این یک مزیت معنادار نسبت به لیست‌های پیوندی تکی است، جایی که حذف یک گره نیازمند یافتن اسلاف آن ابتدا با جستجو از ابتدا است.

یک ساده‌سازی عملی: نگهبان‌ها

بسیاری از پیاده‌سازی‌های لیست پیوندی از یک Sentinel (نگهبان) استفاده می‌کنند، یک گره ساختگی که یک عنصر واقعی را نشان نمی‌دهد اما با حذف بررسی‌های حالت‌خاص برای ابتدا و انتهای لیست، شرایط مرزی را ساده می‌کند. یک لیست پیوندی دوگانه دایره‌ای با یک نگهبان اجازه می‌دهد هر درج و حذف دقیقاً از همان کد استفاده کند، بدون بررسی اینکه آیا لیست خالی است یا آیا یک عملیات روی اولین یا آخرین عنصر واقعی تأثیر می‌گذارد.

نمایش درخت‌های ریشه‌دار

درخت‌ها به ساختارهای اشاره‌گر پیچیده‌تری نسبت به لیست‌های خطی نیاز دارند، چون هر گره ممکن است تعداد متغیری فرزند داشته باشد.

درخت‌های دودویی: حالت ساده

برای یک Binary Tree (درخت دودویی)، جایی که هر گره حداکثر دو فرزند دارد، نمایش ساده است: هر گره اشاره‌گرهایی به فرزند چپ، فرزند راست، و به‌طور اختیاری والدش ذخیره می‌کند.

ساختار هر گره:
  key
  p       (اشاره‌گر به والد، یا NIL برای ریشه)
  left    (اشاره‌گر به فرزند چپ، یا NIL)
  right   (اشاره‌گر به فرزند راست، یا NIL)

این نمایش به‌طور گسترده برای درخت‌های جستجوی دودویی و سایر ساختارهای درخت دودویی که بعداً در این مجموعه پوشش داده می‌شوند استفاده می‌شود.

درخت‌های با شاخه‌بندی نامحدود: فرزند-چپ، راهبر-راست

برای یک درخت عمومی، جایی که یک گره ممکن است هر تعداد فرزندی داشته باشد، ذخیره یک اشاره‌گر جداگانه برای هر فرزند ممکن غیرعملی است، چون تعداد فرزندان از قبل شناخته‌شده نیست و می‌تواند به‌طور گسترده بین گره‌ها متفاوت باشد. نمایش ظریف Left-Child, Right-Sibling (فرزند-چپ، راهبر-راست) این را با استفاده از فقط دو اشاره‌گر به‌ازای هر گره حل می‌کند، صرف‌نظر از اینکه آن گره واقعاً چند فرزند دارد.

ساختار هر گره:
  key
  p              (اشاره‌گر به والد)
  left-child     (اشاره‌گر به اولین/چپ‌ترین فرزند گره)
  right-sibling  (اشاره‌گر به راهبر بعدی گره در سمت راست)

هر گره فقط مستقیماً به چپ‌ترین فرزندش اشاره می‌کند؛ برای رسیدن به راهبرهای آن فرزند، الگوریتم اشاره‌گر right-sibling چپ‌ترین فرزند را به‌طور مکرر دنبال می‌کند، که به‌طور مؤثر یک درخت با شاخه‌بندی دلخواه را به‌عنوان یک نوع خاصی از درخت دودویی کدگذاری می‌کند.

مثال: یک گره با سه فرزند A، B، C

با استفاده از left-child/right-sibling:
node.left-child → A
A.right-sibling → B
B.right-sibling → C
C.right-sibling → NIL (راهبر دیگری نیست)

برای بازدید از همه فرزندان، از node.left-child شروع کن
و به‌طور مکرر اشاره‌گرهای right-sibling را دنبال کن

این نمایش به‌طور ظریفی درخت‌های با فاکتور شاخه‌بندی دلخواه و متغیر را با استفاده از مقدار ثابتی حافظه به‌ازای هر گره، دقیقاً دو اشاره‌گر، مدیریت می‌کند، صرف‌نظر از اینکه هر گره واقعاً چند فرزند دارد.

چرا تسلط بر این ساختارها اهمیت دارد

هر ساختار داده‌ای که بعداً در این مجموعه بحث می‌شود — جداول هش که از لیست‌های پیوندی برای مدیریت برخوردها استفاده می‌کنند، درخت‌های جستجوی دودویی که از ساختار گره مبتنی بر اشاره‌گر معرفی‌شده در اینجا استفاده می‌کنند، و حتی نمایش‌های گراف که از لیست‌های مجاورت استفاده می‌کنند — مستقیماً روی این ساختارهای ابتدایی و پیچیدگی‌های زمانی مرتبط‌شان بنا می‌شود. یک درک محکم و شهودی از دقیقاً چگونگی و چرایی دستیابی هر عملیات ابتدایی به زمان اجرای بیان‌شده‌اش، پایه‌ای برای استدلال درست درباره هر ساختار پیشرفته‌تری است که در ادامه می‌آید.