Data Structures

This is part 1 of our Data Structures and Algorithms series. This post focuses on Data Structures.

What are Data Structures?

Data structures are a ways of organizing, storing, and managing data in a computer so that it can be accessed and modified efficiently.

Some common types of data structures:

• Arrays
• Lists
• Trees

There’s a lot more data structures but this post focuses mainly on beginner knowledge.

What is an Array?

An array is a fundamental data structure used in programming to store a collection of elements of the same data type in a contiguous memory block (consecutive blocks of memory are allocated).

Each element is accessed using an index, representing its position within the array. They are widely used for tasks such as data storage, algorithm implementation, image processing, and more.

Arrays have a fixed size, making them suitable for scenarios where element counts remain consistent, for dynamic sizing and more complex data manipulation, other data structures might be more appropriate.

There’s a lot of programming languages that support Arrays: Java, Python, C++, Go, etc.

A series of key characteristics for arrays:

Homogeneous Elements - arrays contain elements of the same data type.

For example, you can create an array of integers, an array of characters, or an array of floating-point numbers.

Fixed Size - arrays have a fixed size.

You need to specify the number of elements they will hold when you create them. This size is determined at the time of declaration and cannot be easily changed.

Indexed Elements - each element in an array is uniquely identified by its index or position.

The index typically starts from 0 and goes up to (array size - 1).

Contiguous Memory Allocation - elements in an array are stored in contiguous memory locations.

This makes accessing elements efficient through direct indexing.

Efficient Access - accessing elements in an array is very efficient using their index.

Since the memory locations are contiguous, calculating the memory address of an element involves simple arithmetic.

Sequential Storage - elements are stored sequentially, one after another, in the order they were added.

This allows for efficient iteration through the array.

Direct Element Access - you can access any element in the array directly by using its index.

This provides constant-time (O(1)) access time.

Static Allocation - in many programming languages, arrays are statically allocated.

This means that the size of the array needs to be known at compile time. This can limit their flexibility, especially when the size of the data needs to change dynamically.

Common Operations - other tuning techniques besides indexes.

Queries can be analyzed, rewritten e.g. by using join tables to cimbine data, all of which optimizes the query performance.

Arrays in action - code examples

Here we prepared a straightforward example in Java of operations performed using Arrays, let’s look at the whole thing first:

public class ArrayExample {
    public static void main(String[] args) {
        // Array of strings
        String[] names = { "Alice", "Bob", "Charlie", "David", "Eve" };
        
        // Array of chars
        char[] characters = { 'A', 'B', 'C', 'D', 'E' };
        
        // Array of integers 
        int[] numbers = { 5, 10, 15, 20, 25 };
        
        // Array of boolean flags 
        boolean[] flags = { true, false, true, false, true };

        // Example of adding elements to array
        int[] elements = new int[3]; // Create an array with initial size 3

        // Adding elements to the array
        elements[0] = 5;
        elements[1] = 10;
        elements[2] = 15;
        
        System.out.println(elements[0]);
        System.out.println(elements[1]);
        System.out.println(elements[2]);
    }
}

And now let’s try to understand it step-by-step.

Array of Strings

String[] names = { "Alice", "Bob", "Charlie", "David", "Eve" };

This is an array of String values, containing five names. Each element is a String.

Array of Characters

char[] characters = { 'A', 'B', 'C', 'D', 'E' };

This is an array of char values. Each element is a character representing a letter.

Array of Integers

int[] numbers = { 5, 10, 15, 20, 25 };

This is an array of int values. Each element is an integer.

Array of Booleans

boolean[] flags = { true, false, true, false, true };

This is an array of boolean values, holding true or false values.

Creating an Array

int[] elements = new int[3];

A new array named elements of int type is created with a length of 3. Initially, it contains default values of 0 for each index because it’s an integer array.

Adding values to an Array

elements[0] = 5;
elements[1] = 10;
elements[2] = 15;

Here, values are added to each index of the elements array:

