ArrayList در مقابل LinkedList

مقدمه

Collections Framework دو پیاده‌سازی از رابطه‌ی List ارائه می‌دهد: ArrayList و LinkedList. آیا یکی از دیگری بهتر است؟ کدام را باید در برنامه‌ی خود انتخاب کنید؟

این بخش تفاوت‌های هر دو پیاده‌سازی را بررسی می‌کند. عملکرد عملیات ارائه‌شده و مصرف حافظه‌ی این پیاده‌سازی‌ها را خواهید دید. در نهایت قادر به انتخاب صحیح برای مورد استفاده‌ی خود خواهید بود.

پیچیدگی الگوریتم

پیچیدگی الگوریتم برای برخی عملیات رایج لیست

نقطه‌ی شروع تمام بحث‌ها درباره‌ی تفاوت لیست‌های مبتنی بر آرایه و لیست‌های پیوندی، پیچیدگی الگوریتم است که با نماد O(n) اندازه‌گیری می‌شود. پیچیدگی عملیات مختلف رابطه‌ی List بسته به پیاده‌سازی متفاوت است و معمولاً O(1)، O(n) یا حتی O(ln(n)) توصیف می‌شود.

بیایید این پیچیدگی را برای سه عملیات پایه‌ای مقایسه کنیم:

• دریافت عنصر از لیست. دریافت از ابتدای لیست، انتهای لیست و وسط لیست را مقایسه می‌کنیم.
• پیمایش عناصر لیست. دو الگو وجود دارد: پیمایش با ایندکس یا با Iterator.
• درج عنصر. درج در ابتدای لیست، وسط لیست و انتهای لیست را مقایسه می‌کنیم.

ما جایگزینی یک عنصر با عنصر دیگر را مقایسه نمی‌کنیم چون در واقع همان خواندن عنصر مورد نظر است.

جدول پیچیدگی این عملیات:

عملیات	ArrayList	LinkedList
خواندن اول	O(1)	O(1)
خواندن آخر	O(1)	O(1)
خواندن وسط	O(1)	O(n)
اضافه کردن در انتها	O(1)	O(1)
درج در ابتدا	O(n)	O(1)
درج در وسط	O(n)	O(n)

تفاوت‌های زیادی وجود ندارد: LinkedList فقط در دو عملیات O(n) است: خواندن وسط و درج در وسط.

دو نکته‌ی قابل توجه:

اول: خواندن آخر در LinkedList O(1) است چون این پیاده‌سازی مرجع مستقیمی به آخرین عنصر لیست دارد.

دوم: عملیات روی ArrayList و LinkedList یکسان نیستند. برای ArrayList عملیات شامل جابه‌جایی یک آرایه‌ی n بایتی است، در حالی که برای LinkedList شامل پیمایش n مرجع است.

پیچیدگی الگوریتم چه معنایی دارد؟

نماد O(n) به این معناست که پس از یک آستانه‌ی خاص، زمان پردازش الگوریتم با مقدار داده‌ها (n) متناسب است. یعنی اگر مقدار داده را دو برابر کنید، زمان پردازش هم تقریباً دو برابر می‌شود. برای پیچیدگی O(1)، الگوریتم به مقدار داده وابسته نیست. این منطقی است: خواندن اولین عنصر لیست به اندازه‌ی لیست وابسته نیست.

این نماد رفتار مجانبی (Asymptotic) الگوریتم شما را نشان می‌دهد. نکته‌ی مهم عبارت پس از یک آستانه‌ی خاص است. مقدار این آستانه چقدر است؟

فرض کنید الگوریتمی دقیقاً a*n + b عملیات انجام می‌دهد. اگر a = 10 و b = 1 باشد، فرض کردن اجرای الگوریتم در n برای ۱۰ یا تعداد بیشتر عنصر خطای کمتر از ۱٪ دارد. اما اگر a = 1 و b = 10 باشد، این فرض فقط برای ۱۰۰۰ یا تعداد بیشتر عنصر معتبر است.

نکته این است: دانستن اینکه پیچیدگی O(n) است جالب است، اما باید بدانید چگونه روی مورد استفاده‌ی شما اعمال می‌شود. اگر آستانه ۱۰۰۰ باشد و شما ۱۰۰ عنصر پردازش کنید، این فرمول صدق نمی‌کند.

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

