Linked list, queues, and arrays
Linked lists are a series of data structures attached using special connections called links. These lists contain items and are some of the most commonly used data structures today. Each link stores a type of data called an element and a link to the adjacent link called Next. Linked lists can be of many types. The most common ones include a simple linked list in which the navigation of an item is forward only and a doubly-linked list in which navigation of items is done both forward and backward. There is also a circular linked list in which the first element contains a connection to the last element (previous) and the last item has a connection to the first element (next).
Queues are linear data structures or abstract data types whereby the first item is inserted on one end called the tail (rear) and the removal of items is done from the opposite end called the head (front). This structure makes queues a First in First Out (FIFO) data structure, meaning, the items inserted first are removed first. The process of adding items to the queue is referred to as en queueing and that of removing items from the queue is referred to as dequeuing. Some of the applications of queues include processing requests for single-shared resources like CPU tasks scheduling and handling interrupts in real-time systems.
Arrays are simply data structures that store a collection of elements. The elements stored in arrays are typical of a similar data type such as a string or integer. Computer programs use arrays to sort data, which makes searching related values much easier. Elements in an array are accessed by referring to their index number. Index number referencing is also done when changing the values of elements in an array.
Hashing
Hashing is basically converting a specific key into a different value. The process involves the use of mathematical algorithms, and the algorithm used to create the new value is referred to as the hash function. The resulting new value is called a hash value. Hash algorithms are one way, meaning, once a value has been converted, it cannot be changed back to the initial key. Hashing is commonly implemented to create hash tables. These tables store key/value pairs in a list form, where each element can be accessed and processed using an index. This technique of storing data is valuable in preventing the tampering of files.
Dynamic trees
Dynamic trees are data structures that have two components; the successor array and the path set. The successor array explains how different paths are connected and the path sets are a set of binary trees. Operations on dynamic trees are defined based on the path from a given node to the root. To perform these operations effectively, the vertices present in the path must be separated from other parts of the tree. Every path in a dynamic tree has a unique canonical node that helps identify the path. It is important to note that any given dynamic tree can be decomposed into many different paths. Nevertheless, one node cannot have more than two edges and if it does, one of the nodes must have a connection to its parent.
Cycle detection
Also known as cycle finding, cycle detection is an algorithm for locating a cycle in a series of iterated function values. There are two algorithms used in cycle detection: Floyd’s cycle detection algorithm and Brent’s cycle detection algorithm. These two algorithms apply the fast and slow pointer approach to identify a cycle. There are a few differences, however, that make one algorithm better than the other. For instance, Floyd’s algorithm is slower than Brent’s algorithm, making the latter a more preferred option by users looking for speed. Cycle detection is commonly used today to test the quality of cryptographic hash functions, pseudorandom number generators, and computational number theories.
Dynamic graphs
A dynamic graph is a graph that changes over time or goes through a sequence of updates over a given period. Its objective is to update the solution of a defined problem efficiently after dynamic changes instead of having to create a new graph every time the solution changes. Due to their powerful versatility, dynamic graphs are often more difficult to create, analyze, and interpret than their static counterparts. They can be classified based on the types or number of updates allowed. Essentially, a graph is said to be completely dynamic if the updates comprise of unrestricted deletions or insertions of vertices or edges. If the graph allows only a single type of update (either deletions or insertions), then it is considered partially dynamic.
