Data Structures: Arrays, Lists, Stacks, Queues, Trees and Hash Tables

  • Data structures are fundamental components of computer science and bioinformatics because they determine how information is organized, stored, accessed, modified, and processed by computational algorithms. Modern biological research generates large quantities of data, including DNA and RNA sequences, protein sequences, gene expression measurements, genetic variants, molecular interaction networks, and biological annotations. Efficient data structures enable researchers to manage these datasets, improve algorithm performance, reduce memory consumption, and develop scalable analytical workflows. Understanding arrays, lists, stacks, queues, trees, and hash tables provides an essential foundation for programming, algorithm design, and computational problem-solving in bioinformatics.
  • A data structure is a systematic way of organizing data so that specific operations can be performed efficiently. These operations include accessing individual elements, searching for values, inserting new elements, deleting existing elements, sorting information, and traversing collections. Different data structures support different operations with different computational costs. For example, arrays provide efficient access to elements at known positions, linked lists support flexible insertion and deletion when the relevant location is known, queues manage data in the order it arrives, trees represent hierarchical relationships, and hash tables support rapid lookup using keys. Selecting the appropriate data structure depends on the nature of the biological problem, the size of the dataset, the frequency of different operations, and the available computational resources.
  • Data structures are commonly classified as linear or non-linear. Linear data structures organize elements in a sequential arrangement, as seen in arrays, linked lists, stacks, and queues. Non-linear structures organize information through hierarchical or interconnected relationships, as seen in trees and graphs. Data structures may also be classified as static or dynamic, depending on whether their size is fixed or can change during execution. Arrays often provide contiguous storage and efficient indexed access, whereas linked lists allocate individual nodes connected through references or pointers. Hash tables use a mapping between keys and storage locations, while trees represent parent–child relationships or ordered collections. These distinctions influence memory usage, access speed, and implementation complexity.
  • Arrays are among the simplest and most widely used data structures. An array stores a collection of elements in an indexed sequence, usually with elements of the same or compatible data type. In many programming languages, arrays use contiguous memory locations, allowing the position of an element to be calculated directly from its index. Accessing an element by index generally takes (O(1)) time, while searching an unsorted array for a particular value typically requires (O(n)) time. Inserting or deleting an element in the middle of an array may require shifting other elements, resulting in (O(n)) time in the general case. The precise costs depend on the language, array implementation, and operation being performed.
  • Arrays are particularly useful in bioinformatics because many biological datasets naturally contain ordered measurements. A DNA sequence can be represented as an array of nucleotide symbols, while a protein sequence can be stored as a sequence of amino acid symbols. Gene expression measurements may be organized into arrays or multidimensional matrices, with genes represented along one dimension and samples along another. Numerical arrays are also widely used for storing quality scores, substitution matrices, genomic coordinates, and statistical results. Scientific computing libraries provide optimized array operations that can process large collections of numerical values efficiently.
  • For example, a DNA sequence represented as a string or character array can be examined to count nucleotides. The algorithm scans each position, increments the corresponding nucleotide counter, and produces the frequency of each base. If the sequence length is (n), this operation takes (O(n)) time. When only a fixed number of counters is required, the auxiliary memory is (O(1)), excluding storage for the input sequence. This illustrates how an appropriate representation can make a biological computation straightforward and efficient.
  • Multidimensional arrays extend the same principle to tables, matrices, and higher-dimensional datasets. A gene expression matrix may contain rows representing genes and columns representing samples. Each entry records an expression measurement for a particular gene in a particular sample. Matrices are also used in sequence alignment, pairwise distance calculations, statistical modeling, and machine learning. Although matrices can require substantial memory when their dimensions are large, specialized numerical libraries, sparse matrix representations, and optimized matrix operations can improve performance. Sparse matrices are especially useful for single-cell RNA sequencing data, where many gene–cell combinations have zero or undetected expression values.
  • Lists are collections of elements arranged in a sequence. The term list has different meanings across programming languages: in Python, a list is a dynamic array, whereas a linked list consists of nodes connected by references. This distinction is important because the two structures have different performance characteristics. A dynamic array supports efficient indexed access and can grow as elements are added, although resizing may occasionally require allocating new memory and copying existing elements. A linked list stores elements in separate nodes, with each node containing data and one or more references to other nodes.
  • In a singly linked list, each node points to the next node. A doubly linked list stores references to both the next and previous nodes. Linked lists can support (O(1)) insertion or deletion when the relevant node and necessary references are already available. However, locating a particular element by position generally requires (O(n)) time because the list must be traversed sequentially. Linked lists also introduce memory overhead for references and often have poorer cache locality than arrays. Consequently, linked lists are useful in some dynamic applications but are not automatically more efficient than arrays for every task.
  • Lists can be used in bioinformatics to maintain collections of sequencing reads, candidate genes, identified variants, or analytical results. For example, a program may build a list of genes that meet a differential-expression threshold and then pass this collection to a downstream functional-enrichment procedure. A list is also useful when the number of collected items is not known in advance. In many real applications, however, dynamic arrays or specialized collection types provide a simpler and faster solution than linked lists. The choice should reflect the operations performed most frequently rather than the assumption that one structure is universally superior.
  • Stacks are linear data structures that follow the last-in, first-out (LIFO) principle. The most recently added element is the first one removed. A stack supports two primary operations: push, which adds an element to the top, and pop, which removes the top element. A peek or top operation retrieves the top element without removing it. These operations typically take (O(1)) time when the stack is implemented appropriately. A stack can be implemented using an array, a dynamic array, or a linked list, with implementation details determining memory behavior and any additional costs.
  • Stacks are useful whenever a process must reverse its order of access or track nested operations. In computational biology, they can support depth-first traversal of biological networks, parsing of nested expressions, and evaluation of mathematical formulas used in biological models. They can also be used in algorithms that process tree structures, explore possible solutions, or maintain a record of operations that may need to be reversed. Recursive algorithms implicitly use a call stack to store information about active function calls. Understanding stack behavior is therefore helpful when implementing recursive tree traversal, graph search, and certain sequence-processing algorithms.
  • Queues are linear data structures that follow the first-in, first-out (FIFO) principle. The earliest element added is the first one removed. A queue supports an enqueue operation for adding an element at the rear and a dequeue operation for removing an element from the front. Efficient implementations, such as circular buffers or linked queues, can perform these operations in (O(1)) time. By contrast, repeatedly removing the first element from a conventional array may require shifting the remaining elements and can take (O(n)) time per removal. The underlying implementation is therefore important when evaluating queue efficiency.
  • Queues are useful for managing tasks that must be processed in arrival order. In bioinformatics, queues can coordinate batches of sequencing reads, pending computational tasks, data-transfer operations, or jobs waiting for processing. They are also central to breadth-first search, a graph traversal algorithm that explores neighboring vertices level by level. Breadth-first search can be used to investigate connectivity in biological interaction networks or identify shortest paths in unweighted graphs. In large computational workflows, task queues help organize workloads and control how tasks are assigned to available resources.
  • Priority queues are a related structure in which elements are removed according to priority rather than insertion order. They are commonly implemented using heaps, with operations such as insertion and removal of the highest- or lowest-priority element often taking (O(\log n)) time. Priority queues can be useful in algorithms that repeatedly select the most promising candidate, such as certain graph algorithms, optimization procedures, and search strategies. In biological applications, they may help prioritize candidate variants, rank possible paths in a graph, or manage computational tasks according to estimated resource requirements. A priority queue should be distinguished from a standard FIFO queue because the removal order is determined by priority.
  • Trees are non-linear data structures that represent hierarchical relationships. A tree consists of nodes connected by edges, with a designated root node and branches leading to child nodes. Nodes without children are called leaves. Trees are widely used in computer science because they represent nested relationships and can support efficient searching, sorting, and traversal. Different tree structures have different properties, and their performance depends on how the tree is organized. A poorly balanced search tree may require linear-time operations, whereas a balanced search tree can support search, insertion, and deletion in (O(\log n)) time.
  • Binary trees are trees in which each node has at most two children, commonly called the left and right children. Binary search trees impose an ordering rule so that values in the left subtree are smaller than the node’s value and values in the right subtree are larger, subject to the implementation’s handling of duplicates. This structure supports efficient searching when the tree is balanced. Balanced variants, such as AVL trees and red–black trees, maintain structural conditions that prevent excessive height. Trees are also used to represent hierarchical biological classifications, nested annotations, and relationships among entities. However, evolutionary trees, such as phylogenetic trees, represent inferred biological relationships and should not be confused with binary search trees, which are primarily designed for computational operations.
  • Trees have numerous applications in bioinformatics. Phylogenetic trees represent hypothesized evolutionary relationships among organisms, genes, or sequences. Hierarchical clustering produces dendrograms that organize genes, samples, or proteins according to similarity. Trie structures store sequences or strings by sharing common prefixes, which can support efficient prefix-based searching. Suffix trees and related structures index substrings of sequences and can accelerate particular sequence-search tasks, although they may require substantial memory. Decision trees are used in machine learning to classify biological observations, such as predicting disease categories or assigning functional labels to genes. Each tree-based structure has a distinct purpose, and the choice depends on whether the goal is searching, indexing, classification, clustering, or representing biological relationships.
  • Hash tables are data structures that store information as key–value pairs. A hash function converts a key into a numerical value that determines a storage location or bucket. When a key is supplied, the hash table uses the hash function to locate the associated value without scanning the entire collection. Under suitable assumptions, insertion, lookup, and deletion have expected (O(1)) time complexity. However, collisions occur when different keys map to the same location. Hash tables must therefore use collision-resolution methods, such as chaining or open addressing. In the worst case, severe collisions can cause operations to approach (O(n)), depending on the implementation.
  • Hash tables are particularly useful in bioinformatics for mapping identifiers to biological information. A gene identifier may map to its gene name, chromosome location, functional annotation, or expression summary. A sequence identifier may map to the corresponding sequence, while a variant identifier may map to its genomic coordinates and associated metadata. Hash tables are also useful for counting k-mers, storing nucleotide frequencies, detecting repeated identifiers, and linking records across biological databases. For example, a program can count occurrences of short DNA sequences by using each observed k-mer as a key and its occurrence count as the associated value. This approach avoids repeatedly scanning the complete collection to count each pattern.
  • The efficiency of a hash table depends on the hash function, collision-resolution strategy, table size, and distribution of keys. The load factor is the ratio of the number of stored entries to the number of available buckets or slots, depending on the implementation. As the load factor increases, collisions may become more frequent, potentially reducing performance. Many implementations expand the table and redistribute entries when a threshold is reached. Hash tables also have limitations: they do not normally maintain keys in sorted order, and they may use more memory than a compact array. They are most useful when rapid lookup by a key is more important than preserving a particular order.
  • The major characteristics of these data structures can be summarized as follows. The time complexities shown are typical values for common implementations and should be interpreted according to the stated assumptions.
