Συνδεδεμένη λίστα

Οδηγίες

Υλοποίησε μια διπλά συνδεδεμένη λίστα.

Όπως ένας πίνακας, έτσι και μια συνδεδεμένη λίστα είναι μια απλή γραμμική δομή δεδομένων. Πολλοί συνηθισμένοι τύποι δεδομένων μπορούν να υλοποιηθούν με συνδεδεμένες λίστες, όπως οι ουρές, οι στοίβες και οι συσχετιστικοί πίνακες.

Μια συνδεδεμένη λίστα είναι μια συλλογή στοιχείων δεδομένων που ονομάζονται κόμβοι. Σε μια απλά συνδεδεμένη λίστα κάθε κόμβος κρατά μια τιμή και έναν σύνδεσμο προς τον επόμενο κόμβο. Σε μια διπλά συνδεδεμένη λίστα κάθε κόμβος κρατά επίσης έναν σύνδεσμο προς τον προηγούμενο κόμβο.

Θα γράψεις μια υλοποίηση μιας διπλά συνδεδεμένης λίστας. Υλοποίησε ένα Node που κρατά μια τιμή και δείκτες προς τον επόμενο και τον προηγούμενο κόμβο. Έπειτα υλοποίησε μια List που κρατά αναφορές στον πρώτο και τον τελευταίο κόμβο και προσφέρει μια διεπαφή παρόμοια με πίνακα για την προσθήκη και την αφαίρεση στοιχείων:

• push (εισάγει μια τιμή στο τέλος);
• pop (αφαιρεί την τιμή από το τέλος);
• shift (αφαιρεί την τιμή από την αρχή).
• unshift (εισάγει μια τιμή στην αρχή);

Για να κρατήσεις την υλοποίησή σου απλή, τα tests δεν θα καλύπτουν συνθήκες σφάλματος. Συγκεκριμένα: το pop ή το shift δεν θα κληθεί ποτέ σε μια κενή λίστα.

Διάβασε περισσότερα για τις συνδεδεμένες λίστες στη Βικιπαίδεια.