[Java] Fundamental Data Structures: Part 2

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

Fundamental Data Structures – Part 2

Circularly Linked Lists

Circularly linked lists are a variant of singly linked lists where the last node points back to the head instead of null, creating a circular structure.

Examples and Applications

• Round-Robin Scheduling: This scheduling is used in operating systems for process management using a circularly linked list to cycle through tasks.
• Game Development: In multiplayer games, turns can cycle among players in a loop similar to a circularly linked list.

Design and Implementation

• Circularly Linked List Basic Operations:
  • Insertion at the Head: Create a new node, set it as the new head, and adjust the last node to point to this new head.
  • Rotation: Rotate the head to the tail in one operation, which is crucial for efficient round-robin scheduling.

class CircularlyLinkedList<E> {
    private Node<E> tail = null;
    private int size = 0;

    public void rotate() {
        if (tail != null) {
            tail = tail.next; // the old head becomes the new tail
        }
    }

    public void addFirst(E e) {
        if (size == 0) {
            tail = new Node<>(e, null);
            tail.next = tail; // link to itself
        } else {
            Node<E> newest = new Node<>(e, tail.next);
            tail.next = newest;
        }
        size++;
    }

    public void addLast(E e) {
        addFirst(e);
        tail = tail.next; // rotate new element to the back
    }

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E e, Node<E> n) {
            element = e;
            next = n;
        }
    }
}

Equivalence Testing

Understanding how to test equivalence between data structures like arrays and linked lists.

Equivalence in Arrays

• Arrays must be compared element by element.
• Arrays.equals() for one-dimensional arrays.
• Arrays.deepEquals() for multidimensional arrays.

import java.util.Arrays;

public class ArrayEquivalence {
    public static void main(String[] args) {
        int[] array1 = {1, 2, 3};
        int[] array2 = {1, 2, 3};
        System.out.println(Arrays.equals(array1, array2)); // true

        int[][] deepArray1 = {{1, 2, 3}, {4, 5, 6}};
        int[][] deepArray2 = {{1, 2, 3}, {4, 5, 6}};
        System.out.println(Arrays.deepEquals(deepArray1, deepArray2)); // true
    }
}

Equivalence in Linked Lists

• Custom method to compare linked lists node by node.

class SinglyLinkedList {
    Node head;

    boolean isEqual(SinglyLinkedList other) {
        Node currentThis = this.head;
        Node currentOther = other.head;
        while (currentThis != null && currentOther != null) {
            if (!currentThis.element.equals(currentOther.element)) {
                return false;
            }
            currentThis = currentThis.next;
            currentOther = currentOther.next;
        }
        return currentThis == null && currentOther == null;
    }

    private class Node {
        Object element;
        Node next;

        Node(Object e) {
            element = e;
            next = null;
        }
    }
}

Cloning Data Structures

Cloning is creating a copy of a data structure.

Cloning Arrays

• Shallow vs. deep cloning considerations.
• Use clone() for shallow copies, custom methods for deep copies.

Cloning Linked Lists

• Implementing cloning in a linked list with deep copy of each node.

class SinglyLinkedList<E> implements Cloneable {
    private Node<E> head;

    public SinglyLinkedList<E> clone() throws CloneNotSupportedException {
        SinglyLinkedList<E> other = (SinglyLinkedList<E>) super.clone();
        if (size > 0) {
            other.head = new Node<>(head.element, null);
            Node<E> walk = head.next;
            Node<E> otherTail = other.head;
            while (walk != null) {
                Node<E> newest = new Node<>(walk.element, null);
                otherTail.next = newest;
                otherTail = newest;
                walk = walk.next;
            }
        }
        return other;
    }

    private static class Node<E> {
        private E element;
        private Node<E> next;

        public Node(E e, Node<E> n) {
            element = e;


            next = n;
        }
    }
}

---

Back to Top

See other articles in Category Java