ArrayList در تصاویر

سلام! درس امروز درباره در مورد ArrayListدرس‌های قبلی هم آسان‌تر و هم سخت‌تر خواهد بود. دشوارتر خواهد بود زیرا امروز ما می خواهیم به زیر کاپوت نگاه کنیم ArrayListو بررسی کنیم که در طول عملیات های مختلف چه اتفاقی می افتد. از طرفی این درس تقریبا هیچ کدی نخواهد داشت. بیشتر تصاویر و توضیحات است. خب، بریم:) همانطور که می دانید، ArrayListیک آرایه معمولی در داخل وجود دارد که به عنوان یک ذخیره اطلاعات عمل می کند. در بیشتر موارد، اندازه دقیق لیست را مشخص نمی کنیم. اما آرایه داخلی باید مقداری اندازه داشته باشد! و همینطور هم می شود. اندازه پیش فرض آن 10 است .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

ابتدا، بیایید ببینیم افزودن عناصر جدید چگونه به نظر می رسد. اولین کار این است که بررسی کنید آیا آرایه داخلی فضای کافی در آرایه داخلی دارد و آیا یک عنصر دیگر جا می‌شود یا خیر. اگر فضای خالی وجود داشته باشد، عنصر جدید به انتهای لیست اضافه می شود. وقتی می گوییم "تا انتها"، منظور ما آخرین موقعیت در آرایه نیست (که عجیب است). منظور ما موقعیت بعد از آخرین عنصر فعلی است. شاخص آن خواهد بود cars.size(). لیست ما در حال حاضر خالی است ( cars.size() == 0). بر این اساس، عنصر جدید در موقعیت 0 اضافه خواهد شد.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

این به اندازه کافی واضح است. اگر در وسط یعنی بین عناصر دیگر وارد کنیم چه اتفاقی می افتد؟

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   cars.add(1, ford);// add ford to cell 1, which is already occupied
}

مجدداً، ابتدا بررسی می شود که آیا فضای کافی در آرایه وجود دارد یا خیر. اگر فضای کافی وجود داشته باشد، عناصر به سمت راست جابه‌جا می‌شوند و از موقعیتی که عنصر جدید را وارد می‌کنیم شروع می‌شود. ما در موقعیت 1 درج می کنیم. به عبارت دیگر، عنصر از موقعیت 3 در موقعیت 4، عنصر 2 به موقعیت 3، و عنصر 1 در موقعیت 2 کپی می شود. سپس عنصر جدید ما در جای خود قرار می گیرد. عنصر قبلی (بوگاتی) قبلاً از آنجا در یک موقعیت جدید کپی شده است. حال بیایید ببینیم اگر جایی برای درج عناصر جدید در آرایه وجود نداشته باشد، این فرآیند چگونه اتفاق می‌افتد. طبیعتاً ابتدا بررسی می شود که آیا فضای کافی وجود دارد یا خیر. اگر فضای کافی وجود نداشته باشد، یک آرایه جدید در داخل آرایه ایجاد می شود ArrayListکه اندازه آن به اندازه آرایه قدیمی ضربدر 1.5 به اضافه 1 است در مورد ما، اندازه آرایه جدید 16 خواهد بود. همه عناصر فعلی در آنجا کپی می شوند. بلافاصله. مستقیما. آرایه قدیمی توسط جمع کننده زباله حذف می شود و فقط آرایه جدید و گسترش یافته باقی می ماند. اکنون جا برای عنصر جدید وجود دارد. ما آن را در موقعیت 3 قرار می دهیم که اشغال شده است. اکنون روال آشنا شروع می شود. همه عناصر، که با شاخص 3 شروع می شوند، یک موقعیت به سمت راست منتقل می شوند و عنصر جدید بی سر و صدا اضافه می شود. و درج انجام شد! و ما کار درج را تمام کردیم. حالا بیایید در مورد حذف موارد صحبت کنیم . به یاد دارید که هنگام کار با آرایه ها با مشکلی مواجه شدیم: حذف عناصر باعث ایجاد "سوراخ" در آرایه می شود. تنها راه خروج، جابجایی آیتم های باقی مانده با هر حذف بود و ما باید هر بار برای انجام این تغییر، کد خود را می نوشتیم. ArrayList از همان اصل پیروی می کند، اما قبلاً این مکانیسم را پیاده سازی کرده است. اینگونه به نظر می رسد: و در پایان به آنچه می خواهیم می رسیم: عنصر lamboحذف شده است. در اینجا یک عنصر را از وسط حذف کردیم. واضح است که حذف یک عنصر از انتهای لیست سریعتر است، زیرا عنصر به سادگی بدون نیاز به جابجایی سایر عناصر حذف می شود. بیایید یک لحظه دوباره در مورد ابعاد آرایه داخلی و نحوه چیدمان آن در حافظه صحبت کنیم. گسترش یک آرایه به منابعی نیاز دارد. ArrayListبر این اساس، اگر مطمئن هستید که دارای حداقل 100 عنصر است، با اندازه پیش فرض ایجاد نکنید . آرایه داخلی باید تا زمانی که 100 عنصر را وارد می‌کنید 6 بار گسترش یابد و همه عناصر باید هر بار جابجا شوند.

• از 10 عنصر به 16
• از 16 عنصر تا 25
• از 25 تا 38
• از 38 تا 58
• از 58 تا 88
• از 88 تا 133 (یعنی اندازه آرایه قدیمی برابر با 1.5 به علاوه 1)

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

ArrayList<Car> cars = new ArrayList<>(100);

اکنون حافظه آرایه ای از 100 عنصر به یکباره تخصیص داده می شود و آرایه را کارآمدتر می کند (نیازی به گسترش آن نخواهد بود). این استراتژی یک طرف دیگر نیز دارد. هنگامی که اشیاء را از یک حذف می کنید ArrayList، اندازه آرایه داخلی به طور خودکار کاهش نمی یابد. ArrayListفرض کنید یک آرایه داخلی کاملاً کامل از ۸۸ عنصر داریم : با اجرای برنامه، ۷۷ عنصر را حذف می‌کنیم، بنابراین فقط ۱۱ عنصر باقی می‌ماند: آیا قبلا حدس زده‌اید مشکل چیست؟ متوجه شدید، استفاده ناکارآمد از حافظه! ما در اینجا فقط از 11 موقعیت استفاده می کنیم، اما حافظه را برای 88 عنصر اختصاص داده ایم. این 8 برابر بیشتر از نیاز ماست! در این صورت می توانیم استفاده از حافظه خود را با یکی از ArrayListمتدهای ویژه کلاس بهینه کنیم: trimToSize(). این روش طول آرایه داخلی را به تعداد عناصر ذخیره شده در آن کاهش می دهد. اکنون ما فقط به اندازه نیاز به حافظه اختصاص داده ایم! :)