آرایه های پویا در جاوا

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

آرایه های پویا در دوره JavaRush

این مبحث به صورت کاملاً قابل فهم و واضح در سطح 7 و تا حدی در سطح 8 دوره JavaRush در کوئست Java Syntax پوشش داده شده است. در طول چندین سخنرانی و 18 مشکل، مسائل کلیدی، انواع آرایه های پویا و تفاوت بین آنها از جمله عملکرد پوشش داده شده است. این موضوع بسیار مهم است، زیرا آرایه های پویا توسعه دهنده را از افسردگی، سردرد خلاص می کند و مقدار باورنکردنی در زمان صرفه جویی می کند.

آرایه پویا چیست؟

آرایه پویا آرایه ای است که می تواند اندازه خود را در حین اجرای برنامه تغییر دهد. در جاوا این نقش عمدتا توسط کلاس های ArrayList و LinkedList ایفا می شود. بر خلاف آرایه ها، ArrayList و LinkedList فقط شامل انواع داده های مرجع هستند، یعنی فقط می توانند اشیاء را ذخیره کنند. خوشبختانه جاوا دارای مکانیزم‌های خودکار و جعبه‌گشایی خودکار است که به شما امکان می‌دهد انواع اولیه را در آرایه‌های پویا ذخیره کنید. مانند یک آرایه استاتیک، یک آرایه پویا همگن است، یعنی می تواند یک نوع داده واحد را ذخیره کند. با این حال، به لطف مکانیسم وراثت و استفاده مناسب از رابط‌ها، می‌توان در یک آرایه پویا طیف کاملی از کلاس‌های مختلف را که از یک کلاس مشترک به ارث برده شده‌اند ذخیره کرد، اما در مورد آن در زیر بیشتر به ارث رسیده‌اند. یعنی یک آرایه استاتیک به این صورت عمل می کند: و یک آرایه پویا در جاوا به صورت زیر عمل می کند (ادامه نمودار از مرحله سوم): جاوا از یک تابع بومی ویژه برای کپی کردن یک آرایه استفاده می کند، بنابراین چنین "حرکت" خیلی زیاد نیست. گران.

چرا به یک آرایه پویا نیاز داریم؟

یک آرایه پویا در جاوا برای پردازش مجموعه ای از داده های همگن استفاده می شود که اندازه آنها در زمان نوشتن برنامه ناشناخته است. به عنوان مثال، ممکن است بخواهید داده های هر کلاینت هایی که در حال حاضر از برنامه استفاده می کنند را در حافظه پنهان ذخیره کنید. پیش بینی تعداد چنین مشتریانی از قبل غیرممکن است. بدون آرایه های پویا، این مشکل را می توان با گزینه های زیر حل کرد:

1. یک آرایه بزرگ ایجاد کنید که به احتمال 100٪ نیاز را پوشش دهد.
2. یک آرایه استاتیک ایجاد کنید که به عنوان یک بافر عمل می کند.
3. سایر ساختارهای پویا مانند مجموعه ها را اعمال کنید.

گزینه اول فقط در مورد یک محدوده کاملاً محدود مناسب است. در موارد دیگر، چنین آرایه ای مقدار زیادی از فضای حافظه را اشغال می کند که بسیار ناکارآمد است. مورد دوم به پیاده سازی مکانیک های اضافی برای پاکسازی بافر، خواندن و غیره نیاز دارد. سومی نیز به دلیل تفاوت در عملکرد دارای معایبی است.

یک آرایه پویا در جاوا چه می کند؟

در زبان جاوا، کلاس های ArrayList و LinkedList به عنوان یک آرایه پویا عمل می کنند. رایج ترین مورد استفاده، ArrayList است، زیرا برخلاف LinkedList که مفهوم لیست پیوندی دوگانه را پیاده سازی می کند، به عنوان یک آرایه کلاسیک عمل می کند. کمی بعد در مورد آن صحبت خواهیم کرد.

ArrayList، LinkedList - مفاهیم و قوانین عملیاتی

ArrayList یک آرایه کلاسیک است که در طول اجرای برنامه قابل گسترش است. این بر اساس یک آرایه منظم است: اندازه آن هنگام ایجاد 10 عنصر است. با افزایش اندازه، ظرفیت افزایش می یابد. قوانینی که ArrayList بر اساس آن کار می کند:

• درست مانند یک آرایه استاتیک، از 0 ایندکس می شود.
• درج در انتها و دسترسی به فهرست بسیار سریع است - O(1);
• برای درج یک عنصر در ابتدا یا وسط، باید تمام عناصر را یک سلول به سمت راست کپی کنید و سپس یک عنصر جدید را در موقعیت مورد نیاز قرار دهید.
• دسترسی بر اساس مقدار به تعداد عناصر بستگی دارد - O(n);
• برخلاف یک آرایه کلاسیک، می تواند null را ذخیره کند.

