8 ساختار داده که هر برنامه نویسی باید بداند! (قسمت اول)

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

          ساختار داده ها در اکثر زبان های برنامه نویسی استفاده و پیاده سازی شده است. از طرفی ساختار داده یک مفهوم بنیادی در علوم کامپیوتر است که می توان بسیاری از آن ها را در هر زبانی پیاده سازی کرد (اگر به صورت پیش فرض در زبانی پیاده سازی نشده باشد). همچنین این مفهوم در مصاحبه های مهندسی نرم افزار یک مفهوم بسیار مهم و کلیدی است و در بسیاری از مصاحبه ها از آن یاد می شود (یکی از تفاوت های برنامه نویس خوب با دیگران درک بهتر و آشنایی بیشتر با ساختار داده هاست!). بنابراین به عنوان یک برنامه نویس، بهتر است با این مفاهیم آشنا باشید. در این مقاله سعی شده است تا 8 ساختار داده پر کاربرد در علوم کامپیوتر معرفی شود. 

1 – آرایه ها (Arrays)

          آرایه یک ساختار داده با اندازه ثابت و مشخص است که می تواند لیستی از داده ها را که همگی از یک نوع هستند در بر گیرد. به عنوان مثال آرایه می تواند لیست 5 تایی از اعداد صحیح (integer) یا لیست 3 تایی از رشته (string) باشد. همچنین آرایه می تواند لیستی از آرایه ها باشد که به آن آرایه دو بعدی گفته می شود. به هر یک از اعضای آرایه یک المان (element) گفته می شود. آرایه ها index گذاری می شوند. این به آن معنا است که می توان به هر المان دسترسی مستقیم داشت. index ها از شماره صفر شروع می شوند.

عملیات های آرایه:

• پیمایش (Traverse): می توان روی خانه های آرایه پیمایش انجام داد و عملیات های دیگری (مثل print) انجام داد.
• جستجو (Search): می توان یک المان را در یک آرایه جستجو کرد. این جستجو می تواند بر اساس مقدار المان یا index آن باشد.
• به روز رسانی (Update): می توان مقدار یک المان را بر اساس index آن در آرایه به روز رسانی کرد.

نکته: شاید برایتان سوال باشد عملیات افزودن (insert) یا حذف (delete) در لیست عملیات های مربوط به آرایه کجاست؟ باید بگویم در واقع یکی از خواص آرایه ها ثابت بودن اندازه آن هاست. از این رو نمی توان یک المان جدید به آرایه اضافه (یا حذف) کرد. بنابراین برای اضافه کردن المان جدید باید ابتدا یک آرایه جدید با اندازه جدید (اندازه آرایه قبلی + 1) ساخته شود. سپس تمامی المان های آرایه قبل به آن اضافه شده و در نهایت المان جدید را به آن اضافه کرد. البته قابل ذکر است که در بیشتر زبان های سطح بالا (مثل python یا node.js) این قابلیت به صورت پیشفرض پیاده سازی شده است و نیاز به انجام این عملیات ها به صورت دستی نیست (اگر قرار بود دستی انجام شود به نظرم زندگی تباه می شد!)

مثال های کاربردی استفاده از آرایه:

• آرایه ها ساختار داده پایه برای ایجاد دیگر ساختار داده های پیچیده از علوم کامپیوتر مثل لیست ها، پشته ها، hash table ها و ... هستند.
• استفاده برای الگوریتم های مرتب سازی مختلف (مثل insertion sort، quick sort، bubble sort و merge sort).

2 – لیست های پیوندی (Linked List)

          لیست پیوندی یک ساختار داده دارای توالی است که از تعدادی المان پشت سر هم و وابسته تشکیل شده و این المان ها به صورت خطی به یکدیگر متصل شده اند. این به این معنی است که هر المان با المان بعد و قبل از خود متصل است. بنابراین برای دسترسی به المان ها نمی توان به صورت تصادفی و مستقیم (با استفاده از index) به آن ها دسترسی داشت و برای دسترسی به یک المان باید المان های قبل از آن را پیمایش کرد. در یک لیست پیوندی:

• المان های لیست با عنوان node شناخته می شوند.
• هر node دارای یک کلید (key) و یک اشاره گر (pointer) است. کلید مقدار node و اشاره گر آدرس، node بعدی را مشخص می کند. اشاره گر با عنوان next شناخته می شود.
• لیست پیوندی دارای یک node خاص است که اولین node لیست است. هیچ node ی به این node اشاره نمی کند.
• آخرین node یک لیست پیوندی با نام tail شناخته می شود. این node دارای اشاره گر نیست.

          لیست پیوندی دارای انواع مختلفی است:

