ساختار لیست داده پیوندی در جاوا

LinkedList در جاوا یک ساختار داده خطی است که عناصر را به صورت گره‌های (Node) جداگانه در حافظه ذخیره می‌کند.
هر گره شامل دو بخش است:
داده (Data) و اشاره‌گر (Pointer) به گره بعدی.
برخلاف آرایه که عناصر به صورت پشت سر هم و در مکان‌های ممتد حافظه ذخیره می‌شوند، در LinkedList گره‌ها می‌توانند در مکان‌های پراکنده حافظه قرار گیرند و با اشاره‌گرها به هم متصل شوند.

 

LinkedList در جاوا بخشی از کالکشن فریمورک (Collection Framework) است و اینترفیس‌های List، Queue و Deque را پیاده‌سازی می‌کند.

 

 

[داده | اشاره‌گر] -> [داده | اشاره‌گر] -> [داده | اشاره‌گر] -> null

هر مستطیل یک گره است. گره اول سر (Head) و گره آخر دم (Tail) نام دارد. اشاره‌گر گره آخر به null ختم می‌شود.

 

مثال ساده:

 

import java.util.LinkedList;


public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        
        names.add("علی");
        names.add("رضا");
        names.add("سارا");
        
        System.out.println(names);
        // خروجی: [علی, رضا, سارا]
    }
}

برای درک بهتر ساختار LinkedList، بیایید نگاهی به داخل این کلاس بیندازیم.

 

// نمای ساده شده از ساختار داخلی LinkedList
class Node<E> {
    E item;        // داده
    Node<E> next;  // اشاره‌گر به گره بعدی
    Node<E> prev;  // اشاره‌گر به گره قبلی (در LinkedList دوطرفه)
}

 

 

نکته مهم: LinkedList در جاوا یک لیست پیوندی دوطرفه (Doubly Linked List) است.
یعنی هر گره هم به گره بعدی (next) و هم به گره قبلی (prev) اشاره می‌کند.
این ویژگی باعث می‌شود پیمایش در هر دو جهت (از اول به آخر و از آخر به اول) به راحتی انجام شود.

جزء	توضیح
First (Head)	اشاره‌گر به اولین گره لیست
Last (Tail)	اشاره‌گر به آخرین گره لیست
Node	هر گره شامل داده، اشاره‌گر به گره بعدی و اشاره‌گر به گره قبلی
Size	تعداد کل گره‌های موجود در لیست

 

LinkedList در جاوا عملیات مختلفی را پشتیبانی می‌کند.
بیایید نحوه کار مهم‌ترین عملیات را بررسی کنیم.

 

import java.util.LinkedList;


public class AddExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // اضافه کردن به انتهای لیست
        list.add("اول");
        list.add("دوم");
        list.add("سوم");
        
        // اضافه کردن به ابتدای لیست
        list.addFirst("صفر");
        
        // اضافه کردن به اندیس مشخص
        list.add(2, "یک و نیم");
        
        System.out.println(list);
        // خروجی: [صفر, اول, یک و نیم, دوم, سوم]
    }
}

 

 

import java.util.LinkedList;


public class RemoveExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("آبی");
        list.add("قرمز");
        list.add("سبز");
        list.add("زرد");
        
        // حذف از ابتدا
        list.removeFirst();
        
        // حذف از انتها
        list.removeLast();
        
        // حذف با اندیس
        list.remove(0);
        
        System.out.println(list);
        // خروجی: [سبز]
    }
}

 

 

import java.util.LinkedList;


public class GetExample {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        numbers.add(100);
        numbers.add(200);
        numbers.add(300);
        numbers.add(400);
        
        // دسترسی به عنصر اول
        System.out.println("اولین: " + numbers.getFirst());
        
        // دسترسی به عنصر آخر
        System.out.println("آخرین: " + numbers.getLast());
        
        // دسترسی با اندیس (از 0 شروع می‌شود)
        System.out.println("اندیس 2: " + numbers.get(2));
    }
}

نکته مهم: دسترسی با اندیس در LinkedList کند است. زیرا باید از ابتدا یا انتها شروع به پیمایش کرد تا به اندیس مورد نظر رسید. زمان این عملیات O(n) است.

 

import java.util.LinkedList;


public class IterateExample {
    public static void main(String[] args) {
        LinkedList<String> colors = new LinkedList<>();
        colors.add("قرمز");
        colors.add("آبی");
        colors.add("سبز");
        colors.add("زرد");
        
        // روش اول: حلقه for معمولی
        System.out.println("روش اول:");
        for (int i = 0; i < colors.size(); i++) {
            System.out.println(colors.get(i));
        }
        
        // روش دوم: حلقه foreach (توصیه می‌شود)
        System.out.println("\nروش دوم:");
        for (String color : colors) {
            System.out.println(color);
        }
        
        // روش سوم: استفاده از Iterator
        System.out.println("\nروش سوم:");
        java.util.Iterator<String> it = colors.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

LinkedList در جاوا علاوه بر عملیات List، عملیات Queue و Deque را نیز پشتیبانی می‌کند.

 

import java.util.LinkedList;
import java.util.Queue;


public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        
        // افزودن به انتهای صف
        queue.add("اولین");
        queue.add("دومین");
        queue.add("سومین");
        
        // مشاهده عنصر اول بدون حذف
        System.out.println("سر صف: " + queue.peek());
        
        // حذف و برگرداندن عنصر اول
        System.out.println("خارج شده: " + queue.poll());
        System.out.println("خارج شده: " + queue.poll());
        
        System.out.println("باقیمانده: " + queue);
    }
}