در مورد LinkedList، همه چیز کمی پیچیده تر است: این لیست بر اساس یک لیست دارای پیوند دوگانه است. یعنی از نظر ساختاری، این آرایه پویا جاوا تعدادی اشیاء پراکنده است که به یکدیگر اشاره دارند. توضیح آن با تصاویر راحت تر است. در داخل LinkedList یک شی اصلی داریم Headکه اطلاعاتی درباره تعداد عناصر و همچنین پیوندی به اولین و آخرین عناصر ذخیره می کند: اکنون فیلد ، و size = 0است . هر عنصری که به این لیست اضافه می شود محتوای یک شی داخلی جداگانه است. بیایید یک عنصر اضافه کنیم : اکنون یک گره با مقدار "Johnny" داریم. برای عنصر اصلی، پیوندهای اولین و آخرین عنصر به گره جدید اشاره می کنند. این شی همچنین دارای پیوندهایی به عناصر قبلی و بعدی است. پیوند قبلی همیشه تهی خواهد بود، زیرا این اولین عنصر است، و پیوند به بعدی همیشه پوچ خواهد بود، زیرا هنوز وجود ندارد. بیایید این را حل کنیم: یک عنصر جدید با مقدار "Watson" اضافه شد که به عنصر دوم تبدیل شد. لطفاً توجه داشته باشید که عنصر اول دارای فیلدی است که به عنصر بعدی اشاره می کند و عنصر جدید دارای فیلدی است که به عنصر قبلی اشاره می کند. برای عنصر اصلی، پیوند به آخرین عنصر اکنون به گره جدید اشاره می کند. نمودار زیر نحوه افزودن عناصر به وسط لیست را نشان می دهد: یک عنصر جدید "Hamish" اضافه شده است. برای درج آن در وسط لیست، کافی است پیوندها را به عناصر، همانطور که در شکل نشان داده شده است، دوباره اختصاص دهید. این تصاویر روند یک لیست دوگانه پیوند خورده را در سطح بالا بدون پرداختن به جزئیات توضیح می دهد. برای خلاصه کردن داستان LinkedList، می‌توانیم چندین قانون را برای عملکرد آن استخراج کنیم: firstlast = nullJohnnynextprevious

• درست مانند یک آرایه، از 0 ایندکس می شود.
• دسترسی به اولین و آخرین عنصر به تعداد عناصر بستگی ندارد - O(1).
• دریافت یک عنصر با فهرست، درج یا حذف از وسط یک لیست به تعداد عناصر بستگی دارد - O(n);
• می توانید از مکانیسم تکرار کننده استفاده کنید: سپس درج و حذف در زمان ثابت رخ می دهد.
• برخلاف یک آرایه کلاسیک، می تواند null را ذخیره کند.

نمونه های کد

بیایید چند نمونه را مرور کنیم. قطعه کد شامل نمونه هایی برای ArrayList و LinkedList است.

ایجاد

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

افزودن یک عنصر

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

در نگاه اول، متدهای add()AND addLast()عملکرد یکسانی را انجام می دهند، اما متد add()از رابط به LinkedList آمد Listو متد addLastاز اینترفیس آمده است Deque. LinkedList هر دوی این رابط ها را پیاده سازی می کند. یک تمرین خوب در این مورد استفاده از روشی است که برای زمینه مناسب ترین است. اگر LinkedList به عنوان یک صف استفاده می شود، بهتر است از addLast. اگر LinkedList به عنوان یک لیست استفاده می شود، مناسب است که از add().

حذف یک عنصر

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

اگر یک شی توسط شاخص حذف شود، متد شی حذف شده را برمی گرداند. اگر یک شی با مقدار حذف شود (یا اولین یا آخرین عناصر یک LinkedList حذف شود)، اگر شی پیدا شود و حذف شود، متد true را برمی‌گرداند، در غیر این صورت false را برمی‌گرداند .

دسترسی به یک مورد و جستجو در لیست

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

راه رفتن در یک حلقه

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

در اینجا ارزش گفتن چند کلمه در مورد جستجو را دارد. بسیاری از توسعه دهندگان مبتدی، هنگام جستجوی یک عنصر در یک لیست، جستجو را در یک حلقه شروع می کنند و با وجود روش ها، همه عناصر را با عنصر جستجو شده مقایسه می indexOf()کنند lastIndexOf(). همچنین می توانید از روش contains()برای دریافت این واقعیت استفاده کنید که یک عنصر در لیست است:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

لینک هایی برای مطالعه بیشتر

1. در اینجا یک مقاله عالی در مورد حذف عناصر از ArrayList وجود دارد . با توجه به اینکه این یک آرایه جاوا پویا است ، ظرافت های زیادی در حذف عناصر وجود دارد.
2. عملکرد ArrayList به تفصیل در اینجا نشان داده شده است .
3. کمی بیشتر در مورد LinkedList.
4. چند مقاله از Habr درباره ArrayList و LinkedList .