Data Structures: Difference between revisions
From charlesreid1
| Line 46: | Line 46: | ||
[[Search Trees]] | [[Search Trees]] | ||
[[ | [[Balanced Search Trees]] | ||
[[Trees for Set Intervals]] | [[Trees for Set Intervals]] | ||
Revision as of 02:30, 7 June 2017
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
- 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
- Stacks, queues, and deques are important structures for O(1) access to front/back, order in determines order out
- 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
- 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