Scribd
Upload
1 views1 page

Document 1 Python Ds

The document provides an overview of core built-in Python data structures, including lists, tuples, sets, and dictionaries, along with their time complexities for various operations. It highlights the performance characteristics of these structures, such as average time complexities for access, search, insertion, and deletion. Additionally, it offers optimization rules for efficient data handling, recommending the use of deque for queues, generator expressions for large data streams, and set or dict for filtering datasets.

Uploaded by

AmineElbahi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views1 page

Document 1 Python Ds

The document provides an overview of core built-in Python data structures, including lists, tuples, sets, and dictionaries, along with their time complexities for various operations. It highlights the performance characteristics of these structures, such as average time complexities for access, search, insertion, and deletion. Additionally, it offers optimization rules for efficient data handling, recommending the use of deque for queues, generator expressions for large data streams, and set or dict for filtering datasets.

Uploaded by

AmineElbahi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Python Data Structures & Time Complexity

Reference
Technical Reference Guide • Computer Science & Software Engineering

1. Overview of Core Built-in Types


• List: Dynamic array supporting fast random access ($O(1)$) and variable-length sequencing.

• Tuple: Immutable ordered sequence used for fixed data records and dictionary keys.

• Set: Unordered collection of unique elements implemented via a hash table.

• Dictionary (dict): Key-value hash map providing average $O(1)$ lookups, insertions, and deletions.

2. Asymptotic Time Complexities

Structure Access Search Insertion Deletion

List O(1) O(n) O(n) [O(1) at end] O(n)

Tuple O(1) O(n) N/A (Immutable) N/A (Immutable)

Set N/A O(1) avg O(1) avg O(1) avg

Dict O(1) avg O(1) avg O(1) avg O(1) avg

3. Performance Optimization Rules


• Use [Link] when implementing FIFO queues or double-ended stacks to avoid $O(n)$ element shifting
penalties on [Link](0).

• Use generator expressions instead of list comprehensions when processing large streams of sequential data to
keep memory usage minimal.

• Prefer in operators against set or dict collections rather than lists when filtering high-volume datasets.

You might also like