• elements[0] is assigned 5
• elements[1] is assigned 10
• elements[2] is assigned 15

It’s important to remember that in arrays indexes always start from 0.

Printing an Array

System.out.println(elements[0]);
System.out.println(elements[1]);
System.out.println(elements[2]);

These System.out.println statements print each value in the elements array:

• The first line prints 5
• The second line prints 10
• The third line prints 15

What Array can be used for?

There’s a wide variety of problems that can be solved with Array, of which the most common are:

Used to implement other data structures - e.g. lists, heaps, hash tables, queues, stacks, strings.

Arrays are the most basic data structures, it's easy to use them to implement other data structures.

Data Storage and Retrieval - used to store data that needs to be accessed and retrieved efficiently.

This includes tasks such as storing user information, product details, or any kind of records in databases.

Algorithm Implementation - the foundation for many algorithms.

Sorting algorithms like insertion sort, searching algorithms like binary search, and graph algorithms often rely on arrays to organize and manipulate data.

Numerical Computations - used for numerical computations.

In scientific and engineering applications, arrays are used for numerical computations. They allow for efficient processing of large datasets and mathematical operations like matrix multiplication, Fourier transforms, and solving linear equations.

Image and Signal Processing - vital for image and signal processing tasks.

Pixels in an image and samples in a signal are often represented using arrays. Operations like convolution (can be known from mathematics but in image processing it’s about transforming an image pixels across an entire image), filtering, and image manipulation rely on arrays.

Time-Series Analysis - used to represent time-series data.

Arrays are used to represent time-series data, such as stock prices, temperature readings, or sensor measurements over time. These arrays enable analysis and visualization of trends and patterns.

Game Development - used to store game states.

Arrays are used in game development to store game states, character attributes, map data, and more. They allow for efficient management of game-related information.

Data Analysis and Statistics - used for storing and analyzing data in statistics.

Arrays are used for storing and analyzing data in statistics. They form the basis for generating histograms, calculating means, medians, and standard deviations, and performing hypothesis testing.

Text Processing - used to represent strings as sequences of characters.

Arrays can represent strings as sequences of characters. They are used for tasks like searching, parsing, and manipulating textual data.

Machine Learning - used to store feature vectors and datasets.

Arrays are often used to store feature vectors and datasets in machine learning algorithms. They provide a convenient way to organize training and testing data for model training.

Graphical User Interfaces (GUIs) - used to store GUI elements.

GUI elements like buttons, menus, and text fields are often stored in arrays for easy management and event handling.

Lookup Tables - used as lookup tables.

Arrays can be used as lookup tables to store precomputed values for quick access. This is useful in applications where complex calculations can be replaced with simple array lookups.

Networking and Communication - used to store and manipulate data packets in network communications.

Arrays can be used to store and manipulate data packets in networking applications, such as sending and receiving messages or files over a network.

Quick summary

Think of Array as a list of boxes where each box has its own identification, which is represented by the index. The index can be used to add or extract information from a given box.

Arrays provide a structured and efficient way to manage and process data across a wide spectrum of programming tasks and domains. While their fixed size limitation can sometimes be a drawback, their simplicity and predictable performance make them an indispensable tool in software development.

What is a List?

A list is a linear data structure that stores a collection of elements. Unlike arrays, which are fixed in size, lists are often dynamic and can grow or shrink as needed.

Lists allow you to store and manage a sequence of elements, and they provide methods for adding, removing, and accessing elements efficiently.

Lists can be implemented using various underlying data structures, such as dynamic arrays, linked lists, or other resizable data structures.

There’s a lot of programming languages that support Arrays: Java, Python, C++, Go, etc.

A series of key characteristics for lists:

Dynamic Sizing - grow or shrink dynamically.

Lists can grow or shrink dynamically, meaning you can add or remove elements without specifying a fixed size upfront.

Insertion and Removal - efficient methods for inserting and removing.

Lists offer efficient methods for inserting and removing elements at different positions within the list.

Order Preservation - elements are stored in the order.

