لیست پیوندی چیست و چه تفاوتی با آرایه دارد

---

لیست پیوندی (Linked List) و آرایه (Array) دو ساختار داده اساسی برای ذخیره و سازماندهی مجموعه‌ای از عناصر هستند. با وجود اینکه هر دو این امکان را فراهم می‌کنند، تفاوت‌های کلیدی در نحوه ذخیره‌سازی، دسترسی، و مدیریت حافظه دارند.

**آرایه (Array):**

* **تعریف:** یک مجموعه مرتب از عناصر هم‌نوع است که در مکان‌های متوالی حافظه ذخیره می‌شوند.
* **ذخیره سازی:** عناصر آرایه به صورت پیوسته در حافظه قرار می‌گیرند.
* **دسترسی:** دسترسی به عناصر آرایه از طریق اندیس (index) انجام می‌شود. این دسترسی **تصادفی** (random access) است، به این معنی که می‌توان به هر عنصر با استفاده از اندیس آن در زمان ثابت (O(1)) دسترسی پیدا کرد.
* **اندازه:** اندازه آرایه معمولاً در زمان ایجاد آن تعیین می‌شود (اندازه ثابت) یا ممکن است در زبان‌های برنامه‌نویسی پیشرفته‌تر، آرایه‌های پویا وجود داشته باشند که قابلیت تغییر اندازه دارند.
* **افزودن/حذف عناصر:** افزودن یا حذف عنصر در وسط آرایه نیازمند شیفت دادن عناصر دیگر است که می‌تواند زمان‌بر باشد (O(n)).
* **مزایا:**
* دسترسی سریع به عناصر (O(1))
* استفاده بهینه از حافظه (به دلیل پیوستگی)
* **معایب:**
* اندازه ثابت (در آرایه‌های ثابت)
* افزودن و حذف عناصر در وسط آرایه زمان‌بر است.
* نیاز به تخصیص فضای پیوسته در حافظه که ممکن است در برخی موارد مشکل‌ساز باشد.

**لیست پیوندی (Linked List):**

* **تعریف:** یک مجموعه از گره‌ها (nodes) است که هر گره حاوی داده و یک اشاره‌گر (pointer) به گره بعدی در لیست است.
* **ذخیره سازی:** گره‌های لیست پیوندی لزوماً در مکان‌های متوالی حافظه ذخیره نمی‌شوند. هر گره به گره بعدی اشاره می‌کند.
* **دسترسی:** دسترسی به عناصر لیست پیوندی به صورت **ترتیبی** (sequential access) است. برای دسترسی به عنصر nام، باید از ابتدای لیست شروع کرده و از طریق اشاره‌گرها به گره مورد نظر رسید. این دسترسی زمان‌بر است (O(n)).
* **اندازه:** اندازه لیست پیوندی پویا است و می‌تواند در زمان اجرا تغییر کند.
* **افزودن/حذف عناصر:** افزودن یا حذف عناصر در لیست پیوندی (به خصوص در ابتدا یا انتها) معمولاً سریع‌تر از آرایه است، زیرا فقط نیاز به تغییر اشاره‌گرها است (O(1) اگر اشاره‌گر به محل درج/حذف وجود داشته باشد).
* **مزایا:**
* اندازه پویا و قابلیت تغییر آسان.
* افزودن و حذف عناصر به خصوص در ابتدا یا انتها سریع‌تر از آرایه است.
* عدم نیاز به تخصیص فضای پیوسته در حافظه.
* **معایب:**
* دسترسی کندتر به عناصر (O(n)).
* مصرف حافظه بیشتر به دلیل نیاز به ذخیره اشاره‌گرها.
* پیاده‌سازی پیچیده‌تر نسبت به آرایه.

**جدول مقایسه‌ای:**

| ویژگی | آرایه (Array) | لیست پیوندی (Linked List