Simple Linked List implementation in Java

Have you ever wondered what is Linked List? Linked List is a dynamic abstract data type comprised of node(s). By meaning of dynamic, the size of Linked List can grow and shrink. There are many types of Linked List, however, the most simple one is Singly Linked List. One you mastered how to create singly linked list, the other type of linked list (doubly linked list and circular linked list) is just a matter of expansion.

I will try to make the most simple linked list implementation possible. There are three class we will create:

  1. Node. Which will be attached to the Linked List as the head, or the other element after the head.
  2. LinkedList. Is a parent which link to head, to other element, to other element, until to the last element.
  3. LinkedListApp. Which will demonstrate the linked list.
package latihan3;

/**
 *
 * @author adampbe
 */
public class Node {
    protected Node right;
    protected Object data;

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

The Node class will have 2 protected variables for right which will reference to any other node, and data where the data will be referenced. The data here is of type Object, it can be any data as long as it is not primitive data type (like int, float, and so on).

package latihan3;

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

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

    public void insert(Object data)
    {
    if (head == null)
    {
        Node head = new Node();
        head.data = data;
        this.head = head;
    }
    else
    {
        Node oldHead = head;
        Node newHead = new Node();
        newHead.right = oldHead;
        newHead.data = data;
        this.head = newHead;
    }
    nElems++;
    }

    public void removeFirst()
    {
    Node oldHead = this.head;
    this.head = oldHead.right;
    oldHead = null; //garbage collect it
    nElems--;
    }

    public Object getFirst()
    {
    return this.head.data;
    }

    public Node getHead()
    {
    return this.head;
    }

    public void walk()
    {
    Node theNode = null;
    for (int i=0; i<nElems; i++)
    {
        if (theNode == null)
        theNode = this.head;
        else
        theNode = theNode.right;

        System.out.println(theNode.data);
    }
    }

}

The LinkedList class is so simple, it has only the following procedures:

  • insert(), which will create a new node. If no head, it will create the node as head, if there is head, we will create a new head and link it to the old head.
  • removeFirst(), which will remove head. note: how if there is no head?
  • getFirst(), will return the data contained in the head
  • getHead(), will return the head
  • walk(), which will print the link’s data from node to node.

And here is the main app to demonstrate the linked list application.

package latihan3;

/**
 *
 * @author adampbe
 */
public class LinkedListApp {
    public static void main (String[] args)
    {
    LinkedList ll = new LinkedList();

    ll.insert(new String("Ardian Prakoso W."));
    ll.insert(new String("Adam Pahlevi B."));
    ll.insert(new String("Tommy Cuaca"));
    ll.insert(new String("Ardian Wisnu"));
    ll.insert(new String("Alfio Ridho"));
    ll.insert(new String("Felita Rahadianti E."));
    ll.insert(new String("Bagas S. Perdana"));
    ll.insert(new String("Timmy Richardo"));
    ll.insert(new String("Fauzi Bowo"));
    ll.insert(new String("Anugerah Widya H."));

    System.out.println("Data in the Linked List:");
    ll.walk();
    System.out.println("\nRemove the head");
    ll.removeFirst();
    System.out.println("\nList after a head already removed:");
    ll.walk();
    System.out.println("\nThe new first head is:");
    System.out.println(ll.getHead().data);

    }
}

If we run the program, it will return:

run:
Data in the Linked List:
Anugerah Widya H.
Fauzi Bowo
Timmy Richardo
Bagas S. Perdana
Felita Rahadianti E.
Alfio Ridho
Ardian Wisnu
Tommy Cuaca
Adam Pahlevi B.
Ardian Prakoso W.

Remove the head

List after a head already removed:
Fauzi Bowo
Timmy Richardo
Bagas S. Perdana
Felita Rahadianti E.
Alfio Ridho
Ardian Wisnu
Tommy Cuaca
Adam Pahlevi B.
Ardian Prakoso W.

The new first head is:
Fauzi Bowo
BUILD SUCCESSFUL (total time: 0 seconds)

Now, how come Linked List can grow and shrink, theoretically unlimited practically depends on RAM, unlike array in Java?

See the picture above. Linked list is actually a node that is connected to one another. The first node is often called head, and the last node is often called tail. Once a node is created, it will links either to other node or to null. And, when a node is deleted, the link has to be linked to other node if appropriate.

Now, can you implement a getTail() in the LinkedList class? You can also modify the singly linked list into doubly linked list by having left and right node on each node, so there will be also insertHead(), insert() and insertTail(), getHead(), and getTail(), removeHead(), and removeTail().

Let’s create 🙂

NB. There is an implementation of LinkedList already in Java.

Advertisements

3 thoughts on “Simple Linked List implementation in Java

  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