ساختار داده‌های ماندگار

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

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

ساختار داده‌ای کاملاً پایدار است اگر هر نگارش هم در دسترس باشد و هم تعدیل شود. اگر در اینجا عملیاتی بود که از ترکیب دو ورژن قبل یک ورژن جدید خلق می‌کرد ساختار داده‌ای پایدار ترکیبی فراخوانی شده بود. این ساختار دادها (پایدار)نامیده می‌شود. ساختاری که(پایدار) نیست گذرا نامیده می‌شود این ساختار داده‌ها بیشتر (منحصراً) در برنامه نویسی تابعی و منطقی رواج دارند و در یک برنامه کاملاً تابعی تمام داده‌ها تغییر ناپذیر هستند. بنابراین تمام ساختار دادها به صورت خود کار کاملاً پایدار هستند. ساختار داده‌ها ی پایدار نیز می‌توانند با بروز کردن داده‌ها در همین نسخه به وجود بیایند و این کار عموماً باعث می‌شود که زمان وفضای ذخیره کمتری ازنمونه کاملاً تابعی مورد استفاده قرار بگیرند. در حالیکه پایداری داده‌ها می‌تواند خیلی ساده از طریق کپی کردن صورت بگیرد اما این کار از لحاظ فضا و زمان کارایی ندارد چون بیشتر عملیاتی که انجام می‌شود تغییرات مختصری در ساختار داده‌ها به وجود می‌آورد. یک روش بهتر این است که از شباهت‌هایی که بین ورژن‌های جدید وقدیم وجود دارد استفاده کنیم تا از ساختار بین آن‌ها به نسبت مساوی بهره ببریم مانند استفاده از فرعی که در تعدادی از ساختارهای درختی موجود است. به هر حال از آنجایی که به سرعت امکان‌پذیر نیست که مشخص شود که چند تا ورژن قبلی در این کار وجود دارد که چه قسمت‌هایی از ساختار و به دلیل اینکه غالب اوقات مطلوب آن که ورژن‌های قدیمی منسوخ شده‌اند این امر مستلزم این است که با جمع‌آوری کلکسیون‌های منسوخ ایجاد شود. شاید ساده‌ترین ساختار داده‌ای ماندگار لیست linked-singly یا لیست based-cons باشد. یک لیست ساده فرم اهداف به وسیله هر یک مراجع حامل به لیست بعد است. این پایدار است زیرا ما می‌توانیم یک انتها از لیست را بگیریم، به معنی k آیتم قبلی برای k تا و اضافه کنیم به انتهای آن. این دنباله ممکن است دو نسخه‌ای نباشد ولی در عوض مناسب برای هر دو نسخه جدید و قدیم خواهد بود. تعدادی از منابع پایدار ساختار داده‌ها از قبیل درخت black-red و صف‌ها می‌توانند به راحتی با نسخه‌های پایدار متناسب شوند. یک نسخه پایدار آرایه‌ای ساختار داده‌ای Vlistتوسط phil bagwellتشریح شده‌است.