Hands-On Data Structures and Algorithms with Python - Third Edition

Hands-On Data Structures and Algorithms with Python - Third Edition

by Dr. Basant Agarwal
Released July 2022
Publisher(s): Packt Publishing
ISBN: 9781801073448

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Understand how implementing different data structures and algorithms intelligently can make your Python code and applications more maintainable and efficient

Key Features

  • Explore functional and reactive implementations of traditional and advanced data structures
  • Apply a diverse range of algorithms in your Python code
  • Implement the skills you have learned to maximize the performance of your applications

Book Description

Choosing the right data structure is pivotal to optimizing the performance and scalability of applications. This new edition of Hands-On Data Structures and Algorithms with Python will expand your understanding of key structures, including stacks, queues, and lists, and also show you how to apply priority queues and heaps in applications. You'll learn how to analyze and compare Python algorithms, and understand which algorithms should be used for a problem based on running time and computational complexity. You will also become confident organizing your code in a manageable, consistent, and scalable way, which will boost your productivity as a Python developer.

By the end of this Python book, you'll be able to manipulate the most important data structures and algorithms to more efficiently store, organize, and access data in your applications.

What you will learn

  • Understand common data structures and algorithms using examples, diagrams, and exercises
  • Explore how more complex structures, such as priority queues and heaps, can benefit your code
  • Implement searching, sorting, and selection algorithms on number and string sequences
  • Become confident with key string-matching algorithms
  • Understand algorithmic paradigms and apply dynamic programming techniques
  • Use asymptotic notation to analyze algorithm performance with regard to time and space complexities
  • Write powerful, robust code using the latest features of Python

Who this book is for

This book is for developers and programmers who are interested in learning about data structures and algorithms in Python to write complex, flexible programs. Basic Python programming knowledge is expected.

