ساختمان داده آرایه و لیست پیوندی:
۱- آرایه ساختمان داده ای است که شامل مجموعه ای از عناصر با نوع داده یکسان می باشد
2- لیست پیوندی ساختمان داده ای است شامل مجموعه ای از ارتباط های نامنظم بین المنت ها (که به آنها گره می گویند) که در آن نوع داده مهم نیست (لازم نیست تمام المنت ها از یک نوع داده باشند)
3- در آرایه برای دسترسی به عناصر، ایندکس آن عنصر را در براکت میگذاریم و به این ترتیب به داده نوردنظر دسترسی پیدا میکنیم
4- در لیست پیوندی برای دسترسی به یک المنت باید از المنت headشروع کرده و به ترتیب لیست را پیمایش کنیم تا به المنت مورد نظر برسیم
5- دسترسی به یک عنصر از آرایه سریع انجام می شود ولی در لیست پیوندی سرعت دسترسی به المنت مورد نظر مقداری کند تر است
6- عملیات هایی مانند اضافه کرد یا حذف کردن در آرایه زمان زیادی رد با خود اختصاص می دهد ولی در لیست پیوندی این کار خیلی سریل انجام می شود
7- سایز آرایه ثابت است ( در Array List سایز آرایه داینامیک است) ولی در لیست پیوندی سایز لیست دینامیک است و می توان لیست را توسعه داد یا کوچک تر کرد
8- در آرایه حافظه در زمان کامپایل اختصاص داده می شود ولی در لیست پیوندی حافظه در طول اجرا یا زمان اجرا اختصاص داده می شود
9- در آرایه عناصر بصورت متوالی ذخیره می شوند ولی در لیست پیوندی عناصر بصورت رندم ذخیره می شوند
10- آرایه حافظه کمتری را به خود اختصاص می دهد (شامل ایندکس و مقدار) ولی لیست پیوندی به حافظه بیشتری نیاز دارد (شامل اشاره گر عقب، مقدار، اشاره گر جلو)
11- استفاده آرایه از حافظه ناکارآمد است ولی لیست پیوندی بصورت کارآمد از حافظه استفاده می کند
نقاط قوت لیست پیوندی:
1- سایز آرایه ثابت است بنابراین ما باید حداکثر تعداد عنصری که قراره در آرایه ذخیره شود را بدانیم و همچنین مقدار حافظه ای که به آرایه اختصاص داده می شود برابر طول آرایه می باشد بنابر این در حالتی که آرایه کامل پر نشود حافظه هدر می رود ولی در لیست پیوندی ما قابلیت گسترش دادن لیست را داریم
2- اضافه کردن یک عنصر به آرایه هزینه زیادی دارد. به عنوان مثال اگر ما هر خانه از آرایه را یک مربع فرض کنیم در اینصورت برای اضافه کردن یک عنصر جدید به وسط آرایه لازم است بقیه خانه های آرایه جابجا شوند و بالعکس برای حذف یک خانه از آرایه نیاز است که بقیه خانه ها جابجا شوند
بطور خلاصه میتوان گفت لیست پیوندی دو مزییت زیر را دارد:
1- داینامیک بودن سایز
2- راحتی افزودن یا حذف کردن عنصر
معایب لیست پیوندی:
۱- نمیتوانیم بصورت مستقیم به عنصر موردنظر مان دسترسی داشته باشیم، برای دسترسی به عنصر موردنظر باید از گره اول شروع کنیم و لیست را پیمایش کنیم تا به عنصر موردنظر برسیم
بنابراین امکان جستجوی دودویی در لیست پیوندی وجود ندارد
2- لیست پیوندی حافظه بیشتری نسب به آرایه اشغال می کند
3- آرایه قابلیت کش شدن بهتری نسبت به لیست پیوندی دارد که باعث ایجاد یک تفاوت بزرگ در کارایی آرایه و لیست پیوندی می شود.
صفحه اینستاگرام ما را دنبال کنید:
درباره این سایت