مکانیزم‌های پنهان داخلی وجود دارد که بر عملکرد تأثیر می‌گذارد و فراتر از پیچیدگی ساده‌ی الگوریتم است. بقیه‌ی این بخش تمام آن‌ها را بررسی می‌کند.

خواندن عناصر از یک لیست

بیایید یک بنچمارک ایجاد کنیم که شامل خواندن عناصر از یک لیست است:

• اولین عنصر
• سپس آخرین عنصر
• سپس عنصر وسط

چون انتظار نتایج متفاوت با اندازه‌های مختلف لیست را داریم، بنچمارک را برای اندازه‌های مختلف اجرا می‌کنیم.

تمام بنچمارک‌های این صفحه با JMH انجام شده‌اند؛ تنها ابزار مناسب برای اندازه‌گیری قابل اعتماد عملکرد.

خواندن اولین و آخرین عنصر لیست

کد بنچمارک به شکل زیر است. برای هر دو ArrayList و LinkedList و برای اندازه‌های مختلف لیست اجرا می‌شود. نتیجه به JMH blackhole ارسال می‌شود تا مطمئن شویم هیچ بهینه‌سازی JVM رخ نمی‌دهد.

List<Integer> ints = ...; // varies in size

int LAST = ints.size() - 1;
int MIDDLE = ints.size()/2;

// 1st bench
ints.get(0);

// 2nd bench
ints.get(LAST);

// 3rd bench
ints.get(MIDDLE);

می‌توانید اعداد این صفحه را با هم مقایسه کنید چون تمام بنچمارک‌ها روی یک ماشین اجرا شده‌اند. البته بعید است روی ماشین خودتان همان اعداد را بگیرید. توصیه می‌شود محاسبات دقیق برنامه‌ی خود را در نزدیک‌ترین شرایط به محیط production بسنجید.

نتایج عملیات خواندن اول:

ArrayList     SIZE  Score   Error  Units
Read first      10  1.181 ± 0.022  ns/op
Read first     100  1.200 ± 0.041  ns/op
Read first    1000  1.167 ± 0.009  ns/op
Read first   10000  1.174 ± 0.014  ns/op

LinkedList    SIZE  Score   Error  Units
Read first      10  1.127 ± 0.030  ns/op
Read first     100  1.107 ± 0.008  ns/op
Read first    1000  1.121 ± 0.016  ns/op
Read first   10000  1.119 ± 0.014  ns/op

نتایج برای هر دو پیاده‌سازی یکسان است و به اندازه‌ی لیست وابسته نیست.

نتایج عملیات خواندن آخر:

ArrayList     SIZE  Score   Error  Units
Read last       10  1.248 ± 0.020  ns/op
Read last      100  1.232 ± 0.035  ns/op
Read last     1000  1.240 ± 0.019  ns/op
Read last    10000  1.254 ± 0.040  ns/op

LinkedList    SIZE  Score   Error  Units
Read last       10  1.493 ± 0.040  ns/op
Read last      100  1.467 ± 0.019  ns/op
Read last     1000  1.475 ± 0.019  ns/op
Read last    10000  1.484 ± 0.042  ns/op

تفاوت جزئی وجود دارد که افت عملکرد اندکی در LinkedList نشان می‌دهد. این تفاوت بسیار کوچک و غیرمهم است.

خواندن عنصر وسط لیست

وضعیت هنگام تلاش برای رسیدن به وسط لیست متفاوت است.

ArrayList     SIZE  Score   Error  Units
Read middle     10  1.571 ± 0.055  ns/op
Read middle    100  1.616 ± 0.073  ns/op
Read middle   1000  1.543 ± 0.018  ns/op
Read middle  10000  1.537 ± 0.010  ns/op

LinkedList    SIZE     Score     Error  Units
Read middle     10     3.211 ±   0.023  ns/op
Read middle    100    31.118 ±   0.321  ns/op
Read middle   1000   566.079 ±   8.696  ns/op
Read middle  10000  7836.099 ± 902.666  ns/op

رسیدن به عنصر وسط در آرایه تقریباً مثل رسیدن به آخر آن است و به اندازه‌ی آرایه وابسته نیست.

وضعیت برای LinkedList متفاوت است. رسیدن به عنصر وسط پرهزینه است و به تعداد عناصر لیست وابسته است. رسیدن به آخر سریع بود چون LinkedList مرجع مستقیم به اولین و آخرین گره‌ی لیست پیوندی داخلی دارد.