import java.util.Deque;
import java.util.LinkedList;


public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        
        // افزودن از دو طرف
        deque.addFirst("اول");
        deque.addLast("آخر");
        deque.addFirst("جديدترين اول");
        deque.addLast("جديدترين آخر");
        
        System.out.println("Deque: " + deque);
        
        // گرفتن از دو طرف
        System.out.println("گرفته شده از اول: " + deque.removeFirst());
        System.out.println("گرفته شده از آخر: " + deque.removeLast());
        
        System.out.println("بعد از عملیات: " + deque);
    }
}

این یکی از مهم‌ترین مقایسه‌ها در برنامه‌نویسی جاوا است. انتخاب درست بین این دو تأثیر زیادی بر کارایی برنامه دارد.

ویژگی	LinkedList	ArrayList
ساختار داخلی	آرایه پویا (داینامیک)	لیست پیوندی دوطرفه
دسترسی با اندیس (get)	خیلی سریع O(1)	کند O(n)
درج/حذف در ابتدا	کند O(n) - جابه‌جایی همه عناصر	سریع O(1)
درج/حذف در انتها	سریع O(1) (با احتساب افزایش ظرفیت)	سریع O(1)
درج/حذف در میانه	کند O(n) - جابه‌جایی عناصر	نسبتاً سریع O(n) (پیمایش + درج ثابت)
مصرف حافظه	کمتر (فقط داده + یک متغیر size)	بیشتر (داده + دو اشاره‌گر)
پیمایش با حلقه	سریع (کش فریندلی)	نسبتاً کند
مناسب برای	خواندن مکرر، دسترسی تصادفی	درج و حذف مکرر در ابتدا و میانه

import java.util.*;


public class CompareExample {
    public static void main(String[] args) {
        // تست ArrayList
        List<Integer> arrayList = new ArrayList<>();
        // تست LinkedList
        List<Integer> linkedList = new LinkedList<>();
        
        // درج در ابتدا - LinkedList برنده است
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            arrayList.add(0, i);  // کند
        }
        long end = System.nanoTime();
        System.out.println("ArrayList add first: " + (end - start) + " ns");
        
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            linkedList.add(0, i);  // سریع
        }
        end = System.nanoTime();
        System.out.println("LinkedList add first: " + (end - start) + " ns");
        
        // دسترسی تصادفی - ArrayList برنده است
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            arrayList.get(5000);
        }
        end = System.nanoTime();
        System.out.println("ArrayList get: " + (end - start) + " ns");
        
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            linkedList.get(5000);  // کند
        }
        end = System.nanoTime();
        System.out.println("LinkedList get: " + (end - start) + " ns");
    }
}

 

 

import java.util.LinkedList;
import java.util.Queue;


class Customer {
    String name;
    String service;
    
    Customer(String name, String service) {
        this.name = name;
        this.service = service;
    }
    
    @Override
    public String toString() {
        return name + " (" + service + ")";
    }
}


public class CustomerQueueSystem {
    public static void main(String[] args) {
        Queue<Customer> queue = new LinkedList<>();
        
        // مشتریان وارد صف می‌شوند
        queue.add(new Customer("علی رضایی", "افتتاح حساب"));
        queue.add(new Customer("سارا محمدی", "دریافت کارت"));
        queue.add(new Customer("رضا کریمی", "مشاوره سرمایه‌گذاری"));
        queue.add(new Customer("مریم احمدی", "تغییر رمز"));
        
        System.out.println("صف مشتریان: " + queue.size() + " نفر");
        
        // خدمت رسانی به مشتریان
        int number = 1;
        while (!queue.isEmpty()) {
            Customer current = queue.poll();
            System.out.println(number + ". خدمت به " + current);
            number++;
        }
        
        System.out.println("همه مشتریان خدمت دریافت کردند.");
    }
}

LinkedList در جاوا یک ساختار داده قدرتمند و انعطاف‌پذیر است که برای سناریوهای خاصی بسیار مناسب است.
نکاتی که باید به خاطر بسپارید:

انتخاب بین ArrayList و LinkedList باید بر اساس نیاز واقعی برنامه شما انجام شود. هیچکدام ذاتاً بهتر از دیگری نیست؛ هر کدام برای کاربرد خاص خود طراحی شده است.