Elements in a list are typically stored in the order they were added, allowing for easy traversal and maintenance of sequences.

Element Access - fast access by index.

Lists provide methods for accessing elements by their index or position in the list.

Resizing - automatic memory allocation.

Lists automatically manage memory allocation and resizing to accommodate new elements.

Data Flexibility - hold different data types.

Lists can hold elements of different data types or even objects of complex classes.

Dynamic Memory Management - automatic memory deallocation.

Languages with garbage collection automatically manage memory deallocation for unused elements.

Lists in action - code examples

Here we prepared a straightforward example in Java of operations performed using Lists, let’s look at the whole thing first:

public class ListExample {
    public static void main(String args[]) {
        // List of strings
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("David");
        names.add("Eve");
        
        // List of chars
        ArrayList<Character> characters = new ArrayList<>();
        characters.add('A');
        characters.add('B');
        characters.add('C');
        characters.add('D');
        characters.add('E');
        
        // List of ints
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(10);
        numbers.add(15);
        numbers.add(20);
        numbers.add(25);
        
        // List of boolean flags 
        ArrayList<Boolean> flags = new ArrayList<>();
        flags.add(true);
        flags.add(false);
        flags.add(true);
        flags.add(false);
        flags.add(true);

    }
}

And now let’s try to understand it step-by-step.

List of Strings

ArrayList<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");
names.add("David");
names.add("Eve");

An ArrayList of String type called names is created. ArrayList<String> can dynamically resize, unlike arrays, so you don’t have to specify a fixed size. The .add() method is used to add each name to the list in sequence. This results in a list of five String elements.

List of Characters

ArrayList<Character> characters = new ArrayList<>();
characters.add('A');
characters.add('B');
characters.add('C');
characters.add('D');
characters.add('E');

This is an ArrayList of Character objects, which stores individual characters. Each .add() call inserts a character into the list.

List of Integers

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(10);
numbers.add(15);
numbers.add(20);
numbers.add(25);

This is an ArrayList of Integer objects, used to store integer values. Each integer is added to the list using the .add() method.

List of Booleans

ArrayList<Boolean> flags = new ArrayList<>();
flags.add(true);
flags.add(false);
flags.add(true);
flags.add(false);
flags.add(true);

This is an ArrayList of Boolean objects, storing true and false values. The .add() method is used to insert each boolean value.

What Lists can be used for?

There’s a wide variety of problems that can be solved with Lists, of which the most common are:

Dynamic Data Storage - grows or shrinks over time.

Lists are particularly useful when you need to store a collection of items that can grow or shrink over time. They provide a convenient way to manage elements without needing to allocate memory upfront.

Input Collection - hold values in organized manner.

When you need to collect input from users or read data from files, lists can hold the input values in an organized manner.

Iterative Processing - one by one processing.

Lists are great for storing elements you need to process one by one using loops. This is helpful for tasks like data validation, transformation, or computation.

Sorting and Searching - used to implement sorting and searching algorithms.

Lists can be used to implement sorting and searching algorithms like binary search, linear search, and various sorting techniques (bubble sort, merge sort, quicksort).

Task Lists - used for managing to-do list.

Lists are ideal for managing to-do lists, task queues, and other workflows where elements need to be added, removed, and managed in order.

Data Filters and Transformations - used to store data.

Lists can store data that needs filtering, transformations, or mapping to create new lists with modified elements.

Record Keeping - historical data.

Lists are useful for storing records, logs, and historical data for later analysis.

Implementing Queues and Stacks - restricted add and removal.

Queues (FIFO) and stacks (LIFO) can be implemented using lists, where adding and removing elements are restricted to specific ends.

Data Processing Pipelines - multiple stages for various operations.

Lists can represent stages in a data processing pipeline, where data is passed through multiple stages for various operations.

Graph Traversals - data type consisting nodes and their relations.

Lists can be used to represent collections of unsorted lists in graph data structures, making it easier to traverse graphs (data type consisting nodes and their relations/edges).

Simulation and Gaming - hold states.