برای درک اینکه چرا رسیدن به عنصر وسط پرهزینه است، باید ساختار لیست پیوندی را در نظر بگیرید.

[دیاگرام: ساختار داخلی LinkedList - مجموعه‌ای از اشیاء Node که هرکدام سه مرجع دارند: next، previous و مرجع به شیء حمل‌شده]

پیاده‌سازی Java لیست پیوندی مجموعه‌ای از اشیاء Node است. هر Node سه مرجع دارد: یکی به گره‌ی بعدی، یکی به گره‌ی قبلی و سومی به شیء حمل‌شده. پس در واقع یک لیست پیوندی دوطرفه است. علاوه بر این، کلاس LinkedList دو مرجع دیگر هم دارد: یکی به اولین گره و دیگری به آخرین گره. رسیدن به اولین یا آخرین گره سریع است. اما خواندن گره‌ی وسط پرهزینه‌ست چون پیاده‌سازی باید تمام مراجع next را بخواند تا به گره مورد نیاز برسد. این همان چیزی است که در بنچمارک مشاهده می‌کنید.

خواندن گره‌ی وسط بدترین حالت است. چون مرجعی به اولین و آخرین گره دارد، پیاده‌سازی همیشه کوتاه‌ترین مسیر را انتخاب می‌کند.

این افت عملکرد به اثر Pointer Chasing مربوط می‌شود. خواندن مراجع باعث بارگذاری حافظه‌ی مرجع‌شده در کش CPU می‌شود. اگر آن بخش حافظه از قبل در کش باشد، فوراً دریافت می‌شود. اگر نباشد، Cache Miss رخ می‌دهد و باید از حافظه‌ی اصلی دریافت شود که زمان‌بر است.

می‌توانید این موضوع را با ایجاد لیست پیوندی به شکل خاصی مشاهده کنید. در بنچمارک قبلی، لیست پیوندی با کد زیر ایجاد شده (با stream):

var ints = 
   IntStream.range(0, LIST_SIZE)
            .boxed()
            .collect(Collectors.toCollection(LinkedList::new));

چون در یک برنامه‌ی واقعی نیستیم، احتمالاً تمام اشیاء Node این لیست پیوندی در حافظه نزدیک به هم ذخیره شده‌اند. پس وقتی مرجع next یک گره را می‌خوانید، احتمالاً این مرجع از قبل در کش است.

فرض کنید روش دیگری برای ایجاد لیست پیوندی داریم که مطمئن شویم تمام گره‌ها در حافظه از هم جدا هستند. در مثال زیر، تعدادی شیء Node بین دو شیء Node لیست اصلی ایجاد می‌کنیم و در طول بنچمارک مرجعی به این لیست نگه می‌داریم تا garbage collector اشیا را جابه‌جا نکند:

var ints = new LinkedList<>();
var intsOther = new LinkedList<>();
for (int i = 0; i < LIST_SIZE; i++) {
    ints.add(i);
    for (int k = 0; k < SPARSE_INDEX; k++) {
        intsOther.add(k);
    }
}

نتایج:

LinkedList   SIZE  SPARSE    Score    Error  Units
Read middle  1000       0  561.428 ±  4.853  ns/op
Read middle  1000       1  602.401 ± 17.126  ns/op
Read middle  1000      10  944.997 ± 31.920  ns/op
Read middle  1000     100 1509.282 ± 28.749  ns/op

Pointer Chasing واقعاً عملکرد خواندن مقادیر تصادفی در LinkedList را تحت تأثیر قرار می‌دهد. لیست پیوندی با گره‌های توزیع‌شده‌ی تصادفی در حافظه سه برابر کندتر از همان لیست با گره‌های پیوسته است. احتمالاً در برنامه‌ای که مدام عناصر را اضافه و حذف می‌کند، همین وضعیت پیش خواهد آمد.

پیمایش عناصر یک لیست

پیمایش با ایندکس و Iterator

پیمایش عناصر یک لیست با دو الگو قابل پیاده‌سازی است. اولی الگوی کلاسیک Collections Framework با Iterator است. دومی استفاده از ایندکس. پیمایش گره‌های LinkedList احتمالاً از Pointer Chasing رنج می‌برد چون رسیدن به گره بعدی شامل پیمایش یک مرجع است.

الگوی اول با ایندکس:

var ints = ...; // LinkedList or ArrayList
for (var index = 0; index < ints.size(); index++) {
   var v = ints.get(index);
   // pass v to the blackhole
}

الگوی دوم با Iterator. توجه کنید در مثال زیر که از الگوی for-each استفاده می‌کند، کامپایلر در byte code برای شما iterator می‌سازد.

for (var v: ints) {
   // pass v to the blackhole
}

برای ArrayList هر دو الگو تقریباً یکسان هستند. استفاده از ایندکس کمی پرهزینه‌تر است چون باید ایندکس را مدیریت کنید. ممکن است تعجب کنید چرا افزایش یک int پرهزینه‌تر از مدیریت یک iterator است. الگوی for-each iterator را در کد منبع شما نمایان نمی‌کند و JIT compiler می‌تواند آن را بهینه کند و از ایجاد این iterator جلوگیری کند. در نهایت کد بسیار سریع‌تری خواهید داشت.

ArrayList         SIZE    Score   Error Units
Iterate iterator  1000    1.447 ± 0.024 us/op
Iterate index     1000    1.986 ± 0.045 us/op

برای LinkedList وضعیت متفاوت است. استفاده از iterator پرهزینه‌تر است چون Pointer Chasing. در ArrayList کافی است آفستی به آدرسی در heap اضافه کنید، اما در LinkedList باید یک مرجع را دنبال کنید با احتمال cache miss.

استفاده از ایندکس بسیار پرهزینه و نادانانه است. پیمایش با ایندکس یعنی برای هر عنصر، از ابتدا شروع و index بار به گره بعدی بروید. پیچیدگی O(n²) است. هرگز این الگو را روی LinkedList استفاده نکنید. پیمایش لیست ۱۰۰۰ عنصری حدود نیم میلی‌ثانیه طول می‌کشد، در حالی که با iterator فقط ۴ میکروثانیه است.

LinkedList        SIZE    Score   Error Units
Iterate iterator  1000    4.950 ± 0.116 us/op
Iterate index     1000  584.889 ± 4.396 us/op

پیمایش روی یک کپی از LinkedList

پیمایش روی LinkedList دو برابر ArrayList هزینه دارد. ممکن است سوال پیش بیاید آیا کپی کردن LinkedList به یک لیست مبتنی بر آرایه قبل از پیمایش کارآمدتر نیست. این فرآیند حافظه مصرف می‌کند و اگر لیست در حین پیمایش تغییر کند مشکل ایجاد می‌شود.

الگوی زیر و بنچمارک آن:

var ints = 
   IntStream.range(0, 1_000)
            .boxed()
            .collection(Collection.toCollection(LinkedList::new));

var copyOfInts = ints.stream().toList();
for (var v: copyOfInts) {
   // pass v to the blackhole
}

نتیجه نشان می‌دهد برای لیست ۱۰۰۰ عنصری، کپی کردن لیست فقط ۴٪ زمان پیمایش را مصرف می‌کند. اگر هزینه‌ی حافظه قابل قبول است و چندین بار پیمایش یا دسترسی تصادفی دارید، کپی کردن لیست پیوندی به لیست مبتنی بر آرایه خیلی سریع جواب می‌دهد.

از Stream.toList() استفاده می‌کنیم که لیست غیرقابل تغییر ایجاد می‌کند و با ایجاد آرایه‌ی با اندازه‌ی مناسب از ابتدا بهینه شده است.

LinkedList           SIZE  ITERATION    Score    Error  Units
toList then iterate  1000          1    5.182 ±  0.347  us/op
toList then iterate  1000         10   14.031 ±  0.793  us/op
toList then iterate  1000        100  100.104 ±  7.422  us/op

Pointer Chasing و Cache Miss‌ها می‌توانند عملکرد شما را نابود کنند. این تأثیر روی هر داده‌ساختار مبتنی بر مرجع اثر می‌گذارد: لیست پیوندی، درخت‌های Trie، درخت‌های دودویی، درخت‌های Red-Black، Skip List و تا حد کمتری Hash Map.

درج عناصر در یک لیست

لیست‌های پیوندی به خاطر عملکرد عالی‌شان در درج عنصر در یک موقعیت تصادفی شناخته شده‌اند. درج فقط شامل تغییر مرجع next گره‌ی قبلی و مرجع previous گره‌ی بعدی است. به نظر کم‌هزینه می‌آید. اما باید به گره‌ی قبلی و بعدی دسترسی داشته باشید.

از طرف دیگر، درج در لیست مبتنی بر آرایه پیچیده‌تر است. باید بخش سمت راست آرایه یک خانه به سمت راست جابه‌جا شود.

