شما روی پروژهای کار میکنید که هدفش توسعهی یک سامانهی زمانبندی قطار برای شبکهی راهآهنی پرتردد است.
از شما خواسته شده است که یک نمونهی اولیه برای مسیرهای قطار در سامانهی زمانبندی توسعه دهید. هر مسیر از دنبالهای از ایستگاههای قطار تشکیل میشود که قطار موردنظر در آنها توقف میکند.
تیم شما تصمیم گرفته است برای نمایش هر مسیر قطار در برنامهی زمانی، از یک «لیست پیوندی دوطرفه» استفاده کند. هر ایستگاه در مسیر قطار با یک گره در لیست پیوندی نمایش داده میشود.
لازم نیست نگران زمان رسیدن و حرکت در ایستگاهها باشید. هر ایستگاه بهسادگی با یک عدد نمایش داده میشود.
میتوان مسیرها را گسترش داد و به ابتدا یا انتهای یک مسیر ایستگاه افزود. همچنین میتوان با حذف ایستگاهها از ابتدا یا انتهای یک مسیر، آن را کوتاه کرد.
گاهی یک ایستگاه تعطیل میشود و در آن صورت باید آن ایستگاه از مسیر حذف شود، حتی اگر در ابتدا یا انتهای مسیر نباشد.
اندازهی یک مسیر نه با مسافتی که قطار میپیماید اندازهگیری میشود، بلکه با تعداد ایستگاههایی که در آنها توقف میکند.
لیست پیوندی یک ساختار دادهی بنیادی در علوم کامپیوتر است که اغلب در پیادهسازی ساختارهای دادهی دیگر به کار میرود. همانطور که از اسمش پیداست، لیستی از گرههاست که به هم پیوند خوردهاند. لیستی از «گرهها» است که هر گره به همسایه یا همسایههایش پیوند میخورد. در یک لیست پیوندی یکطرفه هر گره فقط به گره بعدی خود پیوند میخورد. در یک لیست پیوندی دوطرفه هر گره هم به گره قبلی و هم به گره بعدی خود پیوند میخورد.
اگر میخواهید دربارهی لیستهای پیوندی بیشتر بدانید، نگاهی به این مقاله بیندازید که آن را با تصویرهای زیبا توضیح میدهد.
شما یک پیادهسازی از لیست پیوندی دوطرفه خواهید نوشت.
یک Node پیادهسازی کنید که یک مقدار و اشارهگرهایی به گرههای بعدی و قبلی را نگه میدارد.
سپس یک LinkedList پیادهسازی کنید که ارجاعهایی به اولین و آخرین گره نگه میدارد و رابطی شبیه به آرایه برای افزودن و برداشتن عنصرها ارائه میدهد:
push (درج مقدار در انتها)؛pop (حذف مقدار از انتها)؛shift (حذف مقدار از ابتدا)؛unshift (درج مقدار در ابتدا)؛delete (حذف اولین گرهی منطبق)برای اینکه پیادهسازی شما ساده بماند، تستها شرایط خطا را پوشش نمیدهند.
بهطور خاص: pop یا shift هرگز روی یک لیست خالی فراخوانی نمیشوند.