Lists can hold game states, player inventories, character attributes, and other game-related data.

String Manipulation - hold and manipulate characters.

Lists can hold characters in a string and allow you to manipulate the characters or perform tasks like palindrome checking.

Input Buffering - temporarily hold input data.

Lists can temporarily hold input data before processing or validation, ensuring that data is organized and processed as needed.

Serialization and Deserialization - save and read state from files.

Lists can be serialized to save their state to a file and deserialized to recreate the list later.

Data Aggregation - used for statistical analysis.

Lists can aggregate data for statistical analysis, data visualization, and reporting.

Undo/Redo Functionality - used to revert or re-apply actions.

Lists can be used to implement undo and redo functionality in applications, allowing users to revert or re-apply actions.

Event Handling - used for callbacks.

Lists can hold event handlers or callbacks in event-driven programming.

Resource Pooling - used to manage resources.

Lists can manage resources like connections, threads, or objects for efficient reuse.

Quick summary

A list is a flexible data structure that holds a collection of elements in a specific order. Unlike arrays, lists can dynamically grow or shrink, adjusting their size as elements are added or removed.

Lists allow for easy addition, removal, and access to elements, which makes them versatile in handling varying amounts of data.

Lists are highly adaptable, capable of storing different data types or complex objects. With features like automatic resizing and memory management, lists are an ideal choice for situations requiring flexible and efficient data handling.

What is an Tree?

A tree is a hierarchical data structure in computer science that resembles a “tree” with a root node and potentially multiple levels of child nodes, forming a branching structure.

Each node in a tree can have zero or more child nodes, and each child node can, in turn, have its own children. The nodes are connected by edges, which represent the relationships between the nodes.

There’s a lot of programming languages that support Arrays: Java, Python, C++, Go, etc.

A series of key characteristics for trees:

Root Node - starting point.

The topmost node in the tree hierarchy is called the root node. It is the starting point for traversing the tree.

Node - element in a tree.

Each element in a tree is called a node. Nodes contain data and references (or pointers) to their child nodes or subtrees.

Child Node - element with relations.

A node that is directly connected to another node (its parent) is considered a child node of that parent. A node can have multiple children, but it can only have one parent.

Parent Node - relations expressed through edges.

A node that has one or more child nodes is referred to as a parent node. A parent node connects to its children through edges.

Leaf Node (Terminal Node) - element without relations.

A leaf node is a node with no children. It resides at the ends of the branches and does not have any descendants.

Internal Node - element positioned between the root and leaf nodes.

An internal node is any node that is not a leaf node. It has one or more child nodes and is not located at the ends of the tree's branches.

Edge - connection between two nodes.

An edge is a connection between two nodes in a tree. It represents the relationship between a parent node and its child node.

Path - sequence of nodes.

A path in a tree is a sequence of nodes that starts at a given node and follows edges to reach another node. Paths are used to navigate through a tree's structure.

Level - distance from the root node.

The level of a node indicates its distance from the root node. The root node is at level 0, its children are at level 1, and so on.

Depth - length of the path from the root node.

The depth of a node is the length of the path from the root node to that particular node.

Height - longest path from the root node to a leaf node.

The height of a tree is the length of the longest path from the root node to a leaf node. It represents the maximum depth of the tree.

Subtree - a node and all of its descendants.

A subtree of a node consists of the node and all of its descendants, including the descendants children.

Trees in action - code examples

Here we prepared a straightforward example in Java of operations performed using Trees, let’s look at the whole thing first:

class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  public TreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  TreeNode root;

  public BinaryTree() {
    root = null;
  }

  // Insert a new node into the tree
  public void insert(int data) {
    root = insertRec(root, data);
  }

  private TreeNode insertRec(TreeNode root, int data) {
    if (root == null) {
      root = new TreeNode(data);
      return root;
    }

    if (data < root.data) {
      root.left = insertRec(root.left, data);
    } else if (data > root.data) {
      root.right = insertRec(root.right, data);
    }

    return root;
  }

  // In-order traversal of the tree
  public void inOrderTraversal(TreeNode root) {
    if (root != null) {
      inOrderTraversal(root.left);
      System.out.print(root.data + " ");
      inOrderTraversal(root.right);
    }
  }
}