• لیست پیوندی یک طرفه: در این نوع پیمایش node ها فقط از اول به آخر امکان پذیر است و نمی توان از یک node به node قبلی دسترسی پیدا کرد.
• لیست پیوندی دو طرفه: در این نوع، پیمایش دو طرفه امکان پذیر است. این نوع علاوه بر next دارای یک مقدار خاص دیگر با عنوان prev است که آدرس node قبلی را مشخص می کند.
• لیست پیوندی حلقوی: در این نوع لیست پیوندی، المان head دارای یک prev بوده و به آخرین node لیست اشاره می کند. همچنین آخرین node نیز دارای next بوده و به اولین node لیست اشاره می کند.

عملیات های لیست پیوندی:

• جستجو: پیدا کردن یک المان با کلید key که با پیمایش لیست امکان پذیر است.
• افزودن: افزودن یک node جدید به لیست به سه روش مختلف ممکن است اتفاق بیفتد: افزودن به انتهای لیست ، افزودن به ابتدای لیست و افزودن در میانه لیست. باید دقت کرد که در هر یک از این روش ها، بایستی به نحوه تغییر اشاره گرها (به خصوص افزودن در میانه لیست) نیز توجه شود.
• حذف: حذف یک node نیز همچون افزودن آن به سه روش حذف از انتها، حذف از ابتدا و حذف از میانه ممکن است.

مثال های کاربردی استفاده از لیست پیوندی:

• استفاده به عنوان مدیریت symbol ها در طراحی compiler ها
• استفاده به عنوان جا به جایی بین برنامه های کاربری (ALT + TAB). در این مثال از لیست پیوندی حلقوی استفاده شده است.
• پیاده سازی انواع blockchain که پایه و اساس ساختار بسیاری از رمزارزهاست (cryptocurrency).

3 – پشته (Stack):

          پشته یک ساختار داده، LIFO (یا Last In First Out) است. در این نوع ساختار داده ها آخرین ورودی به ساختار داده، اولین خروجی ساختار داده خواهد بود. برای درک بهتر فرض کنید درون یک جعبه یک پشته از بشقاب ها را روی هم می گذارید! سپس برای خارج کردن بشقاب ها از جعبه باید ابتدا آخرین بشقاب گذاشته شده در جعبه را خارج کنید. در علوم کامپیوتر و زبان های برنامه نویسی مختلف از پشته استفاده های زیادی می شود.

عملیات های پشته:

• Push: برای افزودن یک المان به انتهای پشته از push استفاده می شود.
• Pop: برای حذف یک المان از انتهای پشته از عنوان pop استفاده می شود. این عملیات آخرین المان پشته را از پشته حذف و به عنوان نتیجه بر می گرداند.

همچنین پشته دارای سه عملیات جانبی دیگر برای مدیریت و دسترسی بهتر دارد:

• Peek: آخرین المان آرایه را بدون حذف از پشته بر میگرداند.
• isEmpty: بررسی می کند آیا پشته خالی است یا خیر.
• isFull: بررسی می کند آیا پشته پر است یا خیر.

مثال های کاربردی استفاده از پشته:

• استفاده به عنوان history در مرورگرها
• پیاده سازی function calls در برنامه نویسی بازگشتی

4 – صف (Queue):

          صف یک ساختار داده FIFO (First In First Out) است. در این نوع ساختار داده ها، اولین المان وارد شده به ساختار، اولین المان خروجی از آن ساختار است. برای درک بهتر یک صف نانوایی را در نظر بگیرید! در این صف اولین فردی که در صف قرار دارد، اولین فردی است که نان دریافت می کند (اگر کسی بد نوبتی نکند!). از صف ها در زبان های برنامه نویسی استفاده بسیاری می شود.

عملیات های صف:

• EnQueue: برای افزودن المان جدید به انتهای پشته از EnQueue استفاده می شود.
• DeQueue: برای حذف المان از ابتدای پشته از DeQueue استفاده می شود. این عملیات اولین المان صف را از صف حذف و به عنوان نتیجه بر می گرداند.

مثال های کاربردی استفاده از صف:

• مدیریت thread ها در ساختار multi-threading
• استفاده برای پیاده سازی سیستم های صف محور (queueing systems)

در قسمت بعدی این مقاله، 4 مورد دیگر از ساختار داده معرفی خواهد شد.