Array List
توضیحات جلسه
جزوه و مستندات
مفاهیم کلیدی
ArrayList
یک ساختار داده در جاوا است که پیادهسازی اینترفیس List محسوب میشود و بر پایه آرایهها یا Array ساخته شده است. این ساختار اجازه میدهد لیستی از اشیا را بهصورت پویا ذخیره کنید.
Dynamic Array
آرایهای است که قابلیت تغییر سایز دارد. برخلاف آرایههای معمولی که طول ثابت دارند، ArrayList در صورت پر شدن، بهصورت خودکار یک آرایه بزرگتر، معمولاً دو برابر، ایجاد میکند و عناصر را به آن منتقل میکند.
Ordered Sequence
یعنی ArrayList ترتیب ورود عناصر را حفظ میکند و هر عنصر بر اساس زمان اضافه شدن، یک ایندکس مشخص دارد.
Duplicate Elements
قابلیتی است که اجازه میدهد مقادیر تکراری در لیست ذخیره شوند. برای مثال، عدد 5 میتواند چندین بار در یک لیست قرار بگیرد.
Generics
قابلیتی در جاوا است که اجازه میدهد نوع دادههای ذخیرهشده در ArrayList را مشخص کنید؛ برای مثال ArrayList<String>. این کار باعث امنیت تایپی یا Type Safety میشود و نیاز به Cast کردن را از بین میبرد.
Zero-based Indexing
یعنی مانند آرایههای استاندارد، شمارهگذاری خانهها در ArrayList از صفر شروع میشود.
موارد مصاحبه ای
چرا دسترسی تصادفی Random Access در ArrayList دارای مرتبه زمانی O(1) است؟
چون ArrayList در لایه زیرین از آرایه استفاده میکند. با داشتن ایندکس، میتوان مستقیماً به آدرس حافظه آن خانه دسترسی پیدا کرد و این زمان مستقل از حجم لیست است.
در چه شرایطی عملیات add دارای مرتبه زمانی O(n) میشود؟
در حالت عادی، اضافه کردن به انتهای لیست O(1) است. اما اگر ظرفیت آرایه پر شده باشد، سیستم باید یک آرایه جدید بسازد و تمام عناصر قبلی را در آن کپی کند. این فرایند به تعداد عناصر، یعنی n، زمان میبرد.
چرا حذف Delete یا درج Insert در میانه لیست O(n) است؟
زیرا با حذف یا درج یک عنصر در وسط لیست، تمام عناصر بعد از آن ایندکس باید یک واحد به جلو یا عقب جابهجا شوند. به این جابهجایی Shift گفته میشود.
تفاوت جستجو در لیست مرتب Sorted و نامرتب Unsorted چیست؟
در لیست نامرتب باید تمام عناصر را یکییکی بررسی کرد که مرتبه زمانی آن O(n) است. اما در لیست مرتب میتوان از Binary Search استفاده کرد که با هر مقایسه، نیمی از دادهها را کنار میگذارد و مرتبه زمانی بهتری دارد؛ یعنی O(log n).
چرا بهتر است از اینترفیس List در سمت چپ تعریف متغیر استفاده کنیم؟
برای مثال:
List<String> list = new ArrayList<>();
این کار یک Best Practice است؛ زیرا کد را منعطف میکند و شما را به یک پیادهسازی خاص محدود نمیکند. بنابراین بعداً میتوانید نوع لیست را راحتتر تغییر دهید.
سناریو کاربردی
در ویدیو، سناریوی مدیریت یک لیست از رشتهها یا String بررسی شد. ابتدا یک ArrayList ساخته شد و عناصری مانند "A"، "B" و "C" به آن اضافه شدند.
سپس مدرس نشان داد که چگونه میتوان با استفاده از متد add(index, value) یک عنصر جدید مانند "A1" را دقیقاً در ایندکس 1، یعنی بین "A" و "B"، اضافه کرد. در این مرحله توضیح داده شد که برای باز شدن جا برای "A1"، عناصر بعدی در حافظه جابهجا میشوند.
همچنین در سناریوی حذف، استفاده از متد indexOf برای پیدا کردن مکان یک شیء و سپس فراخوانی متد remove برای حذف آن نمایش داده شد. اگر شیء تکراری باشد، متد indexOf اولین مورد و متد lastIndexOf آخرین مورد را پیدا میکند.
بیشتر بدانید
نکته بهینهسازی Initial Capacity
اگر میدانید قرار است تعداد زیادی داده، مثلاً 1000 مورد، در لیست ذخیره کنید، بهتر است از ابتدا ظرفیت را در سازنده مشخص کنید:
new ArrayList<>(1000)
این کار از چندین بار تغییر سایز خودکار و کپی شدن آرایه جلوگیری میکند؛ عملیاتی که هزینه پردازشی بالایی دارد.
IDE Tip
در محیط IntelliJ IDEA، هنگام فراخوانی یک متد یا سازنده، با فشردن کلیدهای Ctrl + P میتوانید لیست پارامترهای ورودی و اورلودهای مختلف یا Overloads آن متد را مشاهده کنید.
متد سایز
برای به دست آوردن تعداد عناصر موجود در ArrayList همیشه از متد size() استفاده میشود، نه length که مخصوص آرایههای ساده است.
حذف مستقیم آبجکت
متد remove اورلود شده است؛ یعنی هم میتوانید ایندکس بدهید و هم خود آبجکت را مستقیماً پاس دهید تا جاوا آن را پیدا کند و حذف کند.