public class BinaryTreeExample {
  public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();

    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);

    System.out.println("In-order traversal:");
    tree.inOrderTraversal(tree.root);
  }
}

This example showcases creating a binary search tree (BST) by defining a TreeNode class for nodes and a BinaryTree class for insertion and traversal, and then displays the in-order traversal of the BST.

And now let’s try to understand it step-by-step.

Node Structure

class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  public TreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

This structure represents each node in the binary tree.

• int data: Stores the value of the node.
• TreeNode left: Points to the left child node.
• TreeNode right: Points to the right child node.

The constructor initializes the data with the given value and sets both left and right to null, making this node a leaf by default.

Binary Tree Structure

class BinaryTree {
  TreeNode root;

  public BinaryTree() {
    root = null;
  }

  // Insert a new node into the tree
  public void insert(int data) {
    root = insertRec(root, data);
  }

  private TreeNode insertRec(TreeNode root, int data) {
    if (root == null) {
      root = new TreeNode(data);
      return root;
    }

    if (data < root.data) {
      root.left = insertRec(root.left, data);
    } else if (data > root.data) {
      root.right = insertRec(root.right, data);
    }

    return root;
  }
  
  ...
  
}

Manages the binary tree structure.

• TreeNode root: A reference to the root of the tree, initialized to null in the constructor, meaning the tree is initially empty.
• insert(int data): This public method starts the insertion process from the root. Adds a new node with the specified data value to the correct location in the binary search tree.
• insertRec(TreeNode root, int data): This private helper method recursively finds the correct place for the new data.
  • If root is null, a new TreeNode is created and returned, making it the new node.
  • If data is less than the current node’s data, the function recursively calls itself on the left child (root.left).
  • If data is greater, it recursively calls itself on the right child (root.right).
  • This preserves the BST property, where all left descendants are less than the node and all right descendants are greater.

Tree Traversal

public void inOrderTraversal(TreeNode root) {
    if (root != null) {
        inOrderTraversal(root.left);
        System.out.print(root.data + " ");
        inOrderTraversal(root.right);
    }
}

Traverses the binary tree in in-order (left, root, right) and prints each node’s data.

For each node, it recursively visits the left child, then prints the current node data, and finally visits the right child.

The traversal prints the node values in ascending order for a binary search tree.

Printing a Tree

public class BinaryTreeExample {
  public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();

    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);

    System.out.println("In-order traversal:");
    tree.inOrderTraversal(tree.root);
  }
}

Demonstrates the functionality of the BinaryTree by creating a tree, inserting nodes, and printing them in in-order.

• Nodes with values 50, 30, 70, 20, 40, 60, and 80 are added to the tree in a way that satisfies BST properties.
• tree.inOrderTraversal(tree.root) performs an in-order traversal, printing the nodes in sorted order: 20 30 40 50 60 70 80.

What Trees can be used for?

There’s a wide variety of problems that can be solved with Trees, of which the most common are:

Hierarchical Data Representation - represent hierarchical relationships.

Trees are commonly used to represent hierarchical relationships, such as file systems, organization structures, family trees, and taxonomies.

Searching and Sorting - used to implement algorithms.

Binary search trees (BSTs - key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree) allow efficient searching, insertion, and deletion operations. They can be used to implement various search and sort algorithms.

Navigational Structures - used in navigation systems.

Trees are used in navigation systems to represent routes, maps, and hierarchies of locations.

Expression Parsing and Evaluation - used to represent mathematical expressions.

Trees can represent mathematical expressions, making them suitable for parsing, evaluation, and simplification of expressions.

Graph Representations - used to represent specific types of graphs.

Trees are a subset of graphs and can be used to represent specific types of graphs, such as rooted trees for directed acyclic graphs (DAGs) or spanning trees in graphs.

