جاوا میں متحرک صفیں۔

پیچیدگی کی مختلف ڈگریوں کے پروگرام بناتے وقت، ہر ڈویلپر بہت سے ڈیٹا کی اقسام کا استعمال کرتا ہے، بشمول ارے۔ یہ ڈھانچہ ایک قسم کے سیٹ کو ذخیرہ کرنے کے لیے موزوں ہے، بہترین کارکردگی فراہم کرتا ہے، اور عام طور پر آسان ہے۔ صفوں کا ایک اہم نقصان یہ ہے کہ وہ جامد ہیں: ان کے سائز کی پہلے سے وضاحت ہونی چاہیے۔ تاہم، پروگرامرز ابھی تک یہ نہیں جانتے کہ مستقبل کی پیشن گوئی کیسے کی جائے (جب تک کہ، یقیناً، AI ظاہر نہ ہو جو معلومات کو ناقابل یقین حد تک تیزی سے پروسیس کرے گا اور کسی بھی واقعات کی پیشین گوئی کرنے کے قابل ہو جائے گا)۔ اس وجہ سے، ہم نے ایک ایسا ڈھانچہ بنایا جو پروگرام کے چلنے کے دوران اس کا سائز تبدیل کر سکتا ہے۔ اسے متحرک صف کہا جاتا ہے ۔

JavaRush کورس میں متحرک صفیں۔

اس موضوع کو جاوا سنٹیکس کی تلاش میں جاوا رش کورس کے لیول 7 اور جزوی طور پر لیول 8 پر بہت فہم اور واضح طور پر احاطہ کیا گیا ہے ۔ کئی لیکچرز اور 18 مسائل کے دوران، کلیدی مسائل، متحرک صفوں کی اقسام اور ان کے درمیان فرق، بشمول کارکردگی۔ یہ موضوع انتہائی اہم ہے، کیونکہ متحرک صفیں ڈیپریشن، سر درد سے نجات دلاتی ہیں اور ناقابل یقین وقت بچاتی ہیں۔

ایک متحرک صف کیا ہے؟

ایک متحرک صف ایک ایسی صف ہے جو پروگرام کے عمل کے دوران اپنے سائز کو تبدیل کرسکتی ہے۔ جاوا میں، یہ کردار بنیادی طور پر ArrayList اور LinkedList کلاسز کے ذریعے ادا کیا جاتا ہے۔ arrays کے برعکس، 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ہے، firstاور last = null۔ ہر عنصر جو اس فہرست میں شامل کیا جاتا ہے وہ ایک الگ اندرونی آبجیکٹ کا مواد ہے۔ آئیے ایک عنصر شامل کریں Johnny: اب ہمارے پاس "Johnny" کی قدر کے ساتھ ایک نوڈ ہے۔ مرکزی عنصر کے لیے، پہلے اور آخری عنصر کے لنکس نئے نوڈ کی طرف اشارہ کرتے ہیں۔ اس آبجیکٹ کے پچھلے اور اگلے عناصر سے بھی روابط ہیں۔ پچھلے والے کا لنک ہمیشہ null رہے گا، کیونکہ یہ پہلا عنصر ہے، اور اگلے کا لنک ہمیشہ null رہے گا، کیونکہ یہ ابھی موجود نہیں ہے۔ آئیے اسے ٹھیک کرتے ہیں: "واٹسن" کی قدر کے ساتھ ایک نیا عنصر شامل کیا، جو دوسرا بن گیا۔ براہ کرم نوٹ کریں کہ پہلے عنصر میں ایک فیلڈ ہے nextجو اگلے عنصر کی طرف اشارہ کرتا ہے، اور نئے عنصر میں ایک فیلڈ ہے previousجو پچھلے عنصر کی طرف اشارہ کرتا ہے۔ مرکزی عنصر کے لیے، آخری عنصر کا لنک اب نئے نوڈ کی طرف اشارہ کرتا ہے۔ درج ذیل خاکہ سے پتہ چلتا ہے کہ فہرست کے وسط میں عناصر کو کیسے شامل کیا جائے: ایک نیا عنصر "Hamish" شامل کیا گیا ہے۔ اسے فہرست کے وسط میں داخل کرنے کے لیے، صرف عناصر کے لنکس کو دوبارہ تفویض کریں، جیسا کہ تصویر میں دکھایا گیا ہے۔ یہ مثالیں تفصیل میں جانے کے بغیر، اوپر کی سطح پر دوہری منسلک فہرست کے عمل کی وضاحت کرتی ہیں۔ LinkedList کے بارے میں کہانی کا خلاصہ کرنے کے لیے، ہم اس کے آپریشن کے لیے کئی اصول اخذ کر سکتے ہیں:

• بالکل ایک صف کی طرح، یہ 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 کے پہلے یا آخری عناصر کو حذف کر دیا جاتا ہے)، تو طریقہ درست ہو جاتا ہے اگر آبجیکٹ پایا جاتا ہے اور حذف کر دیا جاتا ہے، ورنہ غلط ۔

کسی شے تک رسائی اور فہرست تلاش کرنا

// Доступ к элементу по индексу
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 سے عناصر کو ہٹانے کے بارے میں یہاں ایک بہترین مضمون ہے ۔ اس حقیقت کی وجہ سے کہ یہ ایک متحرک Java سرنی ہے ، عناصر کو ہٹانے میں بہت سی باریکیاں ہیں۔
2. ArrayList کے کام کو یہاں تفصیل سے بیان کیا گیا ہے ۔
3. LinkedList کے بارے میں تھوڑا سا مزید ۔
4. ArrayList اور LinkedList کے بارے میں Habr کے کچھ مضامین ۔