☑️Data Structures

📚 Array 📚

An array is a data structure that allows you to store a fixed-size sequence of elements of the same type. Benefits include:

  1. Storage and Organization: Arrays provide a contiguous block of memory to store elements in a systematic manner. Each element in the array occupies a specific position, called an index, which starts from 0 and increments by 1 for each subsequent element.

  2. Random Access: Elements in an array can be accessed directly using their index. This allows for efficient retrieval of elements, as the position of each element is known based on its index.

  3. Homogeneous Elements: Arrays hold elements of the same type. This ensures consistency in data representation, making it easier to perform operations on the elements.

  4. Iterating Over Elements: Arrays can be traversed using loops, such as the for loop, allowing you to perform operations on each element sequentially.

public class ArrayExample {
    public static void main(String[] args) {
        // Declare and initialize an array of integers
        int[] numbers = {5, 10, 15, 20, 25};
        
        // Access elements in the array using their index
        int firstNumber = numbers[0]; // Access the first element (index 0)
        int thirdNumber = numbers[2]; // Access the third element (index 2)
        
        // Modify elements in the array
        numbers[1] = 12; // Change the second element (index 1) to 12
        
        // Get the length of the array
        int length = numbers.length; // Returns 5
        
        // Iterate over the elements in the array
        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i]);
        }
    }
}

Arrays allow fast random access but adding/removing elements is slow. They are used when you need indexed access to elements.

📒 Linked List 📒

A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic memory allocation and flexibility in size. Linked lists have the following properties:

  • Elements are stored non-contiguously in memory

  • Elements can only be accessed sequentially starting from the head

  • Adding/removing elements is fast since pointers can be updated

class Node {
  int data;
  Node next;
}

Node head = new Node(1);
head.next = new Node(2); 
head.next.next = new Node(3);

Linked lists allow efficient insertion and removal but only sequential access. They are used when you need fast insertion/deletion but don't require random access.

Key Characteristics

  1. Node: Each node in a linked list contains two parts:

    • Value: The actual data being stored in the node.

    • Next reference: A reference to the next node in the linked list.

  2. Head: The head refers to the first node in the linked list. It acts as the starting point for traversing the list.

  3. Traversal: Linked lists can be traversed by starting at the head and following the next references until reaching the end of the list (i.e., a node with a null reference).

  4. Insertion: Nodes can be inserted into a linked list by creating a new node, adjusting the references, and updating the links between nodes. Common insertion points are at the beginning, end, or middle of the list.

  5. Deletion: Nodes can be removed from a linked list by adjusting references to bypass the node to be deleted, allowing the garbage collector to reclaim the memory.

  6. Search: Linked lists can be searched by traversing the list and comparing the values of each node until finding the desired value or reaching the end of the list.

  7. Advantages: Linked lists offer dynamic memory allocation, efficient insertion and deletion at the beginning (with constant time complexity), and flexibility in size.

  8. Disadvantages: Linked lists require additional memory to store the references, and accessing elements by index is less efficient compared to arrays.

🗃️ Stack 🗃️

A stack is a LIFO (last-in first-out) data structure. Stacks have the following properties:

  • Elements are added/removed from the top of the stack

  • push() adds to the top, pop() removes from the top

  • Access is restricted to only the top element

Stack stack = new Stack();
stack.push(1); // 1 is at the top
stack.push(2); // 2 is now at the top
stack.pop(); // 2 is removed

Stacks provide LIFO ordering and fast operations on the top. They are useful for undo/redo functionality, depth-first search, etc.

📦 Queue 📦

A queue is a FIFO (first-in first-out) data structure. Queues have the following properties:

  • Elements are added to the back and removed from the front

  • enqueue() adds to the back, dequeue() removes from the front

  • Oldest element is always at the front

Queue queue = new Queue();
queue.enqueue(1); // 1 is at the front 
queue.enqueue(2); // 1, 2 with 1 in front
queue.dequeue(); // 1 is removed

Queues provide FIFO ordering and fast addition/removal from both ends. They are useful for breadth-first search, scheduling, etc.

🌳 Binary Tree 🌳

A binary tree is a hierarchical tree structure where each node has up to two child nodes. Binary trees have the following properties:

  • Each node has a left and right child pointer

  • The left subtree contains nodes with keys lesser than the parent node

  • The right subtree contains nodes with keys greater than the parent node

class Node {
  int key; 
  Node left, right;

  Node(int key) {
    this.key = key;
    left = right = null;
  }
}

Node root = new Node(5); 
root.left = new Node(3);
root.right = new Node(8);

Binary trees allow fast search, insertion and deletion operations with time complexity O(log n). They are extensively used in databases, compilers, file systems.

🗄️ Hash Table 🗄️

A hash table stores data using a hash function to compute an index into an array. Hash tables have the following properties:

  • Data is mapped to indices using a hash function

  • collisions are handled by chaining or open addressing

  • Lookup, insertion, deletion are fast with O(1) on average

HashMap<String, Integer> map = new HashMap();
map.put("Alice", 25); 
map.put("Bob", 30);
map.get("Alice"); // returns 25

Hash tables provide fast lookup by computing the index directly from the data. They are used when fast lookups are required, such as dictionaries, caches.

📊 Heap 📊

A heap is a tree-based structure that satisfies the heap property - the parent is greater than or equal to (max heap) or less than or equal to (min heap) the children. Heaps support:

  • peek() - access max/min without removal

  • poll() - remove and return max/min

  • add() - add element in proper position

Heaps are efficient implementations of priority queues. They provide fast access to max/min element and fast insertion and removal in O(log n). Useful for scheduling algorithms, graph algorithms.

📎 Graph 📎

A graph represents relationships by connecting nodes via edges. Graphs contain:

  • Nodes - Entities like people, locations

  • Edges - Relationships between nodes

  • Can be directed or undirected

Vertices: A, B, C, D
Edges: (A, B), (B, C), (B, D)

Graphs model real-world relationships like social networks, roads, flight paths. Used extensively in navigation, social network analysis, bioinformatics.

PreviousBig ONextArray

Last updated