How to Implement Linked List in Java with JUnit Test Example

In this article, we will learn two things, how to implement a linked list from scratch in Java and how to write a unit test using JUnit framework. Though Java has LinkedList class, which is an implementation of the doubly linked list, its good to know how to implement singly linked list in Java, mostly to practice coding interview questions. Coming to back to writing a unit test, from time to time, I have said that a Java programmer must write unit tests. IMHO, unit testing is the best development practice to improve code quality. Fortunately, Java ecosystem has the luxury of great unit testing frameworks in form of JUnit and TestNG, and every Java developer should take advantage of this.

Writing unit tests is one of the best programming practices along with code review. It's natural and I had experienced it myself that unit test, not only provides code coverage, but also present unique opportunities for code refactoring.

Many times, while writing unit tests, I have discovered better names for my methods and refactored large methods into smaller ones. JUnit tests also help to organize code and evaluate encapsulation. There is a good chance of you discovering that a particular field or method is exposing implementation detail, and should be abstracted in the public method. What all this means is, you, a Java developer, must write unit tests.

Since it always helps to start smaller, this JUnit tutorial will present another simple JUnit example to show how to write unit tests in Java. In this JUnit tutorial, we will implement a linked list in Java and we will write unit test cases for a linked list.

For those, who are not familiar with the linked list, it's one of the fundamental data structures to store objects, like an array, which is also used to store objects. By the way, there is much difference between the linked list and array data structure, which is the subject of another blog post, but the main difference is in the way objects are stored. An array needs contiguous memory, while the linked list doesn't need that.

Basics of linked list data structure in Java

Before writing an implementation of linked list data structure, let's revise some terminology. There is two kinds of linked list, singly and doubly linked list. A singly-linked list allows you to traverse in one direction, mostly forward, while the doubly linked list allows you to traverse in both direction, forward, and backward. Since we will implement a singly linked list, we will keep discussion limited with that. linked list store data in the form of nodes, which contains data and reference to next node.

The first node of the linked list is called head and last node is called tail. A linked list is said empty if it doesn't contain any node i.e. head points to null. In this JUnit tutorial, we will create a singly linked list with three methods isEmpty(), length() and append().

As the name suggests isEmpty() will return true, if linked list is empty, length() will return a number of nodes in a linked list, and append() is used to append a node at tail. After that, we will write unit tests for this linked list class. By the way, here is a good example of how singly linked list look like :

Singly Linked List Implementation in Java

/**
  * A Simple linked list implementation in Java to demonstrate unit testing.
  * JUnit tests will be created to test this singly linked list.

  * @author Javin Paul
  */
public class SinglyLinkedList {
    private Node head;  // Head is first node in linked list

    public boolean isEmpty(){
        return length() == 0;
    }
 
    public void append(String data){
        if(head == null){
            head = new Node(data);
            return;
        }
        tail().next = new Node(data);
    }
 
    private Node tail() {
        Node tail = head;
     
        // Find last element of linked list known as tail
        while(tail.next != null){
            tail = tail.next;
        }      
        return tail;
     
    }
 
    public int length() {
       int length = 0;
       Node current = head;  // Starts counting from head - first node
       while(current != null){
           length ++;
           current = current.next;
       }
       return length;
    }

 
    // Node is nested class because it only exists along with linked list
    // Node is private because it's implementation detail
    private static class Node {
        private Node next;
        private String data;

        public Node(String data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return this.data;
        }
    }
}

When you run these unit test as shown here, you will see the following output, which is self-explanatory. Had any test failed or an error occurred e.g. an unexpected exception, JUnit would have shown that in this output.

Testsuite: SinglyLinkedListTest
Tests run: 1, Failures: 0, Errors: 0, Time elapsed: 0.828 sec

Now, there are couple of approaches to write Unit tests in Java. Some programmers prefer to write unit test based on functions e.g. testAppend(), testIsEmpty() or testLength(), and this is also default approach used by IDE like Netbeans and Eclipse. By the way, you can also combine small tests into a complete one, by testing use cases e.g. testing a fresh linked list without any element, testing a linked list with some elements etc.

In this JUnit example, I have a combined test of all three methods into one. Though it's not complete, but it test one use case. You can still add more test cases to test append() with different input e.g. null. Any way let's have a look at our JUnit test case.

import org.junit.Test;
import static org.junit.Assert.;

/**
  * JUnit test cases for linked list data structure in Java. 
  * This class has just one method to test behavior of a 
  * newly created linked list
  *
  * @author Javin Paul
  */
public class SinglyLinkedListTest {
 
    @Test
    public void testNewLinkedList(){
        SinglyLinkedList singly = new SinglyLinkedList();
        assertTrue(singly.isEmpty());       // linked list should be empty
        assertEquals(0, singly.length());   
        // length of linked list should be zero
     
        singly.append("ABC");
        assertFalse(singly.isEmpty());     // linked list should not be empty
        assertEquals(1, singly.length());  
        // length of linked list should be 1
     
    }
}

I have just kept one method testNewLinkedList(), annotated with @Test annotation. This is the minimum requirement for writing unit tests for Java programs. of course, you can use other JUnit 4 annotations like @Before, @After, @BeforeClass or @AfterClass to do some setup and cleanup work, for this JUnit example, we don't need that. If you notice, I have also put comments around tests to make test cases more obvious, 

One of the code comment best practice to follow while writing unit tests. You can use this example to further learn writing unit test, I would suggest implement few more methods like delete() and start writing test cases for that. 

Working with linked list not only helps you to understand unit testing better, but also improves your data structure concept, as linked list forms a good chunk of data structure interview questions.


That's all on this simple JUnit example of implementing a singly linked list in Java and writing unit test using JUnit. Follow the principle of start small and improve step by step. In order to develop unit testing habit, you can also create an empty test method, while understanding requirement and coding, and mark them with @Ignore annotation, to avoid failing tests. Just like coding, unit testing is also an art, which gets better with practice and constant improvement.


If you love unit testing and You will also find the following Java Unit testing Tutorials useful :

• 5 Great books to Learn JUnit and Unit testing in Java (list)
• JUnit best practices for Java Programmers (best practices)
• How to test exceptions in JUnit 4? (solution)
• What is difference between Mock and Stub object? (answer)
• JUnit testing tips - Constructor is called before executing test methods (tips)
• What is difference between Maven, ANT and Jenkins? (answer)
• 10 tips to become a better Software Programmer (tips)
• Why Static code analysis is Important? (opinion)