Understanding Data Structures
In computer science, a fundamental principle states that programs consist of data structures and algorithms. While these two components are interdependent, this article focuses specifically on exploring common data structures.
Data structures refer to the methods of organizing, managing, and storing data in a computer. Although theoretically, all data could be stored haphazardly, computers prioritize efficiency. By understanding data structures and selecting appropriate ones for specific scenarios, we can represent data relationships in storage and utilize compatible algorithms for computation, significantly improving program performance.
The four primary categories of data structures include:
- Set Structure: Elements share a collective relationship without additional constraints
- Linear Structure: Each element has exactly one predecessor and one successor
- Tree Structure: Each element may have multiple successors but only one predecessor
- Graph Structure: Elements can have complex many-to-many relationships
Logical vs. Physical Structure
The logical relationships between data elements constitute the logical structure, representing a mathematical description of the object. The physical structure (or storage structure) represents how this logical structure is implemented in computer memory.
Two primary methods exist for representing relationships in memory: sequential mapping and non-sequential mapping, leading to two storage structures: sequential storage and linked storage.
Bit Manipulation and Applications
The bit is the smallest unit of information in computing. Computers fundamentally operate on binary values, with all data ultimately represented as sequences of 0s and 1s.
Common bit operations include:
~: Bitwise NOT (inverts all bits)&: Bitwise AND|: Bitwise OR^: Bitwise XOR<<: Left shift (signed)>>: Right shift (signed)>>>: Right shift (unsigned)
Bloom Filter Implementation
A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It consists of a bit array and multiple hash functions.
Key characteristics:
- False positives are possible, but false negatives are not
- Deletion is problematic as it affects other elements
- Excellent for membership testing with minimal storage
class BloomFilter {
private BitSet bitArray;
private int size;
private MessageDigest[] hashFunctions;
public BloomFilter(int size, int hashCount) {
this.size = size;
this.bitArray = new BitSet(size);
this.hashFunctions = new MessageDigest[hashCount];
for (int i = 0; i < hashCount; i++) {
hashFunctions[i] = createHashFunction(i);
}
}
public void add(String element) {
for (MessageDigest md : hashFunctions) {
int hash = Math.abs(md.digest(element.getBytes())[0]) % size;
bitArray.set(hash);
}
}
public boolean contains(String element) {
for (MessageDigest md : hashFunctions) {
int hash = Math.abs(md.digest(element.getBytes())[0]) % size;
if (!bitArray.get(hash)) {
return false;
}
}
return true;
}
}
Array Data Structure
Arrays represent the most fundamental linear data structure, characterized by contiguous memory allocation and constant-time access via indexing.
Operations and time complexities:
- Access: O(1) - direct indexing
- Search: O(n) - linear scan required
- Insertion: O(n) - requires shifting elements
- Deletion: O(n) - requires shifting elements
class DynamicArray<T> {
private Object[] elements;
private int size;
private int capacity;
public DynamicArray(int initialCapacity) {
this.capacity = initialCapacity;
this.elements = new Object[capacity];
this.size = 0;
}
public void add(T item) {
if (size == capacity) {
resize();
}
elements[size++] = item;
}
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (T) elements[index];
}
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size--;
}
private void resize() {
capacity *= 2;
elements = Arrays.copyOf(elements, capacity);
}
}
Linked Lists
Unlike arrays, linked lists store elements non-contiguously, with each node containing a reference (pointer) to the next node. This enables efficient insertion and deletion operations at the cost of sequential access.
Common variations include:
- Singly Linked: Each node points to the next
- Doubly Linked: Each node points to both previous and next
- Circular: Last node points back to first
class SinglyLinkedList<T> {
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
}
}
private Node head;
private int size;
public void addFirst(T data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
size++;
}
public void addLast(T data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
size++;
}
public boolean remove(T data) {
if (head == null) return false;
if (head.data.equals(data)) {
head = head.next;
size--;
return true;
}
Node current = head;
while (current.next != null) {
if (current.next.data.equals(data)) {
current.next = current.next.next;
size--;
return true;
}
current = current.next;
}
return false;
}
}
Skip Lists
Skip lists are probabilistic data structures that allow O(log n) search complexity while maintaining a simple implementation. They use multiple layers of linked lists with increasing spacing between elements.
The structure resembles a multi-level index, where higher levels contain fewer elements but skip larger ranges, enabling logarithmic-time search operations.
Stack Data Structure
Stacks follow the Last-In-First-Out (LIFO) principle, where elements are added and removed from the same end (the "top").
class ArrayStack<T> {
private Object[] elements;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
this.top = -1;
}
public void push(T element) {
if (top == capacity - 1) {
resize();
}
elements[++top] = element;
}
@SuppressWarnings("unchecked")
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return (T) elements[top--];
}
@SuppressWarnings("unchecked")
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return (T) elements[top];
}
public boolean isEmpty() {
return top == -1;
}
private void resize() {
capacity *= 2;
elements = Arrays.copyOf(elements, capacity);
}
}
Queue Data Structure
Queues implement the First-In-First-Out (FIFO) principle, with elements added at the rear and removed from the front.
class LinkedListQueue<T> {
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
}
}
private Node front;
private Node rear;
private int size;
public void enqueue(T element) {
Node newNode = new Node(element);
if (rear == null) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
size++;
}
public T dequeue() {
if (front == null) {
throw new NoSuchElementException();
}
T data = front.data;
front = front.next;
if (front == null) {
rear = null;
}
size--;
return data;
}
public boolean isEmpty() {
return front == null;
}
}
Hash Tables
Hash tables map keys to array indices using hash functions, enabling average-case O(1) access time. Collisions occur when different keys map to the same index.
Common collision resolution strategies:
- Chaining: Store colliding elements in linked lists
- Open Addressing: Find alternative positions using probing
- Robin Hood Hashing: Minimize variance in probe sequence lengths
class HashMap<K, V> {
private static class Entry<K, V> {
K key;
V value;
Entry<K, V> next;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
private Entry<K, V>[] buckets;
private int size;
private static final int DEFAULT_CAPACITY = 16;
@SuppressWarnings("unchecked")
public HashMap() {
this.buckets = new Entry[DEFAULT_CAPACITY];
}
public void put(K key, V value) {
int index = getIndex(key);
Entry<K, V> entry = buckets[index];
while (entry != null) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
entry = entry.next;
}
Entry<K, V> newEntry = new Entry<>(key, value);
newEntry.next = buckets[index];
buckets[index] = newEntry;
size++;
}
public V get(K key) {
int index = getIndex(key);
Entry<K, V> entry = buckets[index];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
private int getIndex(K key) {
return Math.abs(key.hashCode() % buckets.length);
}
}
Tree Structures
Trees are hierarchical data sturctures with a root node and child nodes. Binary trees, where each node has at most two children, are particularly important.
Binary Search Trees (BST)
BSTs maintain ordering: left subtree cnotains smaller values, right subtree contains larger values. This enables O(log n) search, insertion, and deletion when balanced.
class BinarySearchTree {
private class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
}
}
private Node root;
public void insert(int value) {
root = insertRecursive(root, value);
}
private Node insertRecursive(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value < node.value) {
node.left = insertRecursive(node.left, value);
} else if (value > node.value) {
node.right = insertRecursive(node.right, value);
}
return node;
}
public boolean search(int value) {
return searchRecursive(root, value);
}
private boolean searchRecursive(Node node, int value) {
if (node == null) {
return false;
}
if (value == node.value) {
return true;
}
return value < node.value
? searchRecursive(node.left, value)
: searchRecursive(node.right, value);
}
}
Balanced Trees
To maintain O(log n) operations, self-balancing trees like AVL trees and Red-Black trees automatically adjust their structure during insertions and deletions.
B-Trees and B+ Trees
B-Trees are optimized for disk-based storage systems with large branching factors, reducing I/O operations. B+ Trees extend B-Trees by storing all values in leaf nodes and linking them for efficient range queries.
Heap Data Structure
Heaps are specialized tree-based structures that satisfy the heap property. In a min-heap, parent nodes are less than or equal to their children; in a max-heap, they're greater than or equal.
class MinHeap {
private int[] heap;
private int size;
public MinHeap(int capacity) {
this.heap = new int[capacity];
this.size = 0;
}
public void insert(int value) {
if (size == heap.length) {
throw new IllegalStateException("Heap is full");
}
heap[size] = value;
bubbleUp(size);
size++;
}
public int extractMin() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
int min = heap[0];
heap[0] = heap[--size];
bubbleDown(0);
return min;
}
private void bubbleUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap[parent] <= heap[index]) break;
swap(parent, index);
index = parent;
}
}
private void bubbleDown(int index) {
while (true) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int smallest = index;
if (leftChild < size && heap[leftChild] < heap[smallest]) {
smallest = leftChild;
}
if (rightChild < size && heap[rightChild] < heap[smallest]) {
smallest = rightChild;
}
if (smallest == index) break;
swap(index, smallest);
index = smallest;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
Graph Data Structures
Graphs consist of vertices connected by edges, representing relationships between objects. They can be directed or undirected, weighted or unweighted.
Graph Representations
Two common methods for representing graphs:
- Adjacency Matrix: 2D array where matrix[i][j] indicates edge presence
- Adjacency List: Array of lists containing adjacent vertices
class Graph {
private List<Integer>[] adjacencyList;
private int vertices;
@SuppressWarnings("unchecked")
public Graph(int vertices) {
this.vertices = vertices;
this.adjacencyList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = new ArrayList<>();
}
}
public void addEdge(int source, int destination) {
adjacencyList[source].add(destination);
adjacencyList[destination].add(source); // For undirected graph
}
public void bfs(int startVertex) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int neighbor : adjacencyList[vertex]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
Conclusion
Understanding these fundamental data structures enables developers to select appropriate solutions for specific problems, optimizing both time and space complexity. The choice of data structure significantly impacts algorithm efficiency and overall program performance.