[Java] Fundamental Data Structures: Part 1

📋 Here are the notes summarizing what I learned from the course!

Fundamental Data Structures - Part 1

Arrays

Definition

Arrays are collections of items stored at contiguous memory locations and accessible via indices.

Operations

• Add: To add a new element at a specific index, existing elements must be shifted to make space.
• Remove: Removing an element requires elements after it to be shifted to fill the gap.

Examples in Java

int[] array = new int[5];  // Declaring an array of integers with 5 elements
array[0] = 10;             // Assigning a value to the first element
System.out.println(array[0]); // Accessing the first element

Singly Linked Lists

Definition

A singly linked list consists of nodes that are linked together by a single link or reference.

Operations

• Insert at Head: A new node is added at the beginning, pointing to the previous head.
• Insert at Tail: A new node is added at the end and the last node’s link is updated to this new node.
• Remove at Head: The head is updated to the next node.
• Remove at Tail: More complex because it requires traversal from the head to the second-last node.

Structure

Each node in a singly linked list contains data and a reference to the next node.

Code Example for Singly Linked Lists

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;
    
    void addAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
    
    void removeAtHead() {
        if (head != null) {
            head = head.next;
        }
    }
}

Doubly Linked Lists

Definition

Doubly linked lists allow traversal in both directions (forward and backward) because each node points to both its predecessor and successor.

Operations

• Insertion: Nodes can be inserted in between two nodes efficiently.
• Deletion: Nodes can also be removed efficiently because each node knows its predecessor.

Structure

Each node contains a reference to the previous node, the data, and the next node.

Code Example for Doubly Linked Lists

class DoublyNode {
    int data;
    DoublyNode prev;
    DoublyNode next;
    
    DoublyNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    DoublyNode head;
    
    void add(int data) {
        DoublyNode newNode = new DoublyNode(data);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
    }
    
    void remove(DoublyNode node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
    }
}

---

Back to Top

See other articles in Category Java