[دیاگرام: درج عنصر در آرایه - نمایش جابه‌جایی عناصر برای باز کردن جا]

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

درج عناصر در LinkedList

سه حالت: درج در ابتدا، وسط و انتهای لیست. انتظار داریم چون LinkedList مرجع مستقیم به اولین و آخرین گره دارد، تفاوت زیادی بین ابتدا و انتها نباشد و به اندازه‌ی لیست وابسته نباشد. اما درج در وسط پرهزینه‌تر باشد و با رشد لیست افزایش یابد.

درج در ابتدا. تفاوت با رشد اندازه‌ی لیست قابل توجه نیست:

LinkedList      SIZE    Score    Error  Units
Insert first      10    7.002  ± 0.306  ns/op
Insert first     100    7.126  ± 0.424  ns/op
Insert first    1000    7.561  ± 0.371  ns/op
Insert first   10000    7.738  ± 0.614  ns/op

اضافه کردن در انتها هم همین‌طور. تفاوت با درج در ابتدا همچنان کوچک است:

LinkedList      SIZE    Score    Error  Units
Adding            10    9.135  ± 0.137  ns/op
Adding           100    9.076  ± 0.082  ns/op
Adding          1000    9.795  ± 0.399  ns/op
Adding         10000    9.549  ± 0.202  ns/op

درج در وسط با ایندکس واقعاً پرهزینه‌تر است و هزینه‌اش با رشد لیست افزایش می‌یابد. این با لیست پیوندی متراکم (Sparse) اندازه‌گیری شده:

LinkedList      SIZE      Score     Error  Units
Insert middle     10     10.641 ±   0.679  ns/op
Insert middle    100     49.122 ±   1.808  ns/op
Insert middle   1000    584.870 ±   6.925  ns/op
Insert middle  10000  46157.961 ± 379.327  ns/op

درج عناصر در ArrayList

علاوه بر جابه‌جایی آرایه، باید تغییر اندازه (resizing) آرایه را هم در نظر بگیرید. نمی‌توانید عنصری در آرایه‌ی پر اضافه کنید. ArrayList آرایه‌ی کامل را به آرایه‌ی بزرگ‌تری کپی می‌کند و سپس عنصر را اضافه می‌کند. اندازه‌ی جدید با ضریب ۱.۵ رشد می‌کند. بنابراین در حلقه‌ی تکرار، این عملیات رشد کمتر رخ می‌دهد.

دو حالت را بررسی می‌کنیم: درج در آرایه‌ی جا‌دار و درج در آرایه‌ی پر.

وقتی آرایه جا دارد، انتظارات برآورده می‌شود. درج در انتها تقریباً به اندازه‌ی آرایه وابسته نیست. افزایش زمان احتمالاً به خاطر cache miss در انتهای آرایه‌ی بزرگ است. تفاوت بین آرایه‌ی ۱,۰۰۰ و ۱۰,۰۰۰ عنصری قابل توجه نیست. درج در وسط پرهزینه‌تر است. و درج در ابتدا (پرهزینه‌ترین) دو برابر عناصر را جابه‌جا می‌کند:

ArrayList  SIZE    Score    Error  Units
Adding       10    2.215  ± 0.053  ns/op
Adding      100    2.184  ± 0.027  ns/op
Adding     1000    5.607  ± 0.856  ns/op
Adding    10000    5.240  ± 0.777  ns/op

ArrayList        SIZE    Score     Error  Units
Insert middle     10   23.708  ±  0.370  ns/op
Insert middle    100   25.399  ±  0.241  ns/op
Insert middle   1000   56.061  ±  0.840  ns/op
Insert middle  10000  294.457  ±  4.689  ns/op

ArrayList       SIZE    Score    Error  Units
Insert first     10   22.380  ±  0.266  ns/op
Insert first    100   26.929  ±  0.385  ns/op
Insert first   1000   78.958  ±  1.429  ns/op
Insert first  10000  717.892  ±  9.242  ns/op

وقتی آرایه جا ندارد، ArrayList آرایه‌ی داخلی را به آرایه‌ی بزرگ‌تری کپی می‌کند. این عملیات در بنچمارک‌های قبلی فعال نشده بود، اما می‌توانیم با آرایه‌ی پر آن را بسنجیم:

