Java Complete Application for Singly Linked List

Today’s tutorial class, I got a question for the lecturer to implement a singly linked list into a complete, working example of Java command line program. The whole class get 2 hours for programming this, and I completely finished within the first one hour. In my opinion, this program is not so challenging, maybe a doubly linked list would make this program a bit more challenging.

I assume you already familiar with linked list, if not, you can refer to this page for basic implementation of singly linked list.

Node.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tutorial_6;

/**
 *
 * @author adampbe
 */
public class Node<E> {
    protected E data;
    protected Node<E> right;

    public Node()
    {
    data = null;
    right = null;
    }
}

LinkedList.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tutorial_6;

/**
 *
 * @author adampbe
 */
public class LinkedList<E> {
    private Node<E> head;
    private int nElems;

    public LinkedList()
    {
    head = null;
    nElems = 0;
    }

    public void insertFirst(E data)
    {
    if (head == null)
    {
        Node<E> newHead = new Node<E>();
        newHead.data = data;
        this.head = newHead;
    }
    else
    {
        Node<E> oldHead = this.head;
        Node<E> newHead = new Node<E>();
        newHead.right = oldHead;
        newHead.data = data;
        this.head = newHead;
    }
    nElems++;
    }

    public boolean deleteItem(int position)
    {
    if (position > nElems - 1) return false;

    Node<E> currentNode = null;
    Node<E> lastNode = this.head;

    for (int i=0; i<nElems; i++)
    {
        currentNode = (currentNode == null) ? this.head : currentNode.right;
        if (i == position)
        {
        //next node of intended deleted node
        Node<E> nextNode = currentNode.right;
        //connect previous node to the nextNode. so that the middle node can be deleted
        lastNode.right = nextNode;
        //garbage collect current node
        currentNode = null; 
        //if deleted at head, make the next node as the new head
        if (i==0) this.head = nextNode; 
        nElems--;
        return true;
        }
        lastNode = currentNode;
    }
    return false;
    }

    public void print(int min_range, int max_range)
    {
    if (min_range > max_range || max_range > nElems)
    {
        //exception
        System.out.println("Range out of bound");
    }
    else
    {
        Node<E> currentNode = null;
        for (int i=0; i<nElems; i++)
        {
        currentNode = (currentNode == null) ? this.head : currentNode.right;
        if (i >= min_range && i <= max_range)
        {
            System.out.println("The node " + i + "'s data: " + currentNode.data);
        }
        }
    }
    }

    //print all
    public void print()
    {
    this.print(0, nElems);
    }

}

LinkedListApp.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tutorial_6;
import java.util.*;
/**
 *
 * @author adampbe
 */
public class LinkedListApp {
    public static void main (String[] args)
    {
    LinkedListApp theApp = new LinkedListApp();
    theApp.printHeader();

    LinkedList<Integer> ll = new LinkedList<Integer>();

    for(;;)
    {
        theApp.printMenu();
        int uinput = theApp.getUserInput("\nPlease specify the action (1-5): ");
        switch (uinput)
        {
        //add item
        case 1:
            int nbr = theApp.getUserInput("Key in an integer:");
            ll.insertFirst(nbr);
            break;
        //delete item
        case 2:
            int index = theApp.getUserInput("Key in an index:");
            if (ll.deleteItem(index))
            {
            System.out.println("Delete success");
            }
            else
            {
            System.out.println("Delete not success");
            }
            break;
        //print range
        case 3:
            int min_range = theApp.getUserInput("Min range: ");
            int max_range = theApp.getUserInput("Max range: ");
            ll.print(min_range, max_range);
            break;
        //print all
        case 4:
            ll.print();
            break;
        //exit
        case 5:
            System.exit(0);
            break;
        }
    }
    }

    public void printHeader()
    {
    System.out.println("=================================================");
    System.out.println("= LINKED LIST APP DEMO BY ADAM PAHLEVI B        =");
    System.out.println("=================================================");
    }

    public void printMenu()
    {
    System.out.println("1. Add a new item");
    System.out.println("2. Delete an item");
    System.out.println("3. Show number of items");
    System.out.println("4. Show all items");
    System.out.println("5. Exit");
    }

    public int getUserInput(String command)
    {
    System.out.println(command);
    Scanner kboard = new Scanner(System.in);
    int uinput = kboard.nextInt();
    return uinput;
    }
}

Different from the implementation of singly linked list previously, this code takes advantage of generics. This is the screen shoot of the program run on Windows 7 machine.

I think, there is nothing to be explained here. This is just a singly linked list which explanation almost the same with the other implementation here. Clearly nothing new.

Advertisements

One thought on “Java Complete Application for Singly Linked List

  1. Pingback: Plain English Explanation of Binary Tree with Java Code | fbk

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s