Data Structures

List of pages of notes on the wiki related to data structures:

Elementary Data Structures

An important topic that connects each of the concepts below is Abstract Data Types, which are general implementation interfaces intended to be common to these data containers across both Java and Python

Arrays

• array-based data structures, storage, and algorithms
• lower-level structure that can be implemented by many higher-level data structures
• Python has a built-in array-based list() type, everything (including integers) is reference-based - Arrays/Python
• Java has Array type, size must be known at creation time - Arrays/Java
• Can implement a Python list type in Java - see Arrays/Java/PythonList
• Many data structures below can be implemented under the hood as array-based or linked structure based

StacksQueues

• Stacks, queues, and deques are important structures for O(1) access to front/back, order in determines order out

Lists

• Lists have two main implementations - array-based lists (in Python, this is a natural place to start, due to Python's built-in list type) or object- and link-based (in Java, this is more natural due to the way the language principally focuses on objects).
• Linked Lists can be implemented in either Python or Java - see Linked Lists/Python or Linked Lists/Java
• ArrayLists are a type in Java but are also similar to the array-based list data structure built into Python

Trees

• Tree structures are nonlinear data structures that extend the idea of a linked list node and data pointer organization.
• A tree is a directed acyclic graph consisting of parent nodes and child nodes, such that all nodes have one parent (except the top-level root node). Typically number of children n is fixed.
• Nodes without children are leaf nodes/external nodes. Nodes with one or more children are internal nodes.
• Binary Trees are a tree structure where each node has a maximum of two children:
  • Each node has a maximum of two children
  • Each child node is labeled as left or right
• Left precedes right in order of children of a node
  • Proper/full - each node has 0 or 2 children
  • Improper - one or more nodes have 1 child
• Recursive binary tree definition:
  • A node r, called root of T, stores an element
  • A binary tree, possibly empty, called left subtree of T
  • A binary tree, possibly empty, called right subtree of T
• Binary Trees/LinkedBinTree
• Binary Trees/ArrayBinTree

Dictionaries

Advanced Data Structures

Search Trees

Calanced Search Trees

Trees for Set Intervals

Heaps

Set Data Structures

String Data Structures

Hash Tables

Hash Trees