ساختار داده‌های مرتبط

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

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

اتصال به دو روش انجام می شود: با استفاده از تخصیص پویا، و با استفاده از اتصال فهرست آرایه.

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