دوره‌ها / JAVA / لیست‌های پیوندی (Java LinkedList)

لیست‌های پیوندی (Java LinkedList)

15 دقیقه Article

لیست‌های پیوندی (LinkedList): زنجیره‌ای از داده‌ها 🔗🧩

LinkedList یکی دیگر از کلاس‌های پیاده‌سازی شده از اینترفیس List است. ظاهر آن شبیه به ArrayList است اما روش ذخیره‌سازی آن در حافظه کاملاً متفاوت است.

تفاوت ساختاری: کانتینر در مقابل زنجیره

  • ArrayList: داده‌ها را در خانه‌هایِ پشتِ سرِ همِ حافظه (مثل پارکینگ) می‌گذارد.
  • LinkedList: هر داده را در یک "بسته" (Node) می‌گذارد که شامل خودِ داده و یک "آدرس" به بسته بعدی و قبلی است (مثل واگن‌های قطار).

چه زمانی از LinkedList استفاده کنیم؟ 🚦

در کاربردهای معمولی ArrayList بهتر است، اما در موارد زیر LinkedList برنده است:

  • اگر برنامه شما مدام در اول یا وسط لیست داده اضافه یا حذف می‌کند.
  • اگر به ساختارهای داده مثل Queue (صف) یا Stack (پشته) نیاز دارید.

متدهای اختصاصی

چون این کلاس اینترفیس Deque را هم پیاده کرده، متدهای مفیدی مثل این‌ها دارد:

  • addFirst() / addLast()
  • removeFirst() / removeLast()
  • getFirst() / getLast()

مقایسه سرعت (نبرد Big O):

جستجوی یک ایندکس خاص در ArrayList بسیار سریع (O(1)) است چون جاوا آدرس خانه را می‌داند. اما در LinkedList جاوا باید از واگنِ اول شروع کند و تک‌تک جلو برود تا به مقصد برسد (O(n)).

نکته حافظه: LinkedList به دلیل نگهداری ریفرنس‌های "قبلی" و "بعدی"، حافظه بیشتری نسبت به ArrayList برای همان مقدار داده مصرف می‌کند.
نکته کدنویسی: در اکثر پروژه‌های تجاری، 90% مواقع از ArrayList استفاده می‌کنیم مگر اینکه دلیلِ فنیِ بسیار محکمی برای LinkedList داشته باشیم.
<hr style="margin: 50px 0; border: 0; border-top: 1px dashed rgba(255,255,255,0.1);">

بخش تخصصی: مهندسی داده و بازدهی در جاوا ⚙️💎

در این بخش، به مفاهیمی می‌پردازیم که برای نوشتن برنامه‌های مقیاس‌پذیر و با کارایی بالا (High Performance) ضروری هستند.

۱. تحلیل پیچیدگی زمانی (Big O Notation)

انتخاب کالکشنِ اشتباه می‌تواند سرعت برنامه شما را از میلی‌ثانیه به دقیقه کاهش دهد. مثلاً پر کردن یک ArrayList با ۱ میلیون داده در صورتی که مدام از ابتدای آن حذف کنید، فاجعه‌بار است (O(n)). در حالی که LinkedList این کار را در زمان ثابت (O(1)) انجام می‌دهد. همیشه قبل از انتخاب ابزار، به نحوه دسترسی و تغییر داده‌ها فکر کنید.

۲. مدیریت حافظه (Memory Overhead)

اشیاءِ کالکشن در جاوا "ارزان" نیستند. یک HashMap یا LinkedList به ازای هر گره (Node) مقدار زیادی حافظه اضافی (Overhead) برای نگهداری ریفرنس‌های داخلی مصرف می‌کند. در سیستم‌هایی با رم محدود، گاهی اوقات استفاده از یک آرایه ساده یا کالکشن‌های تخصصیِ Primitive (مثل آنچه در کتابخانه‌های Trove یا FastUtil یافت می‌شود) گزینه‌ی بهتری است.

۳. امنیت نخ (Thread Safety) و کالکشن‌ها

اکثر کالکشن‌های پایه در جاوا (مثل ArrayList و HashMap) Thread-Safe نیستند. یعنی اگر دو نخ (Thread) همزمان سعی کنند در آن‌ها بنویسند، برنامه کراش می‌کند یا داده‌ها خراب می‌شوند. برای محیط‌های چندنخی، باید از ConcurrentHashMap یا کلاس‌های کمکی در Collections.synchronizedList استفاده کرد.

نکته طلایی: در جاوا، همیشه سعی کنید "نوعِ متغیر" را اینترفیس بگیرید و "نوعِ پیاده‌سازی" را کلاس واقعی. مثلاً: List<String> list = new ArrayList<>();. این کار تعویضِ پیاده‌سازی را در آینده بسیار راحت می‌کند.

تمرین‌های عملی

برای تثبیت یادگیری این درس تمرین‌های زیر را حل کنید

کار با سر و ته لیست Medium
سوال تمرین

یک LinkedList از نوع Integer به نام numbers بسازید. عدد 10 را اضافه کنید. سپس با متدهای مخصوص، عدد 5 را به ابتدا و عدد 20 را به انتها اضافه کنید. در نهایت لیست را چاپ کنید.

پاسخ تمرین
JAVA 
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<Integer> numbers = new LinkedList<Integer>();
    numbers.add(10);
    numbers.addFirst(5);
    numbers.addLast(20);
    System.out.println(numbers);
  }
}

آماده رفتن به درس بعدی هستید؟

این درس را به پایان رساندید و می‌توانید به درس بعدی بروید.

درس قبلی درس بعدی