Data Structures

General Introductions

The Types of Data Structures

Arrays

“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)

Graphs

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

Estefania Cassingena Navone

Heaps

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:
  • Python:

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

Sets

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:
  • C/C++

Trees

Big O Notation