Data Compression - used in data compression algorithms.

Huffman (lossless data compression) coding, used in data compression algorithms like ZIP, uses binary trees to assign shorter codes to frequently occurring characters.

Decision Trees - used for classification and regression tasks.

Used in machine learning for classification and regression tasks, decision trees help make decisions based on a sequence of questions.

Game Trees - decision-making processes in games.

Trees can represent decision-making processes in games like chess, where each node corresponds to a game state, and branches represent possible moves.

Memory Management - manage memory allocation and deallocation.

Tree structures like heap and garbage collection trees help manage memory allocation and deallocation in programming languages.

Database Indexing - implement efficient indexing structures.

B-trees and B+ trees are used to implement efficient indexing structures in databases, speeding up data retrieval.

Parse Trees - parsing expressions.

Used in parsing expressions and statements in compilers and interpreters, helping break down complex structures into simpler components.

XML and HTML Parsing - used to represent the structures.

Trees are used to represent the structure of XML and HTML documents, enabling parsing and manipulation.

Network Routing - used to model network hierarchies and routing paths.

Trees can be used to model network hierarchies and routing paths, facilitating efficient data transmission.

Data Aggregation - used for data analysis.

Trees can aggregate data for visualization, reporting, and analysis in business intelligence applications.

Prefix Matching - used for spell checking and autocomplete.

Trie (prefix tree) structures are used in applications like spell checking and autocomplete to efficiently store and search for words.

Optimal Code Generation - used to optimize instruction sequences.

Trees can be used in code generation to optimize instruction sequences for different processor architectures.

Genealogy Tracking - used to represent family genealogy and ancestry.

Trees can represent family genealogy and ancestry, helping track relationships and generations.

Event Hierarchies - used to represent hierarchies of events.

In event-driven programming, trees can represent hierarchies of events, callbacks, and notifications.

Quick summary

A tree is a hierarchical data structure commonly used in computer science to represent relationships between elements. It starts with a root node and branches out to child nodes, each of which can have their own children, forming a tree-like structure.

Key components of a tree include:

• nodes (elements with data)
• edges (connections between nodes)
• paths (sequences of nodes). The root node is the starting point, and leaf nodes are at the ends of the branches with no children. Internal nodes, located between the root and leaves, have child nodes.

Trees are essential for efficient data retrieval, decision-making, and managing complex structures.

Conclusion

In conclusion, lists, arrays, and trees are fundamental data structures in computer science that serve as the building blocks for organizing, storing, and manipulating data efficiently.

• Arrays provide a simple and efficient way to store and access a fixed-size collection of elements in contiguous memory locations. They offer constant-time access to elements via an index but are limited by their fixed size, making them less flexible for dynamic data sets.
• Lists offer more flexibility than arrays by allowing dynamic resizing and efficient insertion or deletion of elements. They cater to scenarios where the number of elements may change over time, but they come with trade-offs in terms of access time and memory overhead.
• Trees, as hierarchical data structures, enable efficient searching, sorting, and representation of hierarchical relationships. Trees facilitate fast data retrieval, organization, and decision-making.

Each of these data structures has its strengths and is suited to different types of problems:

• Arrays excel in scenarios requiring fast, indexed access to a fixed number of elements.
• Lists are ideal when the size of the data set changes frequently or when insertion/deletion efficiency is crucial.
• Trees shine when hierarchical relationships or efficient search and sorting operations are needed.

By mastering these core data structures, developers are equipped to design efficient algorithms and systems that can handle a wide range of computational tasks, from basic data storage to complex problem-solving in fields like databases, artificial intelligence, networking, and more.

Understanding the strengths, weaknesses, and use cases of each structure is essential for making informed decisions in software development and algorithm design.

Live discussion

Want to see a live discussion on the topic? Check out our YouTube recording:

Stay tuned!

Our journey in the Data Structures and Algorithms world doesn’t end here! In the next installment, we’ll delve into the Sorting and Recursion. Stay tuned!