ΘΕΜΑ: Πως λειτουργεί η λίστα στην Python;

Καλησπέρα.

Λόγο μιας άσκησης στην σχολή μου, έψαξα να δω αν γίνεται να φτιάξω στατικούς πίνακες σε python.
Ο λόγος ήταν διότι ήθελα να μπορώ πετυχένω αναζήτηση με πολυπλοκότητα 1. Η στατιτικοί πίνακες
εφόσον έχουν συνεχόμενες θέσεις μνήμης αν γνωρίζεις το index μπορείς να πετύχεις γρήγορη αναζήτηση. Τελικά ανακάλυψα το εξής:

Εδώ το διάβασα

Η δομή list στην python το να πάρεις ένα δεδομένο με αυτόν τον τρόποκοστίζει το ίδιο ανεξάρτητα του index και το μέγεθος της λίστας. Συγκεκριμένα έλεγε ότι
το(n το μέγεθος της λίστας) κοστίζει όσο και το.

Καταρχάς αληθεύει αυτό; Και αν ναι, πως κατάφεραν να δημιουργήσουν μια τέτοια δομή όπου μπορείς
να την μεγαλώνεις και επίσης αν γνωρίζεις το index να παίρνεις το δεδομένο σε πολυπλοκότητα 1 !!!

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

docs.python.org/2/faq/design.html#how-are-lists-implemented
stackoverflow.com/questions/3917574/how-...ons-list-implemented
encrypted.google.com/search?hl=en&q=pyth...0lists%20implemented

pmav99 έγραψε:

Τελικά το βρήκα. Κάνει resize και reallocate στην μνήμη κάθε φορά που μπαίνει ένα νέο στοιχείο έτσι ώστε να δημιουργεί συνεχόμενες θέσεις μνήμης.

babaliaris1 έγραψε: Αν έκανε αυτό που λες θα ήταν πιο αργό από κάθε φαντασία.

pmav99 έγραψε:
Βασικά, κάθε φορά που δεν μπορεί να βρει συνεχόμενη μνήμη.