ArrayList                  SIZE       Score    Error  Units
Adding in a full array      10      19.300 ±    2.953  ns/op
Adding in a full array     100      45.488 ±    3.922  ns/op
Adding in a full array    1000     432.351 ±   46.055  ns/op
Adding in a full array   10000    4140.668 ±  329.160  ns/op

چون هزینه‌ی تغییر اندازه بسیار بالاتر از هزینه‌ی درج است، تفاوت کمی بین درج در وسط و ابتدا انتظار می‌رود:

ArrayList                        SIZE     Score    Error  Units
Insert middle in a full array     10    39.334 ±    1.588  ns/op
Insert middle in a full array    100    61.037 ±    2.130  ns/op
Insert middle in a full array   1000   451.471 ±   27.247  ns/op
Insert middle in a full array  10000  4638.632 ±  360.694  ns/op

ArrayList                       SIZE     Score     Error  Units
Insert first in a full array     10    28.288 ±    0.656  ns/op
Insert first in a full array    100    52.935 ±    2.457  ns/op
Insert first in a full array   1000   452.179 ±   37.434  ns/op
Insert first in a full array  10000  4762.783 ±  133.468  ns/op

مقایسه‌ی درج در LinkedList و ArrayList

همان‌طور که می‌بینید، ArrayList در تمام عملیات به جز یکی از LinkedList بهتر عمل می‌کند. غیرمنتظره است چون از نظر الگوریتمی LinkedList بهتر است. اما Pointer Chasing روی سخت‌افزار مدرن این الگوریتم کارآمد را ناکارآمد می‌سازد.

دلایل عملکرد بهتر LinkedList در درج ابتدای لیست:

1. زمان درج به اندازه‌ی لیست وابسته نیست
2. چون مرجع مستقیم به اولین عنصر وجود دارد، Pointer Chasing فقط یک بار رخ می‌دهد

حتی اگر قیمت تغییر اندازه بالا باشد، چون به ندرت رخ می‌دهد، تأثیرش میانگین می‌شود. با ایجاد ArrayList با اندازه‌ی مناسب می‌توانید از آن اجتناب کنید. نادرست است که هزینه‌ی تغییر اندازه دلیلی برای ترجیح LinkedList بر ArrayList باشد.

بنابراین دو مورد استفاده وجود دارد که LinkedList جالب است: عملیات در ابتدا یا انتهای لیست. LinkedList پیاده‌سازی خوبی برای Stack یا Queue است. اما برای لیست‌های معمولی نه. تقریباً همیشه ArrayList عملکرد بهتری دارد. اگر به Deque نیاز دارید، ArrayDeque انتخاب بهتری است.

تحلیل مصرف حافظه‌ی LinkedList و ArrayList

ArrayList و LinkedList از نظر حافظه چگونه عمل می‌کنند؟ JVMهای مختلف ممکن است حافظه را متفاوت مدیریت کنند.

از ابزار JOL OpenJDK برای اندازه‌گیری حافظه استفاده می‌کنیم.

به‌طور کلی، ذخیره‌ی تعداد مشخصی شیء در LinkedList به حافظه‌ی بسیار بیشتری نسبت به ArrayList نیاز دارد. دلیل: هر مرجع در LinkedList در یک شیء Node با دو مرجع اضافی و header ذخیره می‌شود — معمولاً ۲۴ بایت.

برای ۱۰۰۰ شیء، LinkedList کمی بیش از ۲۴ کیلوبایت و ArrayList کمی کمتر از ۵ کیلوبایت مصرف می‌کند.

یک حالت استثنا: اگر فقط یک شیء داشته باشید، آرایه‌ی داخلی ArrayList ممکن است ۱۰ عنصری باشد. در این صورت ArrayList (۸۰ بایت) بیشتر از LinkedList (۵۶ بایت) حافظه مصرف می‌کند.

الگوهای مختلف ایجاد ArrayList با یک عنصر:

var intsV1 = new ArrayList<Integer>();
intsV1.add(1); // wraps an array of size 10

var intsV2 = new ArrayList<Integer>();
intsV2.addAll(List.of(1)); // wraps an array of size 10

var intsV3 = new ArrayList<Integer>(List.of(1)); // wraps an array of size 1

راه‌حل‌ها: استفاده از List.of() یا ArrayList.trimToSize(). List.of() فقط ۲۶ بایت برای یک عنصر مصرف می‌کند.

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

