Constructive elements and building blocks
All the basic finite math matrix or graph elements that form data structures or concepts
In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type.
Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, relational databases commonly use B-tree indexes for data retrieval, while compiler implementations usually use hash tables to look up identifiers.
Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Data structures can be used to organize the storage and retrieval of information stored in both main memory and secondary memory.
Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer—a bit string, representing a memory address, that can be itself stored in memory and manipulated by the program. Thus, the array and record data structures are based on computing the addresses of data items with arithmetic operations, while the linked data structures are based on storing addresses of data items within the structure itself.
The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations. This observation motivates the theoretical concept of an abstract data type, a data structure that is defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including their space and time cost).
Main article: List of data structures There are numerous types of data structures, generally built upon simpler primitive data types:
- An array is a number of elements in a specific order, typically all of the same type (depending on the language, individual elements may either all be forced to be the same type, or may be of almost any type). Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or resizable.
- A linked list (also just called list) is a linear collection of data elements of any type, called nodes, where each node has itself a value, and points to the next node in the linked list. The principal advantage of a linked list over an array is that values can always be efficiently inserted and removed without relocating the rest of the list. Certain other operations, such as random access to a certain element, are however slower on lists than on arrays.
- A record (also called tuple or struct) is an aggregate data structure. A record is a value that contains other values, typically in fixed number and sequence and typically indexed by names. The elements of records are usually called fields or members.
- A union is a data structure that specifies which of a number of permitted primitive types may be stored in its instances, e.g. float or long integer. Contrast with a record, which could be defined to contain a float and an integer; whereas in a union, there is only one value at a time. Enough space is allocated to contain the widest member datatype.
- A tagged union (also called variant, variant record, discriminated union, or disjoint union) contains an additional field indicating its current type, for enhanced type safety.
- An object is a data structure that contains data fields, like a record does, as well as various methods which operate on the data contents. An object is an in-memory instance of a class from a taxonomy. In the context of object-oriented programming, records are known as plain old data structures to distinguish them from objects.
- In addition, graphs and binary trees are other commonly used data structures.
Mon, Mar 15, 2021
List of data structures
In progress, taken straight from Wikipedia as a strong starting point for a comprehensive list. We might not need all these types, but they are an interesting study. What are the fundamental constructive objects ("basic building blocks") and what are the more composite objects -- complex structure built from simpler structures
- Data types
- Primitive types
- Boolean, true or false.
- Floating-point numbers, limited precision approximations of real number values.
- Including Single precision and Double precision IEEE 754 Floats, among others
- Fixed-point numbers
- Integer, integral or fixed-precision values.
- Reference (also called a pointer or handle), a small value referring to another object's address in memory, possibly a much larger one.
- Enumerated type, a small set of uniquely named values.
- Date Time, value referring to Date and Time
- Composite types or non-primitive type
- Array (as an example String which is an array of characters)
- Record (also called Associative array, Map, or structure)
- Union (Tagged union is a subset, also called variant, variant record, discriminated union, or disjoint union)
- Abstract data types
- Multiset (bag)
- Queue (example Priority queue)
- Double-ended queue
- Graph (example Tree, Heap)
Some properties of abstract data types:
Structure Order Unique List yes no Associative array no yes Set no yes Stack yes no Multimap no no Multiset (bag) no no Queue yes no Order means the insertion sequence counts. Unique means that duplicate elements are not allowed, based on some inbuilt or, alternatively, user-defined rule for comparing elements.
Linear data structures A data structure is said to be linear if its elements form a sequence.
Arrays Array Bit array Bit field Bitboard Bitmap Circular buffer Control table Image Dope vector Dynamic array Gap buffer Hashed array tree Lookup table Matrix Parallel array Sorted array Sparse matrix Iliffe vector Variable-length array Lists Doubly linked list Array list Linked list Association list Self-organizing list Skip list Unrolled linked list VList Conc-tree list Xor linked list Zipper Doubly connected edge list also known as half-edge Difference list Free list Trees Main article: Tree (data structure) Binary trees AA tree AVL tree Binary search tree Binary tree Cartesian tree Conc-tree list Left-child right-sibling binary tree Order statistic tree Pagoda Randomized binary search tree Red–black tree Rope Scapegoat tree Self-balancing binary search tree Splay tree T-tree Tango tree Threaded binary tree Top tree Treap WAVL tree Weight-balanced tree B-trees B-tree B+ tree B*-tree B sharp tree Dancing tree 2-3 tree 2-3-4 tree Queap Fusion tree Bx-tree AList Heaps Heap Binary heap B-heap Weak heap Binomial heap Fibonacci heap AF-heap Leonardo Heap 2-3 heap Soft heap Pairing heap Leftist heap Treap Beap Skew heap Ternary heap D-ary heap Brodal queue Trees In these data structures each tree node compares a bit slice of key values.
Tree (data structure) Radix tree Suffix tree Suffix array Compressed suffix array FM-index Generalised suffix tree B-tree Judy array X-fast trie Y-fast trie Merkle tree C tree Multi way trees Ternary tree K-ary tree And–or tree (a,b)-tree Link/cut tree SPQR-tree Spaghetti stack Disjoint-set data structure (Union-find data structure) Fusion tree Enfilade Exponential tree Fenwick tree Van Emde Boas tree Rose tree Space-partitioning trees These are data structures used for space partitioning or binary space partitioning.
Segment tree Interval tree Range tree Bin K-d tree Implicit k-d tree Min/max k-d tree Relaxed k-d tree Adaptive k-d tree Quadtree Octree Linear octree Z-order UB-tree R-tree R+ tree R* tree Hilbert R-tree X-tree Metric tree Cover tree M-tree VP-tree BK-tree Bounding interval hierarchy Bounding volume hierarchy BSP tree Rapidly exploring random tree Application-specific trees Abstract syntax tree Parse tree Decision tree Alternating decision tree Minimax tree Expectiminimax tree Finger tree Expression tree Log-structured merge-tree Lexicographic Search Tree Hash-based structures Bloom filter Count-Min sketch Distributed hash table Double hashing Dynamic perfect hash table Hash array mapped trie Hash list Hash table Hash tree Hash trie Koorde Prefix hash tree Rolling hash MinHash Quotient filter Ctrie Graphs Many graph-based data structures are used in computer science and related fields:
Graph Adjacency list Adjacency matrix Graph-structured stack Scene graph Decision tree Binary decision diagram Zero-suppressed decision diagram And-inverter graph Directed graph Directed acyclic graph Propositional directed acyclic graph Multigraph Hypergraph Other Lightmap Winged edge Quad-edge Routing table Symbol table See also Purely functional data structure
Mon, Mar 15, 2021
Dimensions and ordered lists
In general, we are defining a dimension as an "ordered list of values", taking a form like a matrix row or a database record.
Thu, Apr 29, 2021