لیست پیوندی
Linked Listلیست پیوندی داده‌ها را داخل Node نگه می‌دارد. هر Node علاوه بر مقدار، یک اشاره‌گر به Node بعدی دارد؛ بنابراین عناصر لازم نیست مثل Array پشت سر هم قرار بگیرند.
اول این مفهوم را در ذهن نگه دار
لیست پیوندی داده‌ها را داخل Node نگه می‌دارد. هر Node علاوه بر مقدار، یک اشاره‌گر به Node بعدی دارد؛ بنابراین عناصر لازم نیست مثل Array پشت سر هم قرار بگیرند.
چطور کار می‌کند؟ ساده و مرحله‌ای
لیست از Nodeای به نام head شروع می‌شود و برای رسیدن به عنصرهای بعدی باید اشاره‌گر next را قدم‌به‌قدم دنبال کنیم.
اضافه‌کردن در ابتدای لیست ارزان است چون فقط چند reference عوض می‌شود، اما دسترسی به عنصر شماره k مستقیم نیست و باید از ابتدا پیمایش کنیم.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
reference مربوط به head را نگه دار.
برای پیمایش current را روی current.next ببر.
در insertion/deletion قبل از تغییر referenceها، اتصال Nodeهای اطراف را دقیق نگه دار.
در 10 → 20 → 30، برای قرار دادن 15 بعد از 10 فقط اتصال‌های اطراف 10 و 15 تغییر می‌کنند.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
head = null;
prepend(value) {
this.head = new Node(value, this.head);
}
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
access O(n), head insert O(1)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
در مصاحبه آن را با Array مقایسه کن: insertion/deletion محلی ساده‌تر است، اما دسترسی با index دیگر O(1) نیست و locality حافظه هم معمولاً ضعیف‌تر است.
لیست پیوندی چه مسئله‌ای را حل می‌کند؟
لیست پیوندی داده‌ها را داخل Node نگه می‌دارد. هر Node علاوه بر مقدار، یک اشاره‌گر به Node بعدی دارد؛ بنابراین عناصر لازم نیست مثل Array پشت سر هم قرار بگیرند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا access O(n), head insert O(1) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.