مقدمه
ساختار دادهها (Data Structures) یکی از بنیادیترین مفاهیم در علوم کامپیوتر است. اگر برنامهنویسی را مثل آشپزی در نظر بگیریم، دادهها مواد اولیه و ساختار دادهها ظرفهایی هستند که این مواد را به بهینهترین شکل ممکن نگه میدارند تا دسترسی و پردازش آنها سریعتر انجام شود.
در این مقاله، به بررسی انواع ساختار دادهها، ویژگیها و کاربرد هر کدام میپردازیم.
چرا ساختار دادهها اهمیت دارند؟
نحوه سازماندهی دادهها تأثیر مستقیمی بر کارایی (Efficiency) برنامه دارد. دو فاکتور اصلی در ارزیابی یک ساختار داده عبارتند از:
- پیچیدگی زمانی (Time Complexity): عملیات مورد نظر چقدر سریع انجام میشود؟
- پیچیدگی فضایی (Space Complexity): این ساختار چقدر از حافظه RAM اشغال میکند؟
دستهبندی کلی ساختار دادهها
ساختار دادهها معمولاً به دو دسته اصلی تقسیم میشوند:
- خطی (Linear): دادهها به صورت متوالی پشت سر هم قرار میگیرند (مانند آرایه و لیست پیوندی).
- غیرخطی (Non-Linear): دادهها روابط پیچیدهتری دارند و به صورت سلسلهمراتبی یا شبکهای متصل میشوند (مانند درخت و گراف).
۱. ساختار دادههای خطی
آرایه (Array)
آرایه سادهترین و قدیمیترین ساختار داده است. در آرایه، عناصر از یک نوع داده (Data Type) در خانههای متوالی حافظه ذخیره میشوند.
- مزیت: دسترسی سریع به هر عنصر از طریق اندیس (Index).
- عیب: اندازه آن ثابت است (Static)؛ یعنی اگر بخواهید عضوی اضافه کنید که خارج از ظرفیت باشد، باید آرایه جدیدی بسازید.
لیست پیوندی (Linked List)
برخلاف آرایه، عناصر در لیست پیوندی در حافظه پخش هستند. هر عنصر (Node) شامل دو بخش است: خودِ داده و یک "اشارهگر" که به آدرس عنصر بعدی اشاره میکند.
- مزیت: اندازه آن پویا (Dynamic) است و حذف یا اضافه کردن گرهها آسان است.
- عیب: برای پیدا کردن یک عنصر، باید از ابتدا لیست را پیمایش کرد (دسترسی مستقیم وجود ندارد).
پشته (Stack)
پشته از قانون LIFO (آخرین ورودی، اولین خروجی) پیروی میکند. درست مثل ستونی از بشقابها که آخرین بشقابی که روی بقیه گذاشته شده، اولین بشقابی است که برداشته میشود.
- عملیات اصلی: Push (افزودن) و Pop (برداشتن).
صف (Queue)
صف از قانون FIFO (اولین ورودی، اولین خروجی) پیروی میکند. درست مثل صف نانوایی.
- کاربرد: در سیستمعاملها برای مدیریت فرآیندها و چاپگرها.
۲. ساختار دادههای غیرخطی
درخت (Tree)
درخت یک ساختار سلسلهمراتبی است. ریشه (Root) در بالاترین سطح قرار دارد و گرههای فرزند (Children) زیر آن قرار میگیرند.
- درخت جستجوی دودویی (Binary Search Tree): در این درخت، فرزند چپ همیشه کوچکتر از والد و فرزند راست بزرگتر از والد است. این ویژگی سرعت جستجو را فوقالعاده بالا میبرد.
گراف (Graph)
گراف مجموعهای از نقاط (Vertex) است که توسط یالها (Edge) به هم متصل شدهاند.
- کاربرد: مدلسازی شبکههای اجتماعی (دوستیها)، نقشههای مسیریابی (مثل Google Maps) و شبکههای اینترنت.
جدول هش (Hash Table)
این ساختار داده از یک تابع ریاضی به نام "هش" استفاده میکند تا هر کلید را به یک خانه مشخص در حافظه نگاشت کند.
- مزیت: سرعت جستجو، درج و حذف در حالت ایدهآل ثابت یا $O(1)$ است که سریعترین زمان ممکن محسوب میشود.
مقایسه کاربردی ساختار دادهها
| ساختار داده | دسترسی (Access) | جستجو (Search) | درج (Insertion) | کاربرد اصلی |
|---|---|---|---|---|
| آرایه | بسیار سریع | متوسط | کند | ذخیره لیستهای ثابت |
| لیست پیوندی | متوسط | متوسط | سریع | لیستهای با تغییرات زیاد |
| درخت جستجو | سریع | سریع | سریع | پایگاه دادهها |
| هش تیبل | بسیار سریع | بسیار سریع | بسیار سریع | دیکشنریها و کشینگ |
نتیجهگیری
انتخاب ساختار داده مناسب، تفاوت بین یک نرمافزار روان و یک نرمافزار کند را رقم میزند. برای مثال، اگر به دنبال سرعت در جستجو هستید، "جدول هش" یا "درختهای متوازن" بهترین گزینه هستند، اما اگر صرفاً میخواهید دادهها را به ترتیب ورود پردازش کنید، "صف" انتخاب بهتری است.