datastructures1SinglyLinkedList

1package pkg3datastructures;2 3/*4 * datastructures1SinglyLinkedList.java5 * ---------------------6 * A singly linked list with add, insert, delete, reverse, and cycle detection.7 *8 * COMPLEXITY:9 *  - addFirst: O(1), addLast: O(n) (O(1) if we track tail), get(i): O(n)10 *  - delete(value): O(n), reverse: O(n)11 *12 * WHEN TO USE: frequent insert/delete at the head; unknown size; no random access.13 */14public class datastructures1SinglyLinkedList {15 16    static class Node {17        int val; Node next;18        Node(int val) { this.val = val; }19    }20 21    private Node head;22    private int size;23 24    void addFirst(int v) { Node n = new Node(v); n.next = head; head = n; size++; }25 26    void addLast(int v) {27        Node n = new Node(v);28        if (head == null) { head = n; }29        else { Node c = head; while (c.next != null) c = c.next; c.next = n; }30        size++;31    }32 33    boolean delete(int v) {34        if (head == null) return false;35        if (head.val == v) { head = head.next; size--; return true; }36        Node c = head;37        while (c.next != null && c.next.val != v) c = c.next;38        if (c.next == null) return false;39        c.next = c.next.next; size--; return true;40    }41 42    // Reverse the list iteratively (classic interview question)43    void reverse() {44        Node prev = null, curr = head;45        while (curr != null) {46            Node next = curr.next;47            curr.next = prev;48            prev = curr;49            curr = next;50        }51        head = prev;52    }53 54    // Floyd's cycle detection (tortoise & hare)55    boolean hasCycle() {56        Node slow = head, fast = head;57        while (fast != null && fast.next != null) {58            slow = slow.next;59            fast = fast.next.next;60            if (slow == fast) return true;61        }62        return false;63    }64 65    int size() { return size; }66 67    @Override public String toString() {68        StringBuilder sb = new StringBuilder("[");69        for (Node c = head; c != null; c = c.next) sb.append(c.val).append(c.next != null ? " -> " : "");70        return sb.append("]").toString();71    }72 73    public static void main(String[] args) {74        datastructures1SinglyLinkedList list = new datastructures1SinglyLinkedList();75        list.addLast(1); list.addLast(2); list.addLast(3);76        list.addFirst(0);77        System.out.println("list: " + list + " size=" + list.size());78 79        list.delete(2);80        System.out.println("after delete(2): " + list);81 82        list.reverse();83        System.out.println("reversed: " + list);84 85        System.out.println("hasCycle: " + list.hasCycle());86        // Build a cycle manually to test detection87        list.head.next.next.next = list.head;   // create loop88        System.out.println("hasCycle after creating loop: " + list.hasCycle());89    }90}