A collection of classic data structures and algorithms written from scratch in C-style C++. Every structure lives in its own .h file, follows the same conventions and has its own automatic test, so the code is easy to read, compare and check.
| Structure | Description | File |
|---|---|---|
| Array | Static array with a fixed maximum size | array.h |
| Dynamic Array | Array that doubles its capacity with realloc when it's full |
dynamicarray.h |
| Stack | LIFO stack stored in an array | stack.h |
| Linked Stack | Stack built with nodes, without a size limit | linkedstack.h |
| Queue | FIFO circular queue stored in an array | queue.h |
| Linked Queue | Queue built with nodes, without a size limit | linkedqueue.h |
| Deque | Circular queue that inserts and removes at both ends | deque.h |
| Linked List | Singly linked list | linkedlist.h |
| Doubly Linked List | Nodes with prev and next, with head and tail |
doublylinkedlist.h |
| Circular Linked List | The last node points to the first one | circularlinkedlist.h |
| Type | Structure | Description | File |
|---|---|---|---|
| Tree | Binary Search Tree | Insert, search, delete, min, max, height and four traversals (in, pre, post and level order) | binarysearchtree.h |
| Tree | AVL Tree | BST that keeps itself balanced with rotations | avltree.h |
| Tree | Heap | Min heap or max heap stored in an array | heap.h |
| Tree | Priority Queue | Min heap of (value, priority) pairs | priorityqueue.h |
| Tree | Trie | Prefix tree for lowercase words | trie.h |
| Hash | Hash Table (chaining) | Each bucket is a linked list of (key, value) pairs | hashtablechaining.h |
| Hash | Hash Table (open addressing) | Linear probing with tombstones | hashtableopenaddressing.h |
| Hash | Set | Set built on the hash table: union, intersection, difference and subset | set.h |
| Graph | Graph (adjacency matrix) | Weighted, directed or undirected, with BFS and DFS | graphmatrix.h |
| Graph | Graph (adjacency list) | Weighted, directed or undirected, with BFS and DFS | graphlist.h |
| Graph | Disjoint Set (Union-Find) | Union by rank and path compression | disjointset.h |
| Type | Algorithms | File |
|---|---|---|
| Searching | Linear search, binary search (iterative and recursive) | searching.h |
| Sorting | Bubble, selection, insertion, merge, quick and heap sort | sorting.h |
| Graphs | Dijkstra (with the priority queue), Prim, Kruskal (with the disjoint set) | graphalgorithms.h |
The structures above work with int. The Generic folder has template versions of the Array, Stack, Queue, Linked List and Binary Search Tree that work with any type (double, char, std::string, your own types...). They use the same function names, so pushStack(&stack, 3.5) works with a GenericStack<double> and the int and generic versions can be used in the same program.
n is the number of elements, L the length of a word, V the number of vertices and E the number of edges.
| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(1) at the end, O(n) at a position | O(n) | Fixed maximum size |
| Dynamic Array | O(1) | O(n) | O(1) amortized at the end, O(n) at a position | O(n) | Grows by doubling |
| Stack / Linked Stack | O(1) top | - | O(1) push | O(1) pop | |
| Queue / Linked Queue | O(1) front | - | O(1) enqueue | O(1) dequeue | |
| Deque | O(1) both ends | - | O(1) both ends | O(1) both ends | |
| Linked List | O(n) | O(n) | O(1) head, O(n) tail | O(n) | |
| Doubly Linked List | O(n) | O(n) | O(1) both ends | O(1) both ends, O(n) by value | |
| Circular Linked List | O(n) | O(n) | O(1) head and tail | O(1) head, O(n) by value | Rotate in O(1) |
| Binary Search Tree | - | O(log n) avg, O(n) worst | O(log n) avg, O(n) worst | O(log n) avg, O(n) worst | Traversals O(n) |
| AVL Tree | - | O(log n) | O(log n) | O(log n) | Always balanced |
| Heap | O(1) top | O(n) | O(log n) | O(log n) extract | Build from an array in O(n) |
| Priority Queue | O(1) top | - | O(log n) | O(log n) | |
| Trie | - | O(L) | O(L) | O(L) | Prefix search O(L) |
| Hash Table (chaining) | - | O(1) avg, O(n) worst | O(1) avg, O(n) worst | O(1) avg, O(n) worst | |
| Hash Table (open addressing) | - | O(1) avg, O(n) worst | O(1) avg, O(n) worst | O(1) avg, O(n) worst | Fixed number of slots |
| Set | - | O(1) avg | O(1) avg | O(1) avg | Union, intersection and difference O(n + m) avg |
| Graph (matrix) | - | O(1) edge | O(1) edge | O(1) edge | BFS/DFS O(V²), memory O(V²) |
| Graph (list) | - | O(V) edge | O(V) edge | O(V) edge | BFS/DFS O(V + E), memory O(V + E) |
| Disjoint Set | - | ~O(1) find | - | - | ~O(1) union (inverse Ackermann) |
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) | - |
| Binary search | O(1) | O(log n) | O(log n) | O(1) iterative, O(log n) recursive | - |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Dijkstra (matrix + priority queue) | O(V² + E log E) | O(V + E) | - | ||
| Prim (matrix) | O(V²) | O(V) | - | ||
| Kruskal | O(E log E) | O(V + E) | - |
DataStructures/
├── LinearDataStructures/
│ ├── StaticDataStructure/ Array
│ └── DynamicDataStructure/ DynamicArray, Stack, LinkedStack, Queue, LinkedQueue, Deque,
│ LinkedList, DoublyLinkedList, CircularLinkedList
├── NonLinearDataStructures/
│ ├── Tree/ BinarySearchTree, AVLTree, Heap, PriorityQueue, Trie
│ ├── Hash/ HashTableChaining, HashTableOpenAddressing, Set
│ └── Graph/ GraphMatrix, GraphList, DisjointSet
└── Generic/ GenericArray, GenericStack, GenericQueue,
GenericLinkedList, GenericBinarySearchTree
Algorithms/
├── Searching/ searching.h
├── Sorting/ sorting.h
└── Graph/ graphalgorithms.h
Tests/
├── test.h Small testing library (CHECK, CHECK_EQUAL, CHECK_ARRAY)
├── LinearDataStructures/ One test file per structure or algorithm file
├── NonLinearDataStructures/
├── Algorithms/
└── Generic/
CMakeLists.txt Builds every test and registers it in CTest
Every test checks the results automatically (expected value against obtained value) and returns 0 only if all the checks pass.
With CMake (any compiler):
cmake -S . -B build
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failureOr compile a single test by hand from the root of the repository:
g++ Tests/LinearDataStructures/test_stack.cpp -o test_stack
./test_stack- One structure per
.hfile, protected with an include guard ending in_JL. - Structures are defined with
typedef structand initialised with aninitXfunction. - Functions return
1if the operation is successful or0if it is not. Values are returned through a pointer parameter. - Every function has a short comment explaining what it does and what it returns.
- Every structure has a
printXfunction that displays its elements as[1, 2, 3]. - Each header has its own size constant (
ARRAY_MAX_SIZE,STACK_MAX_SIZE...) and its own function names, so any headers can be included together. - Structures that reserve memory have a
freeXfunction that releases it.
MIT. See LICENSE.
Una colección de estructuras de datos y algoritmos clásicos escritos desde cero en C++ con estilo C. Cada estructura vive en su propio archivo .h, sigue las mismas convenciones y tiene su propia prueba automática, de forma que el código sea fácil de leer, de comparar y de comprobar.
| Estructura | Descripción | Archivo |
|---|---|---|
| Array | Array estático con un tamaño máximo fijo | array.h |
| Array dinámico | Array que duplica su capacidad con realloc cuando se llena |
dynamicarray.h |
| Pila (Stack) | Pila LIFO almacenada en un array | stack.h |
| Pila con nodos | Pila construida con nodos, sin límite de tamaño | linkedstack.h |
| Cola (Queue) | Cola FIFO circular almacenada en un array | queue.h |
| Cola con nodos | Cola construida con nodos, sin límite de tamaño | linkedqueue.h |
| Deque | Cola circular que inserta y extrae por ambos extremos | deque.h |
| Lista enlazada | Lista simplemente enlazada | linkedlist.h |
| Lista doblemente enlazada | Nodos con prev y next, con cabeza y cola |
doublylinkedlist.h |
| Lista enlazada circular | El último nodo apunta al primero | circularlinkedlist.h |
| Tipo | Estructura | Descripción | Archivo |
|---|---|---|---|
| Árbol | Árbol binario de búsqueda | Insertar, buscar, eliminar, mínimo, máximo, altura y cuatro recorridos (in, pre, post y por niveles) | binarysearchtree.h |
| Árbol | Árbol AVL | BST que se mantiene equilibrado mediante rotaciones | avltree.h |
| Árbol | Heap | Heap de mínimos o de máximos almacenado en un array | heap.h |
| Árbol | Cola de prioridad | Heap de mínimos de pares (valor, prioridad) | priorityqueue.h |
| Árbol | Trie | Árbol de prefijos para palabras en minúsculas | trie.h |
| Hash | Tabla hash (encadenamiento) | Cada posición es una lista enlazada de pares (clave, valor) | hashtablechaining.h |
| Hash | Tabla hash (direccionamiento abierto) | Sondeo lineal con marcas de borrado | hashtableopenaddressing.h |
| Hash | Conjunto (Set) | Conjunto sobre la tabla hash: unión, intersección, diferencia y subconjunto | set.h |
| Grafo | Grafo (matriz de adyacencia) | Con pesos, dirigido o no dirigido, con BFS y DFS | graphmatrix.h |
| Grafo | Grafo (lista de adyacencia) | Con pesos, dirigido o no dirigido, con BFS y DFS | graphlist.h |
| Grafo | Conjuntos disjuntos (Union-Find) | Unión por rango y compresión de caminos | disjointset.h |
| Tipo | Algoritmos | Archivo |
|---|---|---|
| Búsqueda | Búsqueda lineal, búsqueda binaria (iterativa y recursiva) | searching.h |
| Ordenación | Burbuja, selección, inserción, merge sort, quick sort y heap sort | sorting.h |
| Grafos | Dijkstra (con la cola de prioridad), Prim, Kruskal (con los conjuntos disjuntos) | graphalgorithms.h |
Las estructuras anteriores trabajan con int. La carpeta Generic contiene versiones con plantillas del Array, la Pila, la Cola, la Lista enlazada y el Árbol binario de búsqueda que funcionan con cualquier tipo (double, char, std::string, tipos propios...). Usan los mismos nombres de función, así que pushStack(&stack, 3.5) funciona con un GenericStack<double> y las versiones int y genéricas se pueden usar en el mismo programa.
n es el número de elementos, L la longitud de una palabra, V el número de vértices y E el número de aristas.
| Estructura | Acceso | Búsqueda | Inserción | Borrado | Notas |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(1) al final, O(n) en una posición | O(n) | Tamaño máximo fijo |
| Array dinámico | O(1) | O(n) | O(1) amortizado al final, O(n) en una posición | O(n) | Crece duplicando |
| Pila / Pila con nodos | O(1) cima | - | O(1) push | O(1) pop | |
| Cola / Cola con nodos | O(1) frente | - | O(1) encolar | O(1) desencolar | |
| Deque | O(1) ambos extremos | - | O(1) ambos extremos | O(1) ambos extremos | |
| Lista enlazada | O(n) | O(n) | O(1) cabeza, O(n) cola | O(n) | |
| Lista doblemente enlazada | O(n) | O(n) | O(1) ambos extremos | O(1) ambos extremos, O(n) por valor | |
| Lista enlazada circular | O(n) | O(n) | O(1) cabeza y cola | O(1) cabeza, O(n) por valor | Rotar en O(1) |
| Árbol binario de búsqueda | - | O(log n) medio, O(n) peor | O(log n) medio, O(n) peor | O(log n) medio, O(n) peor | Recorridos O(n) |
| Árbol AVL | - | O(log n) | O(log n) | O(log n) | Siempre equilibrado |
| Heap | O(1) cima | O(n) | O(log n) | O(log n) extraer | Construir desde un array en O(n) |
| Cola de prioridad | O(1) cima | - | O(log n) | O(log n) | |
| Trie | - | O(L) | O(L) | O(L) | Búsqueda de prefijo O(L) |
| Tabla hash (encadenamiento) | - | O(1) medio, O(n) peor | O(1) medio, O(n) peor | O(1) medio, O(n) peor | |
| Tabla hash (direccionamiento abierto) | - | O(1) medio, O(n) peor | O(1) medio, O(n) peor | O(1) medio, O(n) peor | Número fijo de posiciones |
| Conjunto | - | O(1) medio | O(1) medio | O(1) medio | Unión, intersección y diferencia O(n + m) medio |
| Grafo (matriz) | - | O(1) arista | O(1) arista | O(1) arista | BFS/DFS O(V²), memoria O(V²) |
| Grafo (lista) | - | O(V) arista | O(V) arista | O(V) arista | BFS/DFS O(V + E), memoria O(V + E) |
| Conjuntos disjuntos | - | ~O(1) find | - | - | ~O(1) union (inversa de Ackermann) |
| Algoritmo | Mejor | Medio | Peor | Memoria extra | Estable |
|---|---|---|---|---|---|
| Búsqueda lineal | O(1) | O(n) | O(n) | O(1) | - |
| Búsqueda binaria | O(1) | O(log n) | O(log n) | O(1) iterativa, O(log n) recursiva | - |
| Burbuja | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Selección | O(n²) | O(n²) | O(n²) | O(1) | No |
| Inserción | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Dijkstra (matriz + cola de prioridad) | O(V² + E log E) | O(V + E) | - | ||
| Prim (matriz) | O(V²) | O(V) | - | ||
| Kruskal | O(E log E) | O(V + E) | - |
DataStructures/
├── LinearDataStructures/
│ ├── StaticDataStructure/ Array
│ └── DynamicDataStructure/ DynamicArray, Stack, LinkedStack, Queue, LinkedQueue, Deque,
│ LinkedList, DoublyLinkedList, CircularLinkedList
├── NonLinearDataStructures/
│ ├── Tree/ BinarySearchTree, AVLTree, Heap, PriorityQueue, Trie
│ ├── Hash/ HashTableChaining, HashTableOpenAddressing, Set
│ └── Graph/ GraphMatrix, GraphList, DisjointSet
└── Generic/ GenericArray, GenericStack, GenericQueue,
GenericLinkedList, GenericBinarySearchTree
Algorithms/
├── Searching/ searching.h
├── Sorting/ sorting.h
└── Graph/ graphalgorithms.h
Tests/
├── test.h Pequeña librería de pruebas (CHECK, CHECK_EQUAL, CHECK_ARRAY)
├── LinearDataStructures/ Un archivo de pruebas por estructura o archivo de algoritmos
├── NonLinearDataStructures/
├── Algorithms/
└── Generic/
CMakeLists.txt Compila todas las pruebas y las registra en CTest
Cada prueba comprueba los resultados automáticamente (valor esperado frente a valor obtenido) y devuelve 0 solo si todas las comprobaciones pasan.
Con CMake (cualquier compilador):
cmake -S . -B build
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failureO compila una sola prueba a mano desde la raíz del repositorio:
g++ Tests/LinearDataStructures/test_stack.cpp -o test_stack
./test_stack- Una estructura por archivo
.h, protegido con un include guard terminado en_JL. - Las estructuras se definen con
typedef structy se inicializan con una funcióninitX. - Las funciones devuelven
1si la operación tiene éxito o0si no. Los valores se devuelven a través de un parámetro puntero. - Cada función tiene un comentario breve que explica qué hace y qué devuelve.
- Cada estructura tiene una función
printXque muestra sus elementos como[1, 2, 3]. - Cada cabecera tiene su propia constante de tamaño (
ARRAY_MAX_SIZE,STACK_MAX_SIZE...) y sus propios nombres de función, así que se pueden incluir varias cabeceras a la vez. - Las estructuras que reservan memoria tienen una función
freeXque la libera.
MIT. Consulta LICENSE.