👋 Welcome to the "Implementations of Data Structures" repository! This repository contains various implementations of common data structures in C++. These data structures include:
:small_blue_diamond: Linked lists
:small_blue_diamond: Stacks
:small_blue_diamond: Queues
:small_blue_diamond: Trees
Each data structure is implemented as a standalone class, with member functions for common operations such as insertion, deletion, printing and searching. The implementation is designed to be easy to understand and use, with well-documented code and clear function names. The different structures are all templated, currently supporting the following types: integer, float, double, char and std::string.
This repository is a great resource for anyone looking to learn about data structures or brush up on their skills. Whether you are a beginner or an experienced programmer, you will find something of value here. I hope you enjoy and let's dive straight into it!
A hash table is a data structure that stores a set of key-value pairs and uses a hash function to map keys to indices in an array. When a key-value pair is inserted into the hash table, the hash function is used to determine the index in the array where the value should be stored. If the index is already occupied by another value, then the hash table uses a collision resolution strategy to find an alternative location for the value.
With this implementation, we are handling collisions with a closed addressing method utilizing linked lists. To put it simply, whenever a value needs to go into a space where we already have something, we will just attach it to the end of the linked list there. The table that is implemented here is using integers as keys and linked lists as values. The nodes in these lists are storing strings.
- The hash method that we are using is the FNV-1a algorithm, this method does not have to be used but has been proven to produce good hash values
Implementation currently supports the following methods:
:small_blue_diamond: Calculate a hash key for any given string value
:small_blue_diamond: Insert a value (no duplicates allowed)
:small_blue_diamond: Remove a value
:small_blue_diamond: Check if the table is empty
:small_blue_diamond: Print all key/value pairs
:small_blue_diamond: Use iterators to traverse the table
This is a data structure consists of two parts - individual nodes and a class for the list itself. Nodes are very simple, each has these key elements:
- Data represented in that node
- Pointer to the next node in the chain
- Pointer to the previous node in the chain
We only use the previous node pointer when we are dealing with doubly linked lists, in singly linked ones this information is not needed. Lists themselves have just the information about the first node in that list, called the head, which is used for traversal alongside the entire list. This is done by utilizing the 'next node' pointer when assembling the list. The end of the list is called the tail, this is the node that has the next pointer set to nullptr, which means the list is null-terminated.
Implementation currently supports singly and doubly linked lists that are implemented with the following features:
:small_blue_diamond: Append/Prepend a node
:small_blue_diamond: Remove head/tail node
:small_blue_diamond: Insert/delete a node in a desired position
:small_blue_diamond: Print all node values in the list
:small_blue_diamond: Use iterators for traversing from one node to the next
An n-ary tree is a tree data structure in which each node has at most n children. N-ary trees are a generalization of binary trees, which are trees in which each node has at most two children. Each node has two parts:
- Data that is stored inside the node
- An array of all the children of that node
The class for the tree itself just stores the information about the first node in the tree, called the root node. Every other node is accessed by traversing the tree using this root node. Common traversals include:
🔹 Pre-order traversal: In a pre-order traversal, the root node is visited first, followed by the subtrees of the left child, then the subtrees of the right child.
🔹 In-order traversal: In an in-order traversal, the left subtree of the root node is visited first, followed by the root node itself, then the right subtree.
🔹 Post-order traversal: In a post-order traversal, the subtrees of the left child are visited first, followed by the subtrees of the right child, and finally the root node is visited.
🔹 Level-order traversal: In a level-order traversal, the nodes of the tree are visited level by level, starting from the root node and proceeding through the levels from top to bottom.
Implementation currently supports the following methods:
:small_blue_diamond: Add a child node to an existing one
:small_blue_diamond: Insert a child node at a specific place
:small_blue_diamond: Remove a child node at a specific index
:small_blue_diamond: Preorder/Postorder traversal
:small_blue_diamond: Print all node values in the tree
:small_blue_diamond: Access the size of the tree (total nodes)
I have also included the Graphviz library here for generating the visual representation of the tree. This library is used by first generating the dot file and then using it to produce a png file.
Example picture:
A stack is a linear data structure that allows elements to be added and removed only from the top of the stack. This behavior is known as last-in, first-out (LIFO) and is similar to a stack of plates in a cafeteria. Here we are implementing it with the std::vector container, but the STL library does offer it's own std::stack.
Implementation currently supports the following methods:
:small_blue_diamond: Push a new value onto the stack
:small_blue_diamond: Pop a value from the top of the stack
:small_blue_diamond: Get the value located at the top
:small_blue_diamond: Check whether a stack is empty or not
:small_blue_diamond: Print all values in the stack
:small_blue_diamond: Use iterators for travering the stack
A queue is a linear data structure that allows elements to be added only to the back of the queue and removed only from the front of the queue. This behavior is known as first-in, first-out (FIFO) and is similar to a line of people waiting in line at the mall. We are implementing it here with the std::vector container, similarly to how we did the stack.
Implementation currently supports the following methods:
:small_blue_diamond: Push a new value onto the queue
:small_blue_diamond: Pop a value from the front of the queue
:small_blue_diamond: Get the value located at the front
:small_blue_diamond: Check whether a queue is empty or not
:small_blue_diamond: Print all values in the queue
:small_blue_diamond: Use iterators for travering the queue