کالکشن ها در جاوا: آموزش کار با LinkedList + مثال

معرفی LinkedList

بر خلاف list که عناصر آرایه وار مستقیم روی حافظه ذخیره میشن، در لیست پیوندی (LinkedList) عناصر در گره (node) ها ذخیره میشن.

هر عنصر داخل یک node نگهداری میشه و هر node به node بعد از خودش و به node قبل از خودش اشاره میکنه. در زیر به صورت تصویری شرح داده شده که چطور عناصر در LinkedList نگهداری میشن.

کار با لیست پیوندی (LinkedList)

یکی دیگه از پیاده‌سازی های List در لیست پیوندی است؛ متد های گفته شده در List، با لیست پیوندی (LinkedList) هم بازنویسی شدن.

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

در نمودار UML زیر رابطه ی سلسله مراتب ارث‌بری در لیست پیوندی شرح داده شده است.

نمودار UML رابطه ارث‌بری کلاس LinkedList در جاوا — نمودار UML سلسه مراتب ارث‌بری کلاس LinkedList در جاوا

کلاس LinkedList علاوه بر متد های تعریف شده در اینترفیس List متد های اختصاصی خودشو داره این متد ها برای بهینه کردن عمل حذف و اضافه عناصر در اول و آخر لیست تعریف شده اند؛ در نمودار UML زیر کلاس LinkedList با متد های اختصاصی تعریف شده در داخلش شرح داده شده است.

java.util.LinkedList
+LinkedList()	یک نمونه از LinkedList ایجاد میکنه.
+LinkedList(c: Collection<? extends E>)	یک نمونه از LinkedList ایجاد می کنه و عناصر کالکشن c رو بهش اضافه می کنه.
+addFirst(e: E): void	عنصر e رو به اول لیست اضافه می کنه.
+addLast(e: E): void	عنصر e رو به آخر لیست اضافه می کنه.
+getFirst(): E	اولین عنصر در لیست رو بر میگردونه.
+getLast(): E	آخرین عنصر در لیست رو بر میگردونه.
+removeFirst(): E	اولین عنصر رو از لیست حذف می کنه و بر میگردونه.
+removeLast(): E	آخرین عنصر رو از لیست حذف میکنه و بر میگردونه.

در مثال زیر میخوایم اسم رنگ ها رو به صورت String در LinkedList ذخیره کنیم و سپس با حلقه ی for به پیمایش در LinkedList بپردازیم و با حلقه ی while عناصر رو از آخر عنصر حذف کنیم.

LinkedList<String> colors = new LinkedList<>();
colors.add("Blue");
colors.add("Pink");
colors.add("Purple");
colors.addFirst("Cyan");
colors.add(1, "Red");
colors.removeLast();
colors.addLast("Yellow");

System.out.println("Display colors ");
for(int i =0; i<colors.size(); i++){
  String c = colors.get(i);
  System.out.print(c + " ");
}

System.out.println("Remove and Display colors backward: ");

while(!colors.isEmpty()){
  String c = colors.removeLast();
  System.out.println(c);
  
}

در بالا پیچیدگی زمان صدا زدن عناصر با index برابر با O(n) است و پیچیدگی زمان حلقه ی for نیز O(n) است پس پیچیدگی زمان کل در حلقه ی for برابر با O(n^2) است؛ در حالی که پیچیدگی زمان کل در حلقه ی while با حذف عناصر برابر با O(n) است.

در مثال زیر یک نمونه از LinkedList از نوع Object ایجاد می کنیم، و عناصری از نوع integer و String رو داخلش نگهداری میکنم و سپس به حذف آخرین عنصر در لیست و اولین عنصر در لیست میپردازیم پس از هر بار حذف با حلقه ی foreach عنصر های باقی مونده در لیست رو نمایش میدیم.

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(52);
list.add(12);
list.add(16);

LinkedList<Object> linkedList = new LinkedList<>(list);
linkedList.add(0, "Red");
linkedList.addFirst("Green");
System.out.println("A list of objects in linked list:");
System.out.println(linkedList);

System.out.println("After removing " + linkedList.removeLast() + " elements in linkedlist are as follow: ");
for(Object o: linkedList)
   System.out.print(o + " ");

System.out.println("After removing " + linkedList.removeFirst() + " elements linkedlist are as follow: ");
for(Object o: linkedList)
   System.out.println(o + " ");

در مثال زیر میخوایم یک پشته (Stack) با لیست پیوندی پیاده کنیم.

public class MyStack<E> {

    private final LinkedList<E> list = new LinkedList<>();

    public MyStack(E[] elements){
        for (int i=0; i<elements.length; i++){
            list.addLast(elements[i]);
        }
    }

    public MyStack(){

    }

    public E pop(){
        if (list.isEmpty()) return null;
        return list.removeLast();
    }

    public void push(E e){
        list.addLast(e);
    }

    public E peek(){
        if (list.isEmpty()) return null;
        return list.getLast();
    }

    public boolean isEmpty(){
        return list.isEmpty();
    }

    public int getSize(){
        return list.size();
    }
}

پیچیدگی زمان متد ها در لیست پیوندی (LinkedList)

در این قسمت میخوایم پیچیدگی زمان متد ها در لیست پیوندی (LinkedList) رو بررسی کنیم.

در جدول زیر پیچیدگی زمان متد های LinkedList در بدترین حالت (worst case) توضیح داده شده است.

LinkedList
متد	پیچیدگی زمان (Time Complexity)
add(E): boolean	O(1)
add(int, E): void	O(n)
get(int): E	O(n)
remove(Object): boolean	O(n)
remove(int): E	O(n)
set(int, E): E	O(n)
contains(Object): boolean	O(n)
addFirst(E): void	O(1)
addLast(E): void	O(1)
removeFirst(): E	O(1)
removeLast(): E	O(1)
getFirst(): E	O(1)
getLast(): E	O(1)

خلاصه

زمانی که بخوایم عناصر رو از ابتدا یا انتهای لیست حذف کنیم استفاده از لیست پیوندی (LinkedList) بهینه تر از ArrayList است.
یکی از پیاده‌سازی های اینترفیس ‌List، در لیست پیوندی (LinkedList) است.
متد های تعریف شده در اینترفیس List در لیست پیوندی بازنویسی شده.