Abstract Data Types and Data Structures

This site is dedicated at teaching abstract data types and data structures built on their framework as well as providing a C++ API that stands on their foundation: one of endless possible but uniquely fast, thanks of being done with elegance and simplicity in mind.

Theory

Covering complete list of abstract data types and data stuctures (if there is any) is a monumental task outside of this site's scope. Only types/structures considered to be potentially useful in a developer's day-to-day life will be covered here!

Abstract Data Types

Abstract Data Types are abstract data units defined by properties and operations without implementation suggestions. Following were found useful enough to be covered:

List: defines blueprints for sequential data unit where every entry is accessible by position
Associative Array: defines blueprints for sequential data unit where every entry is a key-value pair, values accessible by key
Set: defines blueprints for sequential data unit where every entry is unique
Container: defines blueprints for sequential data unit that behaves like a black box where only push/pop operations are used
Tree: defines blueprints for data unit where every entry is a node, connected to one or more nodes
Graph: defines blueprints for data unit where every entry is a vertex, connected to other vertexes via edges

Data Structures

Data Structures are concrete data units that provide implementation to one or more abstract data types. Following are covered to implement abstract data types above:

Dynamic Array: implements a List where all entries lie in a single memory block.
Linked List: implements a List where each entry holds a link to to the next.
Doubly Linked List: implements a List where each entry holds a link to to the next and previous.
Stack: implements a Container where last entry pushed is first to be popped via a List.
Queue: implements a Container where first entry pushed is first to be popped via a List.
Hash Table: abstract data structure where each entry is distributed by a hash function to a List of buckets for O(~1) performance.
- Hash Map: implements Associative Array using Hash Table
- Hash Set: implements Set using Hash Table
- Linked Hash Table: implements a version of Hash Table where each entry is also saved into a Doubly Linked List to allow predictable iteration.
  - Linked Hash Map: implements Associative Array using Linked Hash Table
  - Linked Hash Set: implements Set using Linked Hash Table
Tree implementation:
- Standard Tree: implements a Tree where each node can have unlimited number of children.
- B-Tree: implements a Tree with custom limit nodes' child number self-balanced using b-tree sparse-index algorithm.
  - B+ Tree: implements a modified B-Tree self-balanced using b+tree dense-index algorithm.
- Binary Search Tree: implements a Tree optimized for searching where nodes can only have max two children. Can be used to implement a Set or a Associative Array, where key-value pair will be node data.
  - Red Black Tree: implements a Binary Search Tree self-balanced using red-black-tree algorithm.
  - AVL Tree: implements a Binary Search Tree self-balanced using AVL-tree algorithm.
Unweighted Graph: implements an abstract Graph where all edges have no weights
- Unweighted Directed Graph: implements a version of Unweighted Graph where edges are unidirectional by default
- Unweighted Undirected Graph: implements a version of Unweighted Graph where edges are always bidirectional
Weighted Graph: implements an abstract Graph where all edges have weights
- Weighted Directed Graph: implements a version of Weighted Graph where edges are unidirectional by default
- Weighted Undirected Graph: implements a version of Weighted Graph where edges are always bidirectional

Most strongly typed programming languages come with an official implementation for some of structures above (STL @ C++ or Collections @ Java) but only API below covers them all.

Practice: C++ API

Building an API that partly overlaps with STL looks like textbook "wheel reinventing". Unlike STL, however, this API covers all types/structures above and employs a harmonical architecture instead:

much lighter weight
structured on polymorphism (because if naturally fits the concepts of data structures)
larger in scope (supporting trees and graphs also)
equally stable (rigurously covered by unit and memory leak tests)
superior performance (as benchmarks prove)

Last but not least, this API invites other developers to contribute and exercise their skills to solve pending tasks or add new algorithms/types/structures not supported already while keeping same coding/stability standards!

How does it work?

Abstract Data Types and Data Structures C++ API, or C++ ADT & DS API, is nothing more than a collection of decoupled components and their dependencies designed polymorphically by interface-implementation principle:

each interface corresponds to an abstract data type
each implementation corresponds to one or more data structures built on top of above

To learn more about it, you first need to have firm theoretical knowledge of abstract data types and data structures. If you have it already, go to documentation!

How powerful is it?

Entire implementation of this API was geared towards simplicity and memory/speed efficiency. The end result can be checked in benchmarks page, showing identical memory consumption but superior speed compared to STL. Below chart shows how long it takes to insert a million long entries, for each API class and STL equivalent, measured in milliseconds:

How to install it?

To install API go to installation page and follow steps described there then go through documentation page to learn how to use it. If you just want to see sources, go to https://github.com/aherne/c-data-structures-api.