Mastering Data Structures: From Basics to Advanced Implementations

Data structures and algorithms are core subjects in computer science, providing the foundation for abstract data storage and processing.

Definition of Data

Data : the carrier of information, e.g., personal identity, images, music.

Data object : a collection of data elements with the same nature.

Data element : the basic unit of data.

Data item : the indivisible smallest unit within a data element.

Data Types

Data types consist of atomic types (e.g., int, char, float), structured types (list, map, set), and abstract data types (ADT) which define a data model and its operations.

Three Elements of Data Structures

Data structures have three elements: logical structure, physical (storage) structure, and data operations.

Logical Structure

Logical structure describes the logical relationships among data elements, independent of computer storage. It includes linear structures (linear list, stack, queue) and non‑linear structures (set, tree, graph).

Linear Structure

Examples include a queue of people waiting for tickets.

Set

A set contains elements without additional relationships, e.g., the set of all integers.

Tree Structure

A one‑to‑many relationship, such as animal classifications.

Graph Structure

Many‑to‑many relationships, like a city transportation network.

Storage Structure

Storage structure is the physical representation of a data structure in memory. It includes sequential storage, linked storage, indexed storage, and hash storage.

Sequential Storage

Elements that are logically adjacent are stored in adjacent memory locations, enabling random access.

Linked Storage

Logical neighbors may be stored non‑contiguously; each element stores the address of the next element.

Indexed Storage

An index table maps keys to the addresses of data elements.

Hash Storage

Addresses are computed directly from keys using a hash function.

Data Operations

Operations are defined on the logical structure and implemented on the storage structure.

Linear List

Linear list is a finite sequence of n data elements. It can be implemented with arrays or linked lists.

Array Implementation

int[] oldArray = new int[10];
int[] newArray = new int[20];
for (int i = 0; i < oldArray.length; i++) {
    newArray[i] = oldArray[i];
}
oldArray = newArray;

Insertion at a specific index:

public void add(int index, int e) {
    if (index > size || index < 0) {
        System.out.println("Invalid position");
        return;
    }
    if (size >= oldArray.length) {
        // expand array (e.g., create a larger array and copy)
    }
    for (int i = size - 1; i >= index; i--) {
        oldArray[i + 1] = oldArray[i];
    }
    oldArray[index] = e;
    size++;
}

Linked List

class Node<E> {
    E item;
    Node<E> next;
    Node(E element) {
        this.item = element;
        this.next = null;
    }
}

Node<E> head = null;
Node<E> tail = null;
head = new Node<>("node1");
tail = head;
// Append a new node
tail.next = new Node<>("node2");
tail = tail.next;

Stack

Stack follows LIFO (last‑in‑first‑out). In Java, java.util.Stack extends Vector; a LinkedList can also be used as a stack.

Queue

Queue follows FIFO (first‑in‑first‑out). It can be implemented with LinkedList.

public class MyQueue<E> {
    private LinkedList<E> list = new LinkedList<>();
    public void enqueue(E e) { list.addLast(e); }
    public E dequeue() { return list.removeFirst(); }
}

Tree and Binary Tree

Tree is a hierarchical structure with a root, parent, and children. Binary tree limits each node to at most two children (left and right).

class TreeNode<E> {
    E element;
    TreeNode<E> left;
    TreeNode<E> right;
    TreeNode(E e) { element = e; }
}

Binary search tree (BST) maintains the ordering property: values in the left subtree are smaller than the node, values in the right subtree are larger.

public class MyBinSearchTree<E extends Comparable<E>> {
    private TreeNode<E> root;
    public boolean search(E e) { /* ... */ }
    public boolean insert(E e) { /* ... */ }
    public boolean delete(E e) { /* ... */ }
}

Balanced Binary Trees

AVL tree is a self‑balancing BST where the height difference between left and right subtrees of any node is at most 1.

Red‑Black Tree

Red‑black tree is a balanced BST that relaxes strict balance for simpler rotations while guaranteeing O(log n) operations.

Summary

The three essential aspects of data structures are logical structure, storage structure, and operations. Core types include linear structures (list, stack, queue) and non‑linear structures (set, tree, graph, heap). Storage structures include sequential, linked, indexed, and hash representations, each suited to different algorithmic needs.