خوشبختانه متد ArrayList.trimToSize() ظرفیت آرایه‌ی داخلی را به اندازه‌ی لیست کوچک می‌کند. با فراخوانی این متد روی لیست تک‌عنصری، از LinkedList هم کوچک‌تر می‌شود.

	مصرف حافظه برای ۱ عنصر
ArrayList	۷۶ بایت
ArrayList	۴۴ بایت (بعد از trimToSize())
LinkedList	۵۶ بایت
List.of()	۲۶ بایت

	مصرف حافظه برای ۱,۰۰۰ عنصر
ArrayList	۴,۹۷۶ بایت
LinkedList	۲۴,۰۳۲ بایت

حتی وقتی ArrayList آرایه‌ی نیمه‌خالی دارد، باز هم بسیار کمتر از LinkedList حافظه مصرف می‌کند. مدیریت اشیاء Node هر کدام ۲۴ بایت هزینه دارد. بدترین حالت هنگام تغییر اندازه است که ArrayList دو آرایه دارد. حتی در این حالت هم کمتر از LinkedList مصرف می‌کند.

چند عنصر می‌توانید در یک Heap مشخص ذخیره کنید؟

LinkedList برای هر عنصر یک شیء Node با اندازه‌ی ۲۴ بایت نیاز دارد. حداکثر H/24 عنصر.

برای ArrayList پیچیده‌تر است. اگر آرایه پر باشد H/4 عنصر. اگر تازه تغییر اندازه شده باشد، ۳۳٪ استفاده نشده و میانگین ۶ بایت به ازای هر شیء. حتی در بدترین حالت (تغییر اندازه) ۱۰ بایت به ازای هر شیء — هنوز ۲.۴ برابر از LinkedList کارآمدتر.

کدام پیاده‌سازی را باید انتخاب کنید؟

ArrayList پیاده‌سازی خوبی است که تقریباً در تمام عملیات لیستی کلاسیک از LinkedList بهتر عمل می‌کند. LinkedList ساختاری مبتنی بر اشاره‌گر است که از Pointer Chasing رنج می‌برد. پیمایش پرهزینه است، دریافت عنصر با ایندکس پرهزینه است و این روی تمام عملیات کلاسیک اثر می‌گذارد.

ArrayList در درج به خاطر System.arraycopy() خیلی خوب نیست اما باز هم معمولاً بهتر است. تغییر اندازه پرهزینه است اما به ندرت رخ می‌دهد و با ایجاد ArrayList با اندازه‌ی مناسب قابل اجتناب است.

تنها حالتی که LinkedList بهتر عمل می‌کند: دسترسی به اولین یا آخرین عنصر. یعنی وقتی واقعاً به Stack یا Queue نیاز دارید. LinkedList رابطه‌ی Queue و Deque را پیاده‌سازی می‌کند. اگر به Deque نیاز دارید، ArrayDeque انتخاب بهتری است.

از نظر حافظه، LinkedList بسیار بیشتر مصرف می‌کند. استثنا: لیست تک‌عنصری. List.of() یا ArrayList.trimToSize() این مشکل را حل می‌کنند.

در محیط‌های محدود حافظه‌ای، ایجاد ArrayList با ظرفیت اولیه‌ی ۲ خوب عمل می‌کند: فقط ۴۸ بایت برای ۰، ۱ یا ۲ عنصر. در تمام اندازه‌های غیرصفر از LinkedList کوچک‌تر است.

	ArrayList با ظرفیت ۲	LinkedList	ArrayList پیش‌فرض	ArrayList trimmed
۰	۴۰	۳۲	۴۰	۴۰
۱	۴۸	۵۶	۸۰	۴۸
۲	۴۸	۸۰	۸۰	۴۸
۳	۵۶	۱۰۴	۸۰	۵۶
۴	۵۶	۱۲۸	۸۰	۵۶
۵	۶۴	۱۵۲	۸۰	۶۴
۶	۶۴	۱۷۶	۸۰	۶۴
۷	۸۰	۲۰۰	۸۰	۷۲
۸	۸۰	۲۲۴	۸۰	۷۲
۹	۸۰	۲۴۸	۸۰	۸۰
۱۰	۹۶	۲۷۲	۸۰	۸۰

نکته‌ی نهایی: ArrayList هرگز خودکار کوچک نمی‌شود. فراخوانی remove یا clear آرایه‌ی داخلی را کپی نمی‌کند. ArrayList.trimToSize() این کار را انجام می‌دهد.