What is list

In Python, a list is a built-in data structure that represents an ordered, mutable (changeable), and heterogeneous (can contain different data types) collection of elements. Lists are one of the most commonly used data structures in Python due to their flexibility and dynamic nature.

Definition of a List in Python:

• A list is an ordered sequence of elements.
• Elements can be of different data types (e.g., integers, strings, other lists).
• Lists are mutable (can be modified after creation).
• Lists are represented by square brackets [] with elements separated by commas.

Example:

python

my_list = [1, "hello", 3.14, [5, 6, 7]]

---

How Lists are Represented in Memory

In Python, lists are implemented as dynamic arrays. This means:

1. Contiguous Memory Allocation: Lists store elements in contiguous memory locations for efficient indexing.
2. Dynamic Resizing: When a list grows beyond its current capacity, Python dynamically allocates a larger block of memory and copies the elements.
3. References to Objects: Since Python lists can store different data types, they actually store references (pointers) to objects rather than the objects themselves.

Memory Representation Example:

Consider the list:

python

lst = [10, "hello", 3.14]

In memory, it may look like this:

Index	Memory Address	Stored Value (Reference)	Actual Object
0	0x1000	→ 0x2000	10 (int)
1	0x1004	→ 0x3000	"hello" (str)
2	0x1008	→ 0x4000	3.14 (float)

• The list itself stores pointers to the actual objects.
• The objects can be stored anywhere in memory, but the list maintains an ordered sequence of references.

---

Key Points About List Memory Representation:

1. Dynamic Resizing:
   • Python lists start with some initial capacity.
   • When the list grows beyond this capacity, Python allocates a new, larger memory block (usually with extra space to reduce frequent resizing).
   • The growth factor is typically around 1.125x to 2x (implementation-dependent).
2. Time Complexity:
   • Accessing an element (lst[i]): O(1) (due to indexing).
   • Appending (lst.append(x)): O(1) (amortized, since occasional resizing occurs).
   • Inserting (lst.insert(i, x)): O(n) (requires shifting elements).
   • Deleting (del lst[i]): O(n) (requires shifting elements).
3. Memory Overhead:
   • Lists consume extra memory to store references and maintain dynamic resizing.
   • For large homogeneous data, array.array or numpy.ndarray may be more memory-efficient.

---

Example: List Memory Allocation

python

import sys

lst = [1, 2, 3]
print(sys.getsizeof(lst))  # Output: ~88 bytes (overhead for small list)

lst.append(4)  # May trigger resizing
print(sys.getsizeof(lst))  # New size (e.g., 120 bytes)

Conclusion

• Lists in Python are dynamic arrays that store references to objects.
• They allow fast indexing (O(1)) but may require resizing when growing.
• Memory usage is higher than fixed-size arrays due to dynamic allocation.