Data Structures Explained_ Arrays, Linked Lists, and More

Data Structures Explained: Arrays, Linked Lists, and More

Data structures are fundamental building blocks in computer science, providing efficient ways to store, manage, and retrieve data. Choosing the right data structure can greatly impact the performance and scalability of software applications. This article explores key data structures, including arrays, linked lists, stacks, queues, hash tables, trees, and graphs, explaining their use cases and differences.

1. Arrays

An array is a linear data structure that stores elements in contiguous memory locations. Each element is indexed, allowing fast access via its index.

Characteristics of Arrays:

Fixed size (in static arrays)
Fast access time (O(1) for retrieving an element)
Insertion and deletion can be expensive (O(n) in worst cases)

Example of an Array in C++:

cpp
int arr[] = {1, 2, 3, 4, 5};
cout << arr[2];  // Output: 3

Use Cases of Arrays:

Storing data that does not change often
Implementing lookup tables and matrices
Processing large datasets efficiently

2. Linked Lists

A linked list is a dynamic data structure consisting of nodes. Each node contains data and a reference (or pointer) to the next node in the sequence.

Types of Linked Lists:

Singly Linked List – Each node points to the next node.
Doubly Linked List – Nodes have references to both the previous and next nodes.
Circular Linked List – The last node connects back to the first node.

Example of a Singly Linked List in Python:

python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(data)

Use Cases of Linked Lists:

Dynamic memory allocation
Efficient insertions/deletions in large datasets
Implementing stacks, queues, and graphs

3. Stacks

A stack is a Last In, First Out (LIFO) data structure where elements are added and removed from the top.

Characteristics of Stacks:

Push operation (insert element)
Pop operation (remove element)
Peek operation (view top element)

Example of a Stack in Java:

java
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        System.out.println(stack.pop()); // Output: 20
    }
}

Use Cases of Stacks:

Undo/Redo functionality
Expression evaluation (postfix, prefix)
Function call stack in recursion

4. Queues

A queue is a First In, First Out (FIFO) data structure where elements are added at the rear and removed from the front.

Types of Queues:

Simple Queue – FIFO structure
Circular Queue – Rear connects to front when full
Priority Queue – Elements are dequeued based on priority
Deque (Double-ended queue) – Insert/remove from both ends

Example of a Queue in Python:

python
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft())  # Output: 1

Use Cases of Queues:

Process scheduling in operating systems
Print spooling
Network request handling

5. Hash Tables

A hash table (or hash map) is a data structure that stores key-value pairs and uses a hash function to compute the index of the key.

Characteristics of Hash Tables:

Fast lookups in O(1) average time
Collision handling through chaining or open addressing

Example of a Hash Table in JavaScript:

javascript
let hashMap = new Map();
hashMap.set("name", "Alice");
console.log(hashMap.get("name"));  // Output: Alice

Use Cases of Hash Tables:

Database indexing
Caching systems
Implementing dictionaries

6. Trees

A tree is a hierarchical data structure where nodes are connected through edges.

Common Types of Trees:

Binary Tree – Each node has at most two children.
Binary Search Tree (BST) – Left subtree has smaller values, right subtree has larger values.
AVL Tree – Self-balancing BST.
Heap – Complete binary tree used for priority-based operations.
Trie – Used for efficient string searching.

Example of a Binary Tree in Python:

python
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Use Cases of Trees:

Hierarchical data representation
Search operations in log(n) time complexity
AI and game development (decision trees)

7. Graphs

A graph is a collection of nodes (vertices) connected by edges.

Types of Graphs:

Directed Graph (Digraph) – Edges have direction.
Undirected Graph – Edges do not have direction.
Weighted Graph – Edges have weights.

Example of a Graph using an Adjacency List in Python:

python
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Use Cases of Graphs:

Social networks
Routing algorithms (Dijkstra’s, A*)
Web page ranking (Google’s PageRank)

Conclusion

Understanding data structures is crucial for optimizing performance and solving complex computational problems efficiently. Arrays and linked lists provide foundational storage, while stacks and queues manage ordered data. Hash tables allow rapid lookups, trees provide hierarchical organization, and graphs enable advanced relationships between elements. Mastering these structures will improve your ability to design efficient algorithms and applications.

Share This Page:

Data Structures Explained_ Arrays, Linked Lists, and More