SinglyLinkedList Algorithm in Java

A Singly Linked List, in its simplest form, is a collection of nodes that together form a linear ordering.
    A node has two parts: Element and Pointer (or Data and Reference).
    Each element in the node represents DATA_VALUE of that Node. The Pointer of each node has reference to another Node 
    like STEPS of a LADDER. So NULL Pointer means a TAIL Node, that means End of Linked list. Moving from one node to 
    another by following a next reference is known as Link hopping or Pointer hopping. The first and last node of a linked 
    list usually are called the head and tail of the list. Also remember DATA_VALUE can be anything like a "Person" Object 
    having many attributes or any Wrapper class object.

LinkedList Program:

-----------------------------------------------------------
package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class Node {
    public int data;
    public Node next;
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public String toString(){
        return data+"";
    }
}
-----------------------------------------------------------
package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class SinglyLinkedList {
    public Node start;  //means header node
    public int size;
    
    public SinglyLinkedList(){
        start=null;   //start means header node
        size=0;
    }
    public void addAtFirst(int number){
        Node temp=new Node();
        temp.setData(number);  //Make temp new node
        if(size==0){           //List is empty, create head node
            temp.setNext(null);  //Make first node, so reference is null.
            start=temp;          //make temp as header node
        }else{
            temp.setNext(start);    //new node is complete now with pointing to header       
            start=temp;             //make new node as header 
        }
        size++;
    }
    public void addAtEnd(int number){
        Node temp=new Node();
        temp.setData(number);       //temp is new node
        
        if(size==0){                //List is empty, create head node
            temp.setNext(null);
            start=temp;
        }else{  
            Node tempHead=start;        //store header node "start" to a temp node as "tempHead"
            while(start.getNext()!=null){
                start=start.getNext();
            }
            start.setNext(temp);   //temp.setNext will be null by default.
            start=tempHead;        //Since start pointer has moved to the end, store the old tempHead node to start again.
        }
        size++;
    }
    
    public Node getNodeAt(int nodePos) {
        if(nodePos>=size || nodePos<0){
            return null;
        }
        Node temp = start; //Move start pointer to front
        for(int counter=0; counter<nodePos; counter++){
            temp = temp.next;  //Move till the node position
        }
        return temp;
    }
    public void removeAtPosition(int position) {
        System.out.println("\nRemoving from position: "+position);
        Node temp = getNodeAt(position-1);            
        temp.setNext(temp.getNext().getNext());  //here temp.getNext() is getting removed/reference removed from LinkedList.
        size--;
    }
    public void reverseList() {
        System.out.println("\nReversing the List now.");
        if(size<=1){
            System.out.println("Not required, only one Node.");
        }
        Node previousNode = null; 
        Node currentNode = start; 
        Node nextNode = null;
        
        while(currentNode.next != null) {
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        currentNode.next = previousNode;
        start = currentNode;
    }
    
    public Node getFirst(){
        return getNodeAt(0);
    }

    public Node getLast(){
        return getNodeAt(size-1);
    }

    public boolean contains(int number){
        Node temp = start; //Move pointer to front
        for(int counter=0;counter<size;counter++){
            if(temp.getData()==number)
                return true;
            temp = temp.next;
        }
        return false;
    }
    public void clear(){    
        System.out.println("\nRemoving all the elements in the List: "+size);
        start = null;
        size=0;
    }
    public void displayList(){    
        Node temp=start;  //Save start into a temp Variable
        if(size>0)
            System.out.println("Size: "+size);
        else
            System.out.println("No elements to display.");
        
        for(int i=0;i<size && temp!=null;i++){
            System.out.print(temp.getData()+", ");
            temp=temp.getNext();
        }
    }
}
----------

package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class SinglyLinkedListTest {
    public static void main(String a[]){
        SinglyLinkedList list=new SinglyLinkedList();
        System.out.println("Adding at Begining...");
        list.addAtFirst(10); list.addAtFirst(60);  list.addAtFirst(3); list.addAtFirst(2); list.addAtFirst(70);
        list.displayList(); 
        System.out.println("\nlist.getNodeAt(3): "+list.getNodeAt(3));
        list.clear();
        list.displayList();
        
        System.out.println("\nAdding at End...");
        list.addAtEnd(10);   list.addAtEnd(60);    list.addAtEnd(3);   list.addAtEnd(2);   list.addAtEnd(70);
        list.displayList();
        
        list.reverseList();
        list.displayList();        
        
        System.out.println("\nGet Last Element: list.getLast(): "+list.getLast());
        System.out.println("\nContent Check: list.contains(3): "+list.contains(3));
        System.out.println("Content Check: list.contains(13): "+list.contains(13));
        
        System.out.println("\nNode Check: list.getNodeAt(3): "+list.getNodeAt(3));
        System.out.println("Node Check: list.getNodeAt(10): "+list.getNodeAt(10));
        
        list.removeAtPosition(3);
        list.displayList();
        System.out.println("\nNode Check: list.getNodeAt(3): "+list.getNodeAt(3));
    }
}
-----------------------------------
//Output:
Adding at Begining...
Size: 5
70, 2, 3, 60, 10, 
list.getNodeAt(3): 60

Removing all the elements in the List: 5
No elements to display.

Adding at End...
Size: 5
10, 60, 3, 2, 70, 
Reversing the List now.
Size: 5
70, 2, 3, 60, 10, 
Get Last Element: list.getLast(): 10

Content Check: list.contains(3): true
Content Check: list.contains(13): false

Node Check: list.getNodeAt(3): 60
Node Check: list.getNodeAt(10): null

Removing from position: 3
Size: 4
70, 2, 3, 10, 
Node Check: list.getNodeAt(3): 10
-----------------------------------------------------------
Another useful algorithm for Singly Linked List:
Practice Question: Determine whether a linked list contains a cycle.
    
Ans: Traversal of a linked list with a cycle will never end, so there needs to be some method to keep track 
    of what nodes have been encountered. One idea is to mark nodes that have been seen, either by adding a flag 
    to the node itself or storing information about the node in a separate data structure. Unfortunately, this 
    method requires modification of the node and/or additional space.

    With linked list problems, the solution usually takes advantage of multiple pointers. How can we use another 
    pointer to help us out? The previous problem advanced two pointers at a fixed interval between each other, 
    but that doesn’t seem to help. A better idea is to advance the pointers at two different speeds.

    One pointer will travel at twice the speed of the other, so in an acyclic list, the fast one will reach the end. 
    However, in a cyclic list, both pointers loop endlessly, but the faster pointer will lap the slower pointer at 
    some point, so if the faster pointer ever catches up to the slower pointer, the list has a cycle.

    To make one pointer “faster” than the other, just advance it two nodes instead of one. However, be aware of null 
    pointers.

The running time for this algorithm is O(n). For the ACYCLIC case, the faster pointer will reach the last node 
after traversing the entire list. For the CYCLIC case, the slower pointer will only go around a loop at most once, 
and the faster pointer will only go through a loop at most twice, so in the worst case 3n nodes are examined, which 
is still an O(n) algorithm. 

Code:
----------------
public static boolean hasCycle(Node head) {
    Node fast = head;
    Node slow = head;
 
    while (fast != null && slow != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
 
        if (slow == fast) {
            return true;
        }
    } 
    return false;
}
==================END=======================