لیست پیوندی

دستورالعمل‌ها

یک لیست پیوندی دوطرفه پیاده‌سازی کنید.

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

لیست پیوندی مجموعه‌ای از عناصر داده است که به آن‌ها «گره» می‌گویند. در یک «لیست پیوندی یک‌طرفه»، هر گره یک مقدار و پیوندی به گره‌ی بعدی نگه می‌دارد. در یک «لیست پیوندی دوطرفه»، هر گره پیوندی به گره‌ی قبلی هم نگه می‌دارد.

شما یک پیاده‌سازی از لیست پیوندی دوطرفه خواهید نوشت. یک Node پیاده‌سازی کنید که یک مقدار و اشاره‌گرهایی به گره‌های بعدی و قبلی نگه دارد. سپس یک List پیاده‌سازی کنید که ارجاع‌هایی به گره‌ی اول و آخر نگه می‌دارد و یک رابط شبیه به آرایه برای افزودن و حذف عنصرها ارائه می‌دهد:

• push (مقدار را در انتها درج می‌کند)؛
• pop (مقدار را از انتها حذف می‌کند)؛
• shift (مقدار را از ابتدا حذف می‌کند).
• unshift (مقدار را در ابتدا درج می‌کند)؛

برای اینکه پیاده‌سازی‌تان ساده بماند، تست‌ها شرایط خطا را پوشش نمی‌دهند. به‌طور مشخص: pop یا shift هرگز روی یک لیست خالی فراخوانی نمی‌شوند.

درباره‌ی لیست‌های پیوندی در ویکی‌پدیا بیشتر بخوانید.