لیست پیوندی دوطرفه
Doubly Linked Listلیست پیوندی دوطرفه یک ساختمان داده از دسته ساختمان داده است. این ساختمان داده، مقادیر و ارتباط بین آن‌ها را طوری سازمان‌دهی می‌کند که عملیات مهم هزینه قابل‌پیش‌بینی داشته باشند.
اول این مفهوم را در ذهن نگه دار
لیست پیوندی دوطرفه یک ساختمان داده از دسته ساختمان داده است. این ساختمان داده، مقادیر و ارتباط بین آن‌ها را طوری سازمان‌دهی می‌کند که عملیات مهم هزینه قابل‌پیش‌بینی داشته باشند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم لیست پیوندی دوطرفه ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع access O(n), known-node remove O(1) است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای لیست پیوندی دوطرفه هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
access O(n), known-node remove O(1)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای لیست پیوندی دوطرفه در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی access O(n), known-node remove O(1) و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
لیست پیوندی دوطرفه چه مسئله‌ای را حل می‌کند؟
لیست پیوندی دوطرفه یک ساختمان داده از دسته ساختمان داده است. این ساختمان داده، مقادیر و ارتباط بین آن‌ها را طوری سازمان‌دهی می‌کند که عملیات مهم هزینه قابل‌پیش‌بینی داشته باشند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا access O(n), known-node remove O(1) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.