list

A Python list is a built-in, mutable, ordered sequence data type that stores a collection of heterogeneous object references. Under the hood, CPython implements lists as dynamic arrays of pointers. This means a list does not store the actual objects inline, but rather stores contiguous memory addresses pointing to the objects, allowing it to hold mixed data types while maintaining $O(1)$ time complexity for index-based access.

Instantiation and Syntax

Lists are created using square bracket literal syntax [] or the built-in list() constructor.

# Literal syntax (preferred for performance and readability)
empty_list = []
mixed_list = [42, "node", 3.14, [1, 2]]


# Constructor syntax (typically used for type casting iterables)
from_tuple = list((1, 2, 3))
from_string = list("dev")  # ['d', 'e', 'v']

Core Characteristics

• Mutable: The internal state of the list can be altered in place without creating a new object in memory. Elements can be reassigned, added, or removed.
• Ordered: Lists maintain the exact insertion order of their elements.
• Zero-indexed: Element access begins at index 0. Python also supports negative indexing, where -1 resolves to the final element.
• Dynamic Sizing: Lists automatically handle memory reallocation. When the underlying array reaches its capacity, Python allocates a new, larger array (typically over-allocating by a proportional factor) and copies the existing pointers to the new memory block.

Indexing and Slicing

Lists support standard sequence operations, including slicing, which extracts a new list based on the [start:stop:step] syntax.

buffer = [10, 20, 30, 40, 50, 60]


# Indexing
head = buffer[0]         # 10
tail = buffer[-1]        # 60


# Slicing (creates a shallow copy of the extracted range)
sub_array = buffer[1:4]  # [20, 30, 40]
reversed_array = buffer[::-1]  # [60, 50, 40, 30, 20, 10]


# Mutating via index
buffer[1] = 99           # [10, 99, 30, 40, 50, 60]

Mutation Operations

Because lists are dynamic arrays, operations that modify the end of the list are highly optimized, while operations that modify the beginning or middle require shifting elements in memory.

data = [1, 2, 3]


# O(1) Amortized Operations
data.append(4)           # Appends a single element to the tail: [1, 2, 3, 4]
data.pop()               # Removes and returns the tail element: 4


# O(k) Operations (where k is the length of the iterable)
data.extend([5, 6])      # Appends elements from an iterable: [1, 2, 3, 5, 6]


# O(n) Operations (requires shifting subsequent elements)
data.insert(0, 99)       # Inserts 99 at index 0: [99, 1, 2, 3, 5, 6]
data.pop(0)              # Removes and returns element at index 0: 99
data.remove(5)           # Removes the first occurrence of value 5

Memory and Performance Profile

Understanding the time complexity of list operations is critical for performance optimization:

Operation	Syntax	Average Case Time Complexity
Access	list[i]	$O(1)$
Update	list[i] = x	$O(1)$
Append	list.append(x)	$O(1)$ (Amortized)
Pop (Tail)	list.pop()	$O(1)$
Insert	list.insert(i, x)	$O(n)$
Pop (Index)	list.pop(i)	$O(n)$
Search	x in list	$O(n)$

Because insert() and pop(0) operate in $O(n)$ time due to memory shifting, Python lists are inefficient when used as queues (FIFO structures). For double-ended queue operations, collections.deque is the standard library alternative, implemented as a doubly linked list.

Master Python with Deep Grasping Methodology!

Learn More