آموزش برنامه نویسی

LinkedList

کلاس LinkedList پیاده سازی interface های Deque و List است و برای همین صفات لیست و صف را با هم داراست، این کلاس به صورت ساختمان داده لیست دو پیوندی (Doubly-LinkedList) پیاده سازی شده است و برای همین می‌توان به سادگی و در زمان کم به ابتدا و انتهای عنصر جدید اضافه کرد، به علاوه به دلیل دو پیوندی بودن عمل حذف به صورت بهینه تری انجام می‌پذیرد. از این کلاس می‌توان به عنوان یک لیست ساده با دسترسی تصادفی، صف دو طرفه، صف FIFO یا حتی صف LIFO استفاده کرد.این کلاس از لحاظ عملکرد بسیار شبیه ArrayList است و تفاوت آن‌ها در ساختمان داده ای است که به کار می‌برند، شباهت‌ها و تفاوت این دو کلاس عبارت‌اند از :

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

کلاس LinkedList از طریق مسیر java.util.LinkedList قابل دستیابی است. برای ساختشی از کلاس LinkedList باید از یکی از سازنده‌های زیر استفاده کنیم :

LinkedList()

این سازنده یک LinkedList خالی ایجاد می‌کند.

LinkedList(Collection c)

این سازنده یک LinkedList جدید ایجاد می‌کند و اعضای کالکشن c را به عنوان آیتم‌های اولیه به LinkedList اضافه می‌کند. متدهای مهم LinkedList در جدول زیر آمده‌اند :

بسیاری از متدهای فوق عمل یکسانی انجام می‌دهند و اینکه در عین کاربرد از کدام یک از آن‌ها استفاده کنیم بیشتر به سلایق برنامه نویس مربوط می‌شود. در ادامه با چند مثال با LinkedList آشنا می‌شویم. در این مثال با کاربرد LinkedList به عنوان یک لیست با دسترسی تصادفی آشنا می‌شویم :

import java.util.LinkedList;

public class LinkedListDemo 
{
    public static void main(String[] args) 
    {
        LinkedList myLL = new LinkedList();

        myLL.add("A");
        myLL.add("B");
        myLL.add("C");

        System.out.println(myLL);

        System.out.println(myLL.get(1));
        System.out.println(myLL);

        System.out.println(myLL.remove(1));
        System.out.println(myLL);

        System.out.println(myLL.indexOf("C"));
    }
}

[A, B, C]
B
[A, B, C]
B
[A, C]
1

در کد بالا ابتدا یک LinkedList ایجاد می‌کنیم و سپس با استفاده از متد add عناصری را به آن اضافه می‌کنیم، می دانیم که این متد عناصر را به انتهای لیست اضافه می‌کند. پس از ساخت لیست یک بار آن را چاپ می‌کنیم. با استفاده از متد get عنصر موجود در اندیس 1 را به دست آورده و آن را چاپ کرده و سپس کل لیست را چاپ می‌کنیم. عنصر موجود در اندیس یک را با متد remove حذف کرده و آن را چاپ می‌کنیم، می‌بینیم که عنصر B حذف می‌شود زیرا در LinkedList اندیس از صفر شروع می‌شود. در انتها با استفاده از متد indexOf اندیس عنصر C را به دست آورده و چاپ می‌کنیم. در مثال دوم، به ابتدا و انتهای لیست عنصر اضافه کرده و سپس آن‌ها را حذف می‌کنیم :

import java.util.LinkedList;

public class LinkedListDemo 
{
    public static void main(String[] args) 
    {
        LinkedList myLL = new LinkedList();

        myLL.add("O");

        myLL.addFirst("A1");
        myLL.addLast("B1");
        System.out.println(myLL);

        myLL.addFirst("A2");
        myLL.addLast("B2");
        System.out.println(myLL);

        myLL.removeFirst();
        System.out.println(myLL);

        myLL.removeLast();
        System.out.println(myLL);
    }
}

[A1, O, B1]
[A2, A1, O, B1, B2]
[A1, O, B1, B2]
[A1, O, B1]

در کد بالا ابتدا با استفاده از متد add یک عنصر به لیست اضافه می‌کنیم، سپس عنصر A1 را با استفاده از متد addFirst به ابتدای لیست و عنصر B1 را با استفاده از متد addLast به انتهای لیست اضافه می‌کنیم و بعد لیست را چاپ می‌کنیم. عنصر A2 را به ابتدای لیست و عنصر B2 را به انتهای لیست اضافه می‌کنیم و لیست را چاپ می‌کنیم. با استفاده از متد removeFirst عنصر ابتدای لیست را حذف می‌کنیم. با استفاده از متد removeLastعنصر انتهای لیست را حذف می‌کنیم. می‌توانیم به اشکال زیر از LinkedList به عنوان پیاده سازی Queue، Deque و List استفاده کنیم :

Queue queue = new LinkedList();

Deque deque = new LinkedList();

List list   = new LinkedList();

استفاده از LinkedList به عنوان صف LIFO (یا همان Stack)

از LinkedList می‌توانیم به عنوان صف LIFO نیز استفاده کنیم، کلمه LIFO مخفف عبارت Last in First Out است و بدین معنی است که عنصری که دیرتر اضافه می‌شود زودتر خارج می‌شود، به چنین صفی Stack نیز گفته می‌شود. در جاوا کلاس اختصاصی برای Stack نیز وجود دارد ولی می‌توانیم از LinkedList نیز به جای آن استفاده کنیم :

import java.util.LinkedList;

public class LinkedListDemo 
{
    public static void main(String[] args) 
    {
        LinkedList myLIFO = new LinkedList();

        myLIFO.push("A");
        myLIFO.push("B");
        myLIFO.push("C");

        System.out.println(myLIFO);

        System.out.println(myLIFO.pop());
        System.out.println(myLIFO);

        System.out.println(myLIFO.pop());
        System.out.println(myLIFO);

        System.out.println(myLIFO.pop());
        System.out.println(myLIFO);
    }
}

[C, B, A]
C
[B, A]
B
[A]
A
[]

در کد بالا با استفاده از متد push عناصر را به صف LIFO اضافه می‌کنیم، در انتها عنصر C در بالای صف قرار خواهد داشت. در ادامه با استفاده از متد pop عنصر بالای صف را حذف می‌کنیم، می دانیم که در این شیوه عنصری که دیرتر اضافه شده زودتر حذف می‌شود لذا ابتدا C و سپس B و در انتها A از صف حذف می‌شوند. هر بار پس از عمل حذف صف را نیز چاپ می‌کنیم.