Data Structure: Linked List

LinkedList.java

//Linked List class
//Author: Milon

import java.util.Scanner;
import java.util.Iterator;
import java.util.NoSuchElementException;

//Node class
class Node{
    //Instance variable
    private Object data;
    private Node nextNode;

    //Constructor
    public Node(){
        data = null;
        nextNode = null;
        }

    public Node(Object item, Node next){
        data = item;
        nextNode = next;
        }

    //Set methods
    public void setData(Object item){
        data = item;
        }

    public void setNextNode(Node next){
        nextNode = next;
        }

    //Get methods
    public Object getData(){
        return data;
        }

    public Node getNextNode(){
        return nextNode;
        }

    //Overloaded toString() method
    public String toString(){
        return ("" + data);
        }
    }


//LinkedList class
public class LinkedList{
    //Instance variable
    protected Node head;
    private int size;

    //Constructor
    public LinkedList(){
        head = null;
        size = 0;
        }

    //Returns is the list empty
    public boolean isEmpty(){
        return head == null;
        }

    //Returns the size
    public int size(){
        return size;
        }

    //Insert an element at first position
    public void addFirst(Object item){
        head = new Node(item, head);
        ++size;
        }

    //Insert an element at last position
    public void addLast(Object item){
        if(isEmpty()){
            addFirst(item);
            return;
            }
        Node current = head;
        while(current.getNextNode() != null)
            current = current.getNextNode();
        Node temp = new Node(item, current.getNextNode());
        current.setNextNode(temp);
        ++size;
        }

    //Show the first item
    public Object showFirst(){
        if(head != null)
            return head.getData();
        else{
            System.out.println("LinkedList is empty.");
            //throw new NoSuchElementException();
            return null;
            }
        }

    //Show the last item
    public Object showLast(){
        if(head == null){
            System.out.println("LinkedList is empty.");
            //throw new NoSuchElementException();
            return null;
            }
        else{
            Node current = head;
            while(current.getNextNode() != null)
                current = current.getNextNode();
            return current.getData();
            }
        }

    //Show the nth element
    public Object peek(int position){
        Node current = head;
        for(int i=0;i<position && current != null;i++)
            current = current.getNextNode();
        return current.getData();
        }

    //Remove first element
    public Object removeFirst(){
        if(!isEmpty()){
            Node current = head;
            head = head.getNextNode();
            --size;
            return current.getData();
            }
        else{
            System.out.println("LinkedList is empty.");
            //throw new NoSuchElementException();
            return null;
            }
        }

    //Remove last element
    public Object removeLast(){
        if(isEmpty()){
            System.out.println("LinkedList is empty.");
            return null;
            }
        if(head.getNextNode() == null)
            return removeFirst();
        Node current = head;
        while(current.getNextNode().getNextNode() !=null)
            current = current.getNextNode();
        Object obj = current.getNextNode().getData();
        current.setNextNode(null);
        --size;
        return obj;
        }

    //Check does the item exists in the list
    public boolean contains(Object item){
        Node current = head;
        while(current.getNextNode() != null){
            if(item.equals(current.getData()))
                return true;
            else
                current = current.getNextNode();
            }
        return false;
        }

    //Reverse the list
    public void reverse(){
        Node current, next, loop;
        if(head == null)
            return;
        current = head;
        next = head.getNextNode();
        loop = null;
        while(next != null){
            current.setNextNode(loop);
            loop = current;
            current = next;
            next = next.getNextNode();
            }
        head = current;
        head.setNextNode(loop);
        }

    //Overloaded toString method to show the entire list
    public String toString(){
        String str = "[ ";
        if(head != null){
            str += head.getData();
            Node current = head.getNextNode();
            while(current.getNextNode() != null){
                str += ", " + current.getData();
                current = current.getNextNode();
                }
            str += ", " + current.getData();
            }
        str += " ]";
        return str;
        }

    }

LinkedListImplement.java

//Linked List Implementation class
//Author: Milon

import java.util.Scanner;
import java.util.Random;

public class LinkedListImplement{
    public static void main(String args[]){
        LinkedList list = new LinkedList();
        Scanner input = new Scanner(System.in);
        Random rand = new Random();

        System.out.print("How many item do you want to insert first: ");
        int n = input.nextInt();

        for(int i=0;i<n;i++)
            list.addFirst(new Integer(rand.nextInt(100)));

        while(true){
            System.out.println("\n");
            System.out.println("* * * * * LinkedList Implementation * * * * *");
            System.out.println(" 1\. Show the list.");
            System.out.println(" 2\. Insert an element at first position.");
            System.out.println(" 3\. Insert an element at last position.");
            System.out.println(" 4\. Show the first element.");
            System.out.println(" 5\. Show the last element.");
            System.out.println(" 6\. Show the nth element.");
            System.out.println(" 7\. Reverse the list.");
            System.out.println(" 8\. Show the list size.");
            System.out.println(" 9\. Search an element in the list.");
            System.out.println("10\. Remove first element.");
            System.out.println("11\. Remove last element.");
            System.out.println("12\. Exit\n\n");

            System.out.print("Enter your choice: ");
            int choice = input.nextInt();

            switch(choice){
                case 1:
                        System.out.println("The whole list is:");
                        System.out.println(list.toString());
                        break;

                case 2:
                        System.out.print("Enter the element: ");
                        int item = input.nextInt();
                        list.addFirst(new Integer(item));
                        System.out.println("Item inserted successfully.");
                        break;

                case 3:
                        System.out.print("Enter the element: ");
                        int element = input.nextInt();
                        list.addLast(new Integer(element));
                        System.out.println("Item inserted successfully.");
                        break;

                case 4:
                        System.out.println("The first element is: "+list.showFirst());
                        break;

                case 5:
                        System.out.println("The last element is: "+list.showLast());
                        break;

                case 6:
                        System.out.print("Enter the position: ");
                        int pos = input.nextInt();
                        System.out.println("The "+pos+"th element is: "+list.peek(pos-1));
                        break;

                case 7:
                        //list.head = list.reverse(list.head, null);
                        list.reverse();
                        System.out.println("List reversed successfully.");
                        break;

                case 8:
                        System.out.println("List size is: "+list.size());
                        break;

                case 9:
                        System.out.print("Enter the searching element: ");
                        int key = input.nextInt();
                        if(list.contains(key))
                            System.out.println("Item found.");
                        else
                            System.out.println("Item not found.");
                        break;

                case 10:
                        System.out.println("First element " + list.removeFirst() + " removed.");
                        break;

                case 11:
                        System.out.println("Last element " + list.removeLast() + " removed.");
                        break;

                case 12:
                        System.exit(1);
                        break;

                default:
                        break;
                }
            }
        }

    }