Data structureMain principleTypical efficient operationCommon use in bioinformatics
ArrayIndexed sequenceAccess by index: (O(1))DNA sequences, expression matrices
Dynamic array or listResizable ordered collectionAppend: amortized (O(1))Gene lists, read collections
Linked listNodes connected by referencesInsert or delete at a known node: (O(1))Dynamic collections in selected algorithms
StackLast-in, first-outPush and pop: (O(1))Depth-first search, parsing
QueueFirst-in, first-outEnqueue and dequeue: (O(1))Breadth-first search, task scheduling
Balanced search treeOrdered hierarchical structureSearch, insertion, deletion: (O(\log n))Ordered records and indexing
Hash tableKey–value mappingExpected lookup: (O(1))Gene annotation and k-mer counting
  • Choosing an appropriate data structure requires analyzing the operations that dominate the intended workflow. If an algorithm repeatedly accesses elements by numerical position, an array is often suitable. If it frequently inserts and removes elements at both ends, a deque or another specialized queue structure may be more appropriate. If it needs to retrieve records by unique identifiers, a hash table may be preferable. If elements must remain sorted while insertions and deletions occur, a balanced search tree can provide predictable logarithmic performance. If the data represent hierarchical relationships, a tree may be the most natural representation. The optimal choice depends on data size, memory constraints, required ordering, and the frequency of searches, updates, and traversals.
  • In practice, data structures are frequently combined to solve biological problems. A genome assembly program may use hash tables to count k-mers, arrays to store numerical information, graphs to represent connections, and priority queues to select candidate operations. A gene expression pipeline may use matrices for measurements, hash tables to map gene identifiers to annotations, lists to store selected genes, and trees to represent hierarchical clustering results. A protein interaction analysis may store a graph using adjacency lists while using hash tables to map protein identifiers to node indices. Combining suitable structures allows each stage of an analysis to use a representation that supports its required operations efficiently.
  • Data structures also influence memory usage. Arrays can store elements compactly, particularly when they use fixed-width numerical types. Linked lists require additional memory for pointers or references. Hash tables allocate storage for buckets and may retain unused capacity to preserve performance. Trees require storage for nodes and their connections, while graph representations can consume considerable memory when networks are large. In bioinformatics, where datasets may contain millions of reads or millions of cells, memory overhead can determine whether an analysis is feasible. Researchers should therefore consider both the time and space complexity of the data structure and the practical costs of its implementation.
  • Programming languages provide different built-in data structures and libraries. Python includes lists, tuples, dictionaries, sets, and specialized collections such as deque. Python lists are dynamic arrays rather than linked lists, while dictionaries provide hash-based key–value lookup. NumPy provides efficient multidimensional arrays for numerical computing, and scientific libraries supply sparse matrices and graph representations. In C and C++, arrays, vectors, linked structures, queues, stacks, maps, and hash maps can be used to implement efficient algorithms. R provides vectors, lists, matrices, data frames, and specialized structures for statistical analysis. Understanding how each language implements a data structure helps researchers select suitable tools and interpret performance correctly.
  • Correctness and data integrity remain essential when working with data structures. Algorithms must handle empty collections, duplicate keys, missing values, unexpected input sizes, and invalid biological records according to their specifications. For example, a hash table used for gene annotations must define how duplicate gene identifiers are handled, while a sequence array must preserve the correct order of nucleotide positions. Tests should verify that insertion, deletion, lookup, and traversal operations behave as expected. Researchers should also benchmark implementations using representative biological datasets because theoretical complexity alone cannot predict every practical performance difference.
  • In summary, arrays, lists, stacks, queues, trees, and hash tables provide essential mechanisms for organizing and processing biological information. Arrays support efficient indexed access, lists manage ordered collections, stacks and queues control processing order, trees represent hierarchical structures and support ordered searching, and hash tables enable rapid key-based lookup. These structures form the foundation of many algorithms used in sequence analysis, genome assembly, gene expression studies, protein analysis, and biological network research. Understanding their properties, time and space complexities, and appropriate applications helps bioinformatics researchers design computational solutions that are efficient, scalable, reliable, and reproducible.
Author:

Leave a Reply

Your email address will not be published. Required fields are marked *