Data Structures: Fundamental Building Blocks in Computer Science

Arrays

Arrays are fundamental data structures in programming. They store collections of elements of the same type. The focus is to provide a way to organise data efficiently for easy access and manipulation.

In an array, elements are stored sequentially in contiguous memory locations. Each element is accessed by its index (position) within the array. The index usually starts from 0 and goes up to the length of the array minus one. This means the first element in an array is at index 0, the second element at index 1, and so on. They can be of fixed size, meaning their length is predetermined and cannot be changed once the array is created. Or they can be dynamic, where the length can be altered during the program’s execution.

Linked Lists

Linked lists are a fundamental data structure in computer science for storing collections of data. Unlike arrays, which store elements in contiguous memory locations, linked lists store elements in nodes, where each node contains a reference (or a pointer) to the next node in the sequence.

There are different types of linked lists, but the most common ones are: Singly Linked List, Doubly Linked List, and Circular Linked List.

In a singly linked list, each node contains data and a reference to the next node in the sequence. The last node points to null, indicating the end of the list. In a doubly linked list, each node contains an additional reference to the previous node as well as the next node. This allows traversal in both directions. In a circular linked list, the last node points back to the first node, forming a circle. This can be either a singly or doubly linked list.

Stacks

Stacks are a fundamental data structure in computer science. They follow the Last In, First Out (LIFO) principle. Just like a stack of plates, where you can only take the topmost plate off, a stack data structure allows operations on the topmost element only.

Operations in a stack can add (push) or remove (pop) the top element in the stack. Return the top element without removing it. Check if the stack is empty. And return the number of elements within the stack.

Stacks are used in various applications including expression evaluation, backtracking algorithms, syntax parsing, function call management (call stack), and undo mechanisms in text editors, among others. Find out how to implement a stack in Python coding.

Queues

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are analogous to lines in real life, where the first person in line is the first to be served.

Elements are processed in the order they were added. Operations: adding (enqueue) an element to the end of the queue and removing (dequeue) an element from the front of the queue. In addition, accessing the front element without removing it, checking if the queue is empty, and getting the number of elements in the queue.

There are simple queues, circular queues, priority queues, and double-ended queues. Common usage cases are task scheduling, breadth first search, print spooling, and buffering. Learn about coding queues in Python.

Trees

A tree is a widely-used data structure in computer science that simulates a hierarchical tree structure with a set of connected nodes.

Trees have several characteristics: root node, child node, parent node, leaf node, internal node, subtree, edge depth, height, and degree.

There are multiple types of trees, such as: binary tree, binary search tree, AVL tree, B-Tree, Red-Black tree, and more. Common uses are efficient searching, insertion, and deletion operations, efficient retrieval of keys in a dataset of strings, and database indexing and filesystem storage.

Graphs

A graph is a fundamental data structure in computer science and mathematics used to model relationships between objects. The two main components are vertices (nodes) and edges (links).

Vertices are individual objects or entities in the graph. Each vertex represents a unique object. Edges are he connections between pairs of vertices. An edge signifies a relationship or link between the vertices it connects.

There are multiple types of graphs. Such as Simple graph, Directed graph, Undirected graph, Weighted graph, Unweighted graph, Multigraph, and more. Graphs apply in various applications. For example, social networks, computer networks, web page ranking, transport networks, biological networks, and others.

Hash Tables

A hash table (or hash map) is a data structure that provides efficient access to data using a technique called hashing. It is widely used for implementing associative arrays, sets, and other data structures requiring fast lookups, insertions, and deletions.

Three key components: key-value pairs, hash function, and buckets. Hash tables apply in databases, for indexing to quickly locate records. In caches, to store frequently accessed data for rapid retrieval. In sets, for implementing sets where quick membership testing is required. Or symbol tables, used in compilers and interpreters to store variable names and values.

Heaps

A heap is a specialised tree-based data structure that satisfies the heap property. There are two main types of heaps: min-heaps and max-heaps.

In a min-heap, the key of the parent node is always less than or equal to the keys of its children. The smallest key is at the root of the heap. In a max-heap, the key of the parent node is always greater than or equal to the keys of its children. The largest key is at the root of the heap.

Applications extend to implementation of priority queues, supporting comparison-based sorting algorithms to sort elements, and applying in several graph algorithms. Explore a code building tutorial about heaps in Python.

Trie

A trie, also known as a prefix tree or digital tree, is a type of search tree used to store a dynamic set or associative array where the keys are usually strings. It is a specialised tree data structure that provides efficient storage and retrieval operations.

The root node represents an empty string. Keys are the paths from the root node to the leaf nodes. Nodes represent prefix characters from the keys. And edges flow the single characters from the keys.

Some applications of a trie are: autocomplete systems (suggest words), spell checking (look up valid words), IP routing (store routing tables), and DNA sequencing (store sequences of nucleotides).

Priority Queues

A priority queue is a specialised data structure that operates similarly to a regular queue or stack, but with an added feature. Each element is associated with a priority. Elements are served based on their priority rather than their order in the queue.

Each element in the priority queue has a priority level. Elements with higher priority are dequeued before elements with lower priority. Insertion and deletion operations ensure that the element with the highest priority is always at the front of the queue. The priority queue is an abstract data type, meaning its implementation can vary, but its behaviour is defined by the operations it supports.

Common applications are CPU scheduling, data compression algorithms, and in graph algorithms for finding the shortest path.

Skip Lists

Skip Lists are a data structure that combines elements of both linked lists and balanced trees to allow fast search, insertion, and deletion operations. They are particularly useful for ordered sequences of elements.

A skip list is built on top of a sorted linked list with multiple layers, where each layer is a “sub-list” of the layers below it.

Bottom Layer is the original sorted linked list. Each higher layer contains a subset of the elements from the layer immediately below it, with pointers (or “forward links”) that skip over many elements, hence the name “skip list.”

Popular use cases for skip lists are indexing large amounts of data. network applications, and memory-efficient algorithms.

Bloom Filters

Bloom filters are a probabilistic data structure that test whether an element is a member of a set. It can efficiently determine membership, with a trade-off between space and accuracy.

A Bloom filter is composed of bit array and hash function. A fixed-size array of bits initialized to 0. A set of “k” independent hash functions, each of which maps an element to one of the “m” positions in the bit array uniformly at random.

Applications of bloom filters extend to databases, web browsers, network security, and distributed systems.

Disjoint Sets

Disjoint Sets, also known as Union-Find data structures, keep track of a partition of a set into disjoint (non-overlapping) subsets. They support two primary operations efficiently, find and union.

Find determines which subset a particular element is in. This can be used for determining if two elements are in the same subset. And union joins two subsets into a single subset.

Popular use cases are in algorithms that deal with partitioning, network connectivity, and image processing.

Segment Trees

Segment Trees are advanced data structures used for answering range queries and updating elements in an array efficiently. They are particularly useful in scenarios where there are frequent updates and queries on an array.

Segment Trees are binary trees where each node represents an interval or segment of the array. The root of the tree represents the entire array, and each leaf node represents a single element in the array.

Uses cases apply in machine learning, computational geometry, and geographic information systems.

Suffix Trees and Arrays

A suffix tree is a compressed trie (a type of tree data structure) that represents all the suffixes of a given string. It allows for efficient pattern matching and is widely applicable in various string processing applications.

A suffix array is a sorted array of all suffixes of a given string. It is a simpler and more space-efficient alternative to the suffix tree.

Suffix trees apply in substring search and genome sequencing. Suffix arrays’ use cases extend to data compression, pattern matching, and text indexing.