ساختمان داده بخش مهمی در توسعهی نرمافزار و یکی از متداولترین مباحث مربوط به سوالات مصاحبه شغلی توسعهدهندگان است. ساختمان داده در واقع تنها قالب یا فرمتهای تخصصی برای سازماندهی و ذخیرهی دادهها هستند. در این مطلب ساختمان دادههای متداول را بررسی خواهیم کرد.
Linked List یکی از پایهای ترین ساختمان دادهها است که اغلب با آرایهها مقایسه میشود. چرا که بسیاری از ساختمان دادههای دیگر را میتوان با استفاده از آرایهها یا Linked List پیادهسازی کرد که هرکدام مزایا و معایب خود را دارند.
Linked List متشکل از گروهی از گرهها است که با هم یک دنباله را نشان میدهند. هر گره شامل دو نوع اطلاعات است: یکی داده اصلی که قرار است ذخیره شود و از هر نوعی میتواند باشد و یک اشارهگر یا لینک به گره بعدی در لیست.
همچین لیستهای پیوندی دو طرفه داریم که دو اشارهگر که یکی به گره قبلی و دیگری به گره بعدی در لیست اشاره میکنند، دارد.
مهمترین فرآیندها در لیست پیوندی شامل افزودن آیتم جدید به لیست، حذف آیتم از لیست و جستجوی یک آیتم در لیست میباشد.
Stack نوعی ساختمان داده است که تنها میتوانیم آیتم جدید به بالای آن اضافه یا آیتمی را از بالای آن حذف کنیم. Stackها خاصیت Last In First Out دارند. به این معنی که آیتمی که در آخر به لیست اضافه میشود، اولین آیتمی است که میتوان از آن خارج کرد.
سه فرآیند اصلی را میتوان روی Stack انجام داد: افزودن یک آیتم به لیست، حذف یک آیتم از لیست و نمایش محتوای لیست.
ساختمان داده Queue مشابه صف عادی در یک فروشگاه مواد غذایی است. اولین نفری که در صف قرار دارد اولین کسی است که سرویس میگیرد.
Queue خاصیت First In First Out دارد که نحوه دستیابی به اطلاعات آن را مشخص میکند. به این معنی که زمانی که یک المنت جدید به Queue اضافه میشود، برای حذف کردن آن از Queue لازم است تمام المنتهایی که قبل از آن وارد شدهاند را حذف کنیم.
Queue دو فرآیند مهم را پشتیبانی میکند:
Enqueue: به معنای اضافه کردن آیتم به انتهای صف است.
Dequeue: به معنای حذف آیتم موجود در ابتدای صف است.
ساختمان داده Set بدون هیچ ترتیب مشخصی مقادیر را ذخیره میکند. به طوری که مقدار تکراری در آن وجود ندارد. علاوه بر توانایی افزودن و حذف کردن المنتها از یک Set، توابع مهم دیگری نیز وجود دارند که برای انجام فرآیند هم زمان روی دو مجموعه استفاده میشوند.
Union: فرآیندی است که آیتمهای دو مجموعه مختلف را با هم در یک مجموعه جدید قرار داده و برمیگرداند. بدون اینکه آیتم تکراری در مجموعه ایجاد شود.
Intersection: این تابع دو مجموعه را به عنوان ورودی در نظر گرفته و یک مجموعه جدید متشکل از آیتمهایی را که در هر دو مجموعه داده شده وجود دارند، بر میگرداند.
Difference: این تابع لیستی از آیتمهایی را برمیگرداند که در یک مجموعه وجود دارند اما در مجموعه دیگر نیستند.
Subset: این تابع یک مقدار True یا False برمیگرداند که نشان میدهد آیا تمام المنت های یک مجموعه در یک مجموعه دیگر وجود دارند یا نه.
Map ساختمان دادهای است که داده را به صورت مقادیر Key و Value ذخیره میکند. به طوری که Key یک مقدار منحصر بفرد است. Mapها امکان انجام دادن فرآیندهای زیر را برای ما فراهم میکنند:
Hash Table یک ساختمان داده از نوع Map است که شامل Key – Value میباشد. از یک تابع Hash یا درهمساز برای محاسبه Index آرایه که مقدار مورد نظر در آن قرار گرفته، استفاده میکند.
تابع Hash معمولا یک رشته به عنوان ورودی گرفته و خروجی آن یک مقدار عددی است. این تابع همواره خروجی یکسانی برای ورودی یکسان تولید میکند. زمانی که این تابع برای دو ورودی متفاوت، مقدار خروجی عددی یکسانی تولید کند، گفته میشود که تصادم یا Collision اتفاق افتاده است.
بنابراین زمانی که یک Key – Value را به عنوان ورودی به یک تابع Hash بدهیم، فرآیندی روی Key اعمال شده و یک مقدار عددی به ما میدهد. این مقدار عددی اغلب به عنوان کلید واقعی برای مقداری که ذخیره شده استفاده میشود.
زمانی که بخواهیم به آن کلید دسترسی داشته باشیم، تابع Hash فرآیندی روی کلید انجام داده و نتیجه عددی یکسانی برمیگرداند. سپس از این عدد برای جستجوی مقدار Value مرتبط استفاده میشود.
[button class=”github-btn” href=”https://youtu.be/DcHZrqgEz-Q”]یک ساعت از دوره ساختمان داده و الگوریتمها در جاوااسکریپت[/button]
دیدگاهها: