|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| List of pages of notes on the wiki related to data structures:
| | #REDIRECT [[:Category: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]]
| |
| | |
| [[Graphs]]
| |
| | |
| [[Dictionaries]]
| |
| | |
| ==Advanced Data Structures==
| |
| | |
| [[Search Trees]]
| |
| | |
| [[Balanced Search Trees]]
| |
| | |
| [[Trees for Set Intervals]]
| |
| | |
| [[Heaps]]
| |
| | |
| [[Set Data Structures]]
| |
| | |
| [[String Data Structures]]
| |
| | |
| [[Hash Tables]]
| |
| | |
| [[Hash Trees]]
| |