list Internals
Python lists are dynamic arrays — contiguous memory blocks that resize automatically.
A Python list is like a row of people on a bench. Adding someone to the end is easy (scoot over). Inserting at the front? Everyone has to stand up and shift one seat right.
O(1) amortized append (doubles capacity when full — amortized because occasional O(n) resizes are amortized over many appends). O(1) index access. O(n) insert/delete in the middle (shifts elements). O(n) search (in operator). list.sort() uses Timsort — O(n log n) worst case, O(n) best case (already sorted), stable. list comprehensions are faster than equivalent for loops due to CPython optimization.
CPython allocates extra capacity using the formula: new_capacity = (n * 9 / 8) + 6. Over-allocation reduces the frequency of resizes. Slicing creates a new list (shallow copy). list.copy() and list[:] both shallow copy. For memory efficiency with large numbers of uniform-type items, use array.array or numpy.ndarray. sys.getsizeof([]) shows base overhead (~56 bytes for an empty list). The list object has a pointer to an array of object pointers — not a contiguous array of values (unlike C arrays).
Python lists are dynamic arrays — O(1) append amortized, O(1) index. Insertion/deletion in the middle is O(n) due to shifting. Search is O(n). For a deque (fast append/pop from both ends), use collections.deque — O(1) both ends. For sorted data with binary search, use the bisect module. Timsort makes list.sort() extremely fast on partially-sorted data, which is common in practice.
list.insert(0, x) is O(n) — it shifts every element. If you need a queue (FIFO), use collections.deque, not a list. list.pop(0) is also O(n).