Table of contents

  1. Preface
    1. Who this book is for
    2. What this book covers
    3. To get the most out of this book
    4. Get in touch
  2. Python Data Types and Structures
    1. Introducing Python 3.10
    2. Installing Python
      1. Windows operating system
      2. Linux-based operating systems
      3. Mac operating system
    3. Setting up a Python development environment
      1. Setup via the command line
      2. Setup via Jupyter Notebook
    4. Overview of data types and objects
    5. Basic data types
      1. Numeric
      2. Boolean
      3. Sequences
        1. Strings
        2. Range
        3. Lists
      4. Membership, identity, and logical operations
        1. Membership operators
        2. Identity operators
        3. Logical operators
      5. Tuples
    6. Complex data types
      1. Dictionaries
      2. Sets
        1. Immutable sets
    7. Python’s collections module
      1. Named tuples
      2. Deque
      3. Ordered dictionaries
      4. Default dictionary
      5. ChainMap object
      6. Counter objects
      7. UserDict
      8. UserList
      9. UserString
    8. Summary
  3. Introduction to Algorithm Design
    1. Introducing algorithms
    2. Performance analysis of an algorithm
      1. Time complexity
      2. Space complexity
    3. Asymptotic notation
      1. Theta notation
      2. Big O notation
      3. Omega notation
    4. Amortized analysis
    5. Composing complexity classes
    6. Computing the running time complexity of an algorithm
    7. Summary
    8. Exercises
  4. Algorithm Design Techniques and Strategies
    1. Algorithm design techniques
    2. Recursion
    3. Divide and conquer
      1. Binary search
      2. Merge sort
    4. Dynamic programming
      1. Calculating the Fibonacci series
    5. Greedy algorithms
      1. Shortest path problem
    6. Summary
    7. Exercises
  5. Linked Lists
    1. Arrays
    2. Introducing linked lists
      1. Nodes and pointers
    3. Singly linked lists
      1. Creating and traversing
        1. Improving list creation and traversal
      2. Appending items
        1. Appending items to the end of a list
        2. Appending items at intermediate positions
      3. Querying a list
        1. Searching an element in a list
        2. Getting the size of the list
      4. Deleting items
        1. Deleting the node at the beginning of the singly linked list
        2. Deleting the node at the end in the singly linked list
        3. Deleting any intermediate node in a singly linked list
        4. Clearing a list
    4. Doubly linked lists
      1. Creating and traversing
      2. Appending items
        1. Inserting a node at beginning of the list
        2. Inserting a node at the end of the list
        3. Inserting a node at an intermediate position in the list
      3. Querying a list
      4. Deleting items
    5. Circular lists
      1. Creating and traversing
      2. Appending items
      3. Querying a list
      4. Deleting an element in a circular list
    6. Practical applications of linked lists
    7. Summary
    8. Exercise
  6. Stacks and Queues
    1. Stacks
      1. Stack implementation using arrays
      2. Stack implementation using linked lists
      3. Push operation
      4. Pop operation
      5. Peek operation
      6. Applications of stacks
    2. Queues
      1. Python’s list-based queues
        1. The enqueue operation
        2. The dequeue operation
      2. Linked list based queues
        1. The enqueue operation
        2. The dequeue operation
      3. Stack-based queues
        1. Approach 1: When the dequeue operation is costly
        2. Approach 2: When the enqueue operation is costly
        3. Enqueue operation
        4. Dequeue operation
      4. Applications of queues
    3. Summary
    4. Exercises
  7. Trees
    1. Terminology
    2. Binary trees
      1. Implementation of tree nodes
      2. Tree traversal
        1. In-order traversal
        2. Pre-order traversal
        3. Post-order traversal
        4. Level-order traversal
      3. Expression trees
        1. Parsing a reverse Polish expression
    3. Binary search trees
      1. Binary search tree operations
        1. Inserting nodes
        2. Searching the tree
        3. Deleting nodes
        4. Finding the minimum and maximum nodes
      2. Benefits of a binary search tree
    4. Summary
    5. Exercises
  8. Heaps and Priority Queues
    1. Heaps
      1. Insert operation
      2. Delete operation
      3. Deleting an element at a specific location from a heap
      4. Heap sort
    2. Priority queues
    3. Summary
    4. Exercises
  9. Hash Tables
    1. Introducing hash tables
      1. Hashing functions
      2. Perfect hashing functions
    2. Resolving collisions
      1. Open addressing
        1. Linear probing
    3. Implementing hash tables
      1. Storing elements in a hash table
      2. Growing a hash table
      3. Retrieving elements from the hash table
      4. Testing the hash table
      5. Implementing a hash table as a dictionary
        1. Quadratic probing
        2. Double hashing
      6. Separate chaining
    4. Symbol tables
    5. Summary
    6. Exercise
  10. Graphs and Algorithms
    1. Graphs
      1. Directed and undirected graphs
      2. Directed acyclic graphs
      3. Weighted graphs
      4. Bipartite graphs
    2. Graph representations
      1. Adjacency lists
      2. Adjacency matrix
    3. Graph traversals
      1. Breadth-first traversal
      2. Depth-first search
    4. Other useful graph methods
      1. Minimum Spanning Tree
      2. Kruskal’s Minimum Spanning Tree algorithm
      3. Prim’s Minimum Spanning Tree algorithm
    5. Summary
    6. Exercises
  11. Searching
    1. Introduction to searching
    2. Linear search
      1. Unordered linear search
      2. Ordered linear search
    3. Jump search
    4. Binary search
    5. Interpolation search
    6. Exponential search
    7. Choosing a search algorithm
    8. Summary
    9. Exercise
  12. Sorting
    1. Technical requirements
    2. Sorting algorithms
    3. Bubble sort algorithms
    4. Insertion sort algorithm
    5. Selection sort algorithm
    6. Quicksort algorithm
    7. Implementation of quicksort
    8. Timsort algorithm
    9. Summary
    10. Exercise
  13. Selection Algorithms
    1. Technical requirements
    2. Selection by sorting
    3. Randomized selection
      1. Quickselect
    4. Deterministic selection
      1. Implementation of the deterministic selection algorithm
    5. Summary
    6. Exercise
  14. String Matching Algorithms
    1. Technical requirements
    2. String notations and concepts
    3. Pattern matching algorithms
    4. The brute force algorithm
    5. The Rabin-Karp algorithm
      1. Implementing the Rabin-Karp algorithm
    6. The Knuth-Morris-Pratt algorithm
      1. The prefix function
      2. Understanding the KMP algorithm
      3. Implementing the KMP algorithm
    7. The Boyer-Moore algorithm
      1. Understanding the Boyer-Moore algorithm
        1. Bad character heuristic
        2. Good suffix heuristic
        3. Implementing the Boyer-Moore algorithm
    8. Summary
    9. Exercise
  15. Appendix: Answers to the Questions
    1. Chapter 2: Introduction to Algorithm Design
    2. Chapter 3: Algorithm Design Techniques and Strategies
    3. Chapter 4: Linked Lists
    4. Chapter 5: Stacks and Queues
    5. Chapter 6: Trees
    6. Chapter 7: Heaps and Priority Queues
    7. Chapter 8: Hash Tables
    8. Chapter 9: Graphs and Algorithms
    9. Chapter 10: Searching
    10. Chapter 11: Sorting
    11. Chapter 12: Selection Algorithm
    12. Chapter 13: String Matching Algorithms
  16. Other Books You May Enjoy
  17. Index

Product information

  • Title: Hands-On Data Structures and Algorithms with Python - Third Edition
  • Author(s): Dr. Basant Agarwal
  • Release date: July 2022
  • Publisher(s): Packt Publishing
  • ISBN: 9781801073448