Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Κ21.3 · Εισαγωγή στη μέση λίστας

Kahoot «Λίστες, Δέντρα and Beyond» · Δυσκολία ★★★ · multiple-choice · 39% σωστές απαντήσεις (93 απαντήσεις στο αμφιθέατρο) · Κεφάλαια: 21

Η προσθήκη ενός στοιχείου στη μέση μιας απλά συνδεδεμένης λίστας γίνεται σε χρόνο:

• O(n^2)
• O(f(x))
• O(n)
• O(1)

Συχνή παρανόηση

Το 26% επέλεξε O(1), μετρώντας μόνο την αλλαγή των δύο δεικτών και ξεχνώντας ότι πρώτα πρέπει να φτάσουμε στη μέση διατρέχοντας τη λίστα από την αρχή (άλλο ένα 32% διάλεξε το αστείο O(f(x))).

Υπόδειξη

Σε μια απλά συνδεδεμένη λίστα έχετε μόνο τον δείκτη στην κεφαλή· πόσα βήματα χρειάζονται για να φτάσετε στη μέση;

Αριθμός στον οδηγό: Κ21.3 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: kahoot-list-insert-middle · Σύνδεσμος: https://progintro.github.io/study/questions/kahoot/kahoot-list-insert-middle.html · Markdown (GitHub)