Data Structures

General Introductions

• Aakash Varshney. Introduction to Data Structures. the startup, 2018.
  • Covers at a high level one-dimensional arrays, multidimensional arrays, dynamic arrays, singly linked lists, doubly linked lists, circular linked lists, stacks, queues, trees, and binary search trees.
• Robert Horvick. Data Structures Succinctly Part 1. syncfusion, 2014.
  • Covers algorithms and data structures overview, linked lists, array lists, stacks, queues, binary search tree, set, and sorting algorithms.
• Robert Horvick. Data Structures Succinctly Part 2. syncfusion, 2014.
  • Covers skip lists, hash tables, heap and priority queues, and AVL trees.
• Radhika Ghosal. “It’s turtles all the way down.” – A Guide to the Basics of Data Structures. algosaurus, 2015.
• OpenDSA.
• Open Data Structures (ebook) – Available in pseudocode, java, and c++ editions.
  • “Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs.”
• JavaScript:
  • Itsy Bitsy Data Structures – “super simplified examples of many of the common data structures written in easy to read JavaScript.”
  • Thon Ly. Algorithms in JavaScript: 40 Problems, Solutions, and Explanations. medium, 2017.
• Python:
  • Brad Miller, David Ranum. Problem Solving with Algorithms and Data Structures Using Python. runestone.academy.
  • Dan Bader. Common Python Data Structures (Guide). realpython, 8/2020.*
    • Covers dictionaries (dicts, also known as maps, hash tables, lookup tables, associative arrays)…

The Types of Data Structures

Arrays

• Estefania Cassingena Navone. Data Structures 101: Arrays – A Visual Introduction for Beginners. freecodecamp, 2019.

“Multidimensional arrays are sometimes referred to as tables or matrices because of their structure.”

Aakash Varshney, Introduction to Data Structures. The Startup, 2018.

Dictionaries (sometimes called Associative Arrays or Hash Tables)

• Often when someone refers to a “hash” they are speaking of a “hash table” a specific implementation of the abstract data type dictionary (StackOverflow).
• Estefania Cassingena Navone. Python Dictionaries 101: A Detailed Visual Introduction. freecodecamp, 2019.

Graphs

“Graphs are used to represent, find, analyze, and optimize connections between elements (houses, airports, locations, users, articles, etc.).”

Estefania Cassingena Navone

• Estefania Cassingena Navone. Data Structures 101: Graphs — A Visual Introduction for Beginners. freecodecamp, 2019.*
• Vaidehi Joshi. A Gentle Introduction to Graph Theory. basecs, 2017.*
• Vardan Grigoryan. How to Think in Graphs: An Illustrative Introduction to Graph Theory and Its Applications. freecodecamp, 2018.
• Basic Components: Nodes, Edges
• |V| = Number of vertices (nodes) in a graph.
• |E| = Number of edges (connections) in a graph.
• Graphs are classified by edge characteristics.
  • Directional
    • Directed Graphs
    • Undirected Graphs
  • Weighting
    • Weighted Graphs
    • Unweighted Graphs
  • Multigraphs
  • Density
    • Dense Graphs
    • Sparse Graphs
• Traversal
  • Depth First Traversal
  • Breadth First Traversal
• Cycles

Heaps

• Vaidehi Joshi. Learning to Love Heaps. basecs, 7/2017.*
• Mariam Jaludi. Data Structures: Heaps. medium, 9/2019.
• min-heap- the smallest value is at the root, all children must be more than/equal to their parent.
• max-heap – the greatest value is at the root, all children must be less than/equal to their parent.
• C#:
  • Richard Carr. Binary Heaps. BlackWasp, 2013.
    • Starts with a fairly extensive, language-agnostic introduction.
• Python:
  • Min Heap in Python. GeeksforGeeks, 2/2020.
  • Moshe Zadka. The Python heapq Module: Using Heaps and Priority Queues. realpython, 6/2020.

Linked Lists

• Vaidehi Joshi. What’s a Linked List, Anyway? [Part 1], [Part 2]. basecs, 2017.
• Singly Linked List
  • Each item in a linked list has a reference to the item following it.
• Doubly Linked
  • If a linked list is doubly linked, it has a reference to both the previous and next records.
• Circularly Linked
  • Each item is linked to another and forms a circle.
• JavaScript:
  • Kevin Turney. Data Structures 101: Linked Lists. freecodecamp, 2018.
• Python:
  • Pedro Pregueiro. Linked Lists in Python: An Introduction. realpython, 2020.

Queues

• First-In First-Out (FIFO).
• Similar to Stacks, but instead of LIFO (Last-In First-Out) it uses FIFO (First-In First-Out).
• JavaScript
  • Kevin Turney. Data Structures 101: Queues. freecodecamp, 2018.

Sets

• Estefania Cassingena Navone. Python Sets: A Detailed Visual Introduction. freecodecamp, 2020.

Stacks

• Last-In First-Out (LIFO), rarely called First-In Last-Out (FILO).
• Uses push to add to top of stack, pull or pop to remove from top of stack. Not possible to interact with any other item besides top item.
  • Sometimes supports peek which allows looking at top of stack but without removing it from the stack.
  • Think of a stacked pile of physical items, it is easiest to add to the top of the stack and to remove from the top of the stack, getting to other items in the stack is difficult/impossible.
• Wahid Tanner. Episode 206: Collections: Stack. takeupcode, 2017.
• Python:
  • Does not include stack as a data structure but lists (bad idea) and collections.deque (“deck”) can be used as stacks.
    • In Python you will use append() instead of push().
  • Jim Anderson. How to Implement a Python Stack. realpython, 2019.*
  • Stack in Python. GeeksforGeeks, 2020.
• JavaScript:
  • Kevin Turney. Data Structures 101: Stacks. freecodecamp, 2018.
• C/C++
  • Anand Jaisingh. Basics of Stacks. hackerearth, 2020.

Trees

• Wahid Tanner, Trees Can, takeupcode, 2017.
• Wahid Tanner, Trees Use, takeupcode, 2017.
• Traversal
• Binary Search Tree
  • Kevin Turney. Data Structures 101: Binary Search Tree. freecodecamp, 2018.
• AVL Tree
• Spanning Tree
• Splay Tree

Big O Notation

• Richard Carr. Big O Notation Basics. BlackWasp, 2013.