6 Common Data Structures in Programming

Data structures are the building blocks of efficient software in programming. Understanding when and why to use each one can elevate your problem-solving skills. Here, we explore 6 essential data structures, delving into their characteristics, use cases, and implementation in TypeScript. Each section includes diagrams and code examples for clarity.

1. Array

An array is a contiguous block of memory where elements of the same type are stored.

Characteristics:

• Fast access via index.

• Fixed-size (in most languages).

• Can hold duplicate values.

When to Use: Arrays are used to store ordered collections of elements where quick random access is required.

Code Example

const fruits: string[] = ['apple', 'banana', 'cherry'];
console.log(fruits[1]); // Outputs: banana

Visualization

2. Linked List

A linked list is a collection of nodes where each node contains data and a reference to the next node.

Characteristics:

• Dynamic size.
• Inefficient random access.
• Efficient insertions/deletions.

When to Use: Use linked lists for applications requiring frequent insertions and deletions, such as undo functionality in editors.

Code Example

class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;

  add(value: T) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

const list = new LinkedList<number>();
list.add(10);
list.add(20);
console.log(JSON.stringify(list)); 
// Outputs: {"head":{"value":10,"next":{"value":20,"next":null}}}

Visualization

3. Stack

A stack is a LIFO (Last In, First Out) data structure.

Characteristics:

• Push and pop operations.
• Useful for backtracking, such as in DFS or expression evaluation.

When to Use: Use stacks for managing function calls, syntax parsing, or undo operations.

Code Example

class Stack<T> {
  private items: T[] = [];
  push(item: T): void {
    this.items.push(item);
  }
  pop(): T | undefined {
    return this.items.pop();
  }
  display(): void {
    console.log(this.items.reverse());
  }
}

const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.display(); // Outputs: [3, 2, 1]
console.log(stack.pop()); // Returns 3

Visualization

4. Queue

A queue is a FIFO (First In, First Out) data structure.

Characteristics:

• Enqueue and dequeue operations.
• Used in scheduling and buffering.

When to Use: Use queues for managing tasks, such as job scheduling or breadth-first search.

Code Example

class Queue<T> {
  private items: T[] = [];
  enqueue(item: T): void {
    this.items.push(item);
  }
  dequeue(): T | undefined {
    return this.items.shift();
  }
  display(): void {
    console.log(this.items);
  }
}

const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.display(); // Outputs: [1, 2, 3]
console.log(queue.dequeue()); // Returns 1

Visualization

5. Hash Table

A hash table is a key-value pair data structure optimized for quick lookups.

Characteristics:

• Average O(1) time complexity for lookup and insertion.
• Handles collisions using chaining or open addressing.

When to Use: Use hash tables for dictionaries, caching, and sets.

Code Example

class HashTable<K, V> {
  private buckets: [K, V][][] = [];

  private hash(key: K): number {
    return JSON.stringify(key).length % 10;
  }

  set(key: K, value: V): void {
    const index = this.hash(key);
    this.buckets[index] = this.buckets[index] || [];
    this.buckets[index].push([key, value]);
  }

  get(key: K): V | undefined {
    const index = this.hash(key);
    const bucket = this.buckets[index] || [];
    for (const [k, v] of bucket) {
      if (k === key) return v;
    }
  }
}

const hashTable = new HashTable<string, number>();
hashTable.set("name", "Alice");
hashTable.set("age", 30);
console.log(hashTable.get("age")); // Outputs: 30

Visualization

6. Binary Tree

A binary tree is a hierarchical structure where each node has up to two children.

Characteristics:

• Traversals include inorder, preorder, and postorder.
• Basis for binary search trees (BST).

When to Use: Use binary trees for hierarchical data like file systems.

Code Example

class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
console.log(JSON.stringify(root));
// Outputs: {"value":1,"left":{"value":2,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}

Visualization

Conclusion

Understanding data structures is crucial for writing efficient and scalable code. Arrays, linked lists, stacks, queues, hash tables, and binary trees each serve specific purposes, from managing order to organizing data hierarchically.

Mastering these basics empowers you to solve diverse challenges, whether in coding interviews or real-world projects. Practice regularly, and you'll quickly see the impact on your problem-solving skills.

References for Further Learning

Books:

• "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
• "Data Structures and Algorithm Analysis in Java" by Mark A. Weiss.
• "The Algorithm Design Manual" by Steven Skiena.

Interactive Platforms:

• LeetCode - Solve coding problems using these structures.
• GeeksforGeeks - Comprehensive articles on data structures.
• HackerRank - Learn and practice data structures hands-on.

Courses:

• CS50’s Introduction to Computer Science - A great beginner-friendly resource.
• Data Structures and Algorithms Specialization on Coursera - In-depth, structured learning.

Follow me on X for more!