همان اندازه که انتخاب الگوریتم در سرعت نرم افزار اهمیت دارد، انتخاب ساختار داده مناسب هم اهمیت دارد، انتخاب ساختار داده اشتباه میتواند نرم افزار ما را به شدت کند و ناکارآمد کند. در این مقاله با دو ساختار داده پر کاربرد آشنا میشویم ؛ آرایه و لیست پیوندی. مقایسه این دو نمونه به ما کمک میکند تا در نرم افزارمان از گزینه مناسب نیازمان استفاده کنیم. در این مطلب از علامت Big O برای نشان دادن سرعت الگوریتم ها استفاده میکنیم، در صورتی که با این مفهوم آشنایی ندارید پیشنهاد میکنم این مقاله را اول بخوانید.
یک کمد بایگانی را تصور کنید، هر قفسه از آن فقط میتواند یک شیء را در خود جا دهد، بنابراین در صورتی که شما بخواهید دو چیز مختلف در آن ذخیره کنید نیاز به دو قفسه خواهید داشت. این دقیقا طرز کار حافظه کامپیوتر شماست، حافظه کامپیوتر مانند یک کمد بایگانی بسیار بزرگ است، هر زمان که ما بخواهیم داده ای در حافظه نگه داریم، داده ما در یکی از قفسه ها قرار میگیرد و آدرس آن به ما داده میشود.
اما اگر بخواهیم مجموعه ای از داده ها را ذخیره کنیم چطور؟ برای این کار دو ساختار داده ساده وجود دارد؛ آرایه و لیست پیوندی.
اگر ما بخواهیم داده های خودمان را در یک آرایه قرار بدهیم به این معناست که همه داده های ما در حافظه کامپیوتر پشت سر هم قرار گرفته اند، به مثال کمد بایگانی توجه کنید؛ اگر ما بخواهیم که 10 شیء را به صورت آرایه نگهداری کنیم باید ده قفسه پشت سر هم برای این کار در نظر بگیریم، گاهی اوقات بهتر است که تعداد بیشتری از نیازمان در نظر بگیریم تا در صورت لزوم بتوانیم شیء یازدهم را به آن اضافه کنیم، برای مثال میتوانیم 15 قفسه را رزرو کنیم اما باز هم اگر تعداد اشیائی که میخواهیم نگهداری کنیم بیشتر شود، احتمالا باید کل آرایه را جابجا کنیم و در کمد بایگانی دنبال جایی بگردیم که حداقل شانزده جای خالی پشت سر هم داشته باشد. این کار به نظر پر زحمت می آید، درست است؟ در این موارد میتوانیم به جای آرایه از لیست پیوندی استفاده کنیم.
در لیست پیوندی شما میتواند هر آیتم را در هر جایی از حافظه قرار دهید، اما باید جایگاه آیتم بعدی را هم در کنار آن آیتم قرار بدهید، در واقع لیست پیوندی مجموعه ای از داده هاست که به صورت پراکنده در حافظه ذخیره شده اند اما هر کدام به وسیله داشتن آدرس بعدی در حافظه به آن متصل شده است. برای پیدا کردن یک آیتم در لیست پیوندی باید به سراغ آیتم اول برویم، در آنجا آدرس آیتم دوم وجود دارد، بعد از آیتم دوم به سراغ آیتم سوم و بعد چهارم میرویم و همین روند را ادامه میدهیم تا آیتم مورد نظر خودمان را پیدا کنیم. اضافه کردن یک آیتم به لیست پیوندی بسیار ساده است. کافیست آیتم جدید را در هر جایی از حافظه ذخیره کنیم و آدرس آن را به آیتم قبلی بدهیم.
فرض کنید میخواهید با سه نفر از دوستان خود به سینما بروید، بعد از کمی جستجو سه صندلی پشت سرهم پیدا میکنید و مینشینید، کمی بعد یکی دیگر از دوستان تان با شما تماس میگیرد و میگوید که میخواهد به شما ملحق شود اما صندلی بعدی خالی نیست، در نتیجه بلند میشوید و به دنبال جایی میگردید که چهار صندلی خالی وجود داشته باشد. این طرز کار یک آرایه است به دلیل اینکه در آرایه لازم است همه آیتم ها پشت سر هم باشند، در صورتی که تعداد آیتم ها از چیزی که شما در نظر گرفتید بیشتر شود باید همه آیتم ها را جابجا کنید و طبیعتا این کار زمان زیادی خواهد برد.
اما درباره لیست پیوندی این مسئله وجود ندارد، چون هر آیتمی میتواند در هر جایی از حافظه ذخیره شود، مانند اینکه با ده نفر از دوستان تان به سینما بروید و بجای اینکه دنبال جایی بگردید که ده صندلی خالی داشته باشد، پراکنده شوید و هر کدام یک صندلی خالی برای نشستن پیدا کنید.
بعد از اینکه با این دو ساختار داده آشنا شدیم، حالا باید به این سوال جواب بدهیم که از کدام یک باید استفاده کنیم؟ در حقیقت یک جواب قطعی برای این سوال وجود ندارد. با توجه به نیاز نرم افزار در هر موردی باید از ساختار داده مناسب استفاده کنیم. در ادامه لیست پیوندی و آرایه را از جهت سرعت و بازدهی در موقعیت های مختلف مقایسه میکنیم.
فرض کنید ما میخواهیم آیتم 100 ام از یک آرایه را بخوانیم، کار بسیار راحتی خواهد بود کافی است از آدرس آیتم اول، نود و نه خانه به جلو برویم. پس عملا ما با یک عملیات آیتم صدم را پیدا میکنیم، بنابراین پیچیدگی زمانی آن، O(1) خواهد بود.
اما درباره لیست پیوندی، قضیه متفاوت خواهد بود، برای پیدا کردن آیتم صدم در لیست پیوندی ابتدا باید آیتم یک را پیدا کنیم سپس آدرس آیتم دوم را در آنجا پیدا کنیم، بعد آیتم سوم و چهارم و… همین روند را ادامه بدهیم تا بالاخره به آیتم صدم برسیم. به عبارتی باید خانه ها را یکی یکی به جلو بیاییم پس پیچیدگی زمانی پیدا کردن آیتم در لیست پیوندی به صورت O(n) خواهد بود.
به نظر میرسد اضافه کردن دیتا به آرایه کار راحتی است، کافیست بعد از آخرین آیتم، یک آیتم جدید قرار دهیم. اما مسئله، زمانی پیچیده میشود که بخواهیم به اول یا اواسط یک آرایه آیتم جدید اضافه کنیم، در این صورت لازم داریم که تمام آیتم های بعدی را به یک خانه جلوتر منتقل کنیم. برای مثال اگر ما یک آرایه داشته باشیم که در حال حاضر ده عضو داشته باشد و بخواهیم به اول آن یک آیتم جدید اضافه کنیم باید آیتم یک را ببریم بجای آیتم دو و آیتم دو بجای آیتم سه ببریم و همین روند را ادامه دهیم تا همه آیتم ها یک خانه جابجا شوند و بتوانیم آیتم جدید را در خانه اول بگذاریم. اضافه کردن به میانه آرایه هم فرایند مشابهی دارد.
همین روند برای حذف کردن دیتا هم وجود دارد. باید تمام آیتم های بعد از آیتم حذف شده، یک خانه به عقب برگردند. برای حذف و اضافه کردن در آرایه، ممکن است نیاز پیدا کنیم تا همه آیتم ها را جابجا کنیم، پس میتوانیم بگوییم که پیچیدگی زمانی این فرایند به صورت O(n) خواهد بود.
اما درباره لیست پیوندی چطور؟ اضافه کردن در لیست پیوندی بسیار ساده است، آیتم جدید را در هر جایی از حافظه که بخواهیم قرار میدهیم و آدرس آن را در آیتم قبلی قرار میدهیم. فرض کنیم که یه لیست پیوندی با 10 آیتم داریم و میخواهیم آیتم جدیدی بین آیتم 3 و 4 اضافه کنیم. کافیست آیتم جدید را در جایی از حافظه قرار دهیم و آدرس آن را به آیتم 3 بدهیم و آدرس آیتم 4 را به آیتم جدید بدهیم. بدون اینکه نیاز به جابجایی دیتا های قبلی وجود داشته باشد.
حذف کردن از لیست پیوندی نیز کار راحتی خواهد بود، کافییست آیتم مورد نظر را از حافظه حذف کنیم و آدرس آیتم بعدی را به آیتم قبلی بدهیم. اضافه و حذف کردن در لیست پیوندی با یک عملیات انجام خواهد شد پس پیچیدگی زمانی آن به صورت O(1) خواهد بود.
آرایه و لیست پیوندی، دو تا از مهم ترین ساختار های داده هستند که وقتی با مجموعه ای از داده ها کار داشته باشیم، باید سراغ آنها برویم.
اینکه سراغ کدام یک برویم بستگی به نیاز ما دارد. اگر قرار است که مجموعه ای داشته باشیم که مدام به آن اضافه یا از آن حذف کنیم، بهتر است از لیست پیوندی استفاده کنیم. برای مثال اگر بخواهیم یک نرم افزار todo list بنویسیم که کار هایمان را در آن قرار دهیم بهتر است از لیست پیوندی استفاده کنیم چون مدام نیاز داریم میان کارهای قبلی، کار جدیدی اضافه کنیم و کار هایی که انجام میدهیم را از لیست حذف کنیم.
اما اگر مجموعه داده های ما تغییرات زیادی ندارد و ما نیاز داریم که مدام از میانه آن آیتم های مان را بخوانیم بهتر است از آرایه کمک بگیریم، برای مثال اگر بخواهیم یک نرم افزار دیکشنری بنویسیم بهتر است از آرایه برای نگهداری لغات استفاده کنیم به دلیل اینکه لغات دیکشنری معمولا کم و زیاد نمیشود اما در عوض همیشه نیاز داریم که کلمه مورد نظرمان را بین کلمات پیدا کنیم.
در آخر این نکته را یادآوری کنم که مثال ها، جنبه آموزشی دارند و در ادامه که بیشتر با ساختار های داده آشنا میشویم، میفهمیم که راه حل های بهتری هم برای این مسائل وجود دارد.
اگر این مطلب برایتان مفید بود، پیشنهاد میکنم سری مقالات الگوریتم و ساختمان داده را دنبال کنید.
خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.
منبع : سری مقالات الگوریتم و ساختمان داده از سایت خودم
