To construct Linked List we’ll need two things. One is an internal representation of Linked List Node, the other is the reference to the first element of the list – the head. This can be represented like here:

package com.farenda.tutorials.algorithms.lists;

public class LinkedList<T> {

    // internal node of the list:
    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    // Reference to the first element:
    private Node<T> head;

    // linked list methods...
}

To help ourselves to verify results of our work we’ll start with implementation of a helper method that prints the contents of a Linked List. As many algorithms on Linked Lists this one works in linear time – O(N), because it has to go through the whole list:

public void printContent() {
    StringBuilder sb = new StringBuilder("[");
    Node node = head;
    while (node != null) {
        sb.append(node.data).append(',');
        node = node.next;
    }
    int lastComma = sb.lastIndexOf(",");
    if (lastComma != -1) {
        sb.deleteCharAt(lastComma);
    }
    sb.append(']');
    System.out.println(sb);
}

The algorithm has to handle two cases:

1. The list is empty. In this case we have to set the new element as the head of list.
2. The list has elements. In this case we have to find the last element and append the new element after it.

public void add(T value) {
    Node<T> newNode = new Node<>(value);
    if (head == null) {
        head = newNode;
    } else {
        Node<T> last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }
}

Again, the algorithm has linear time complexity O(N), because it has to traverse whole list to add element at the end.

Another useful method to have is list.size(), which will return the number of elements in Linked List. It works almost exactly the same as addition, therefore it’s running time is proportional to the size of the list, so its O(N):

public int size() {
    int count = 0;
    Node<T> node = head;
    while (node != null) {
        ++count;
        node = node.next;
    }
    return count;
}

Let’s implement a few JUnit tests that will help us verify correctness of the algorithms:

package com.farenda.tutorials.algorithms.lists;

import org.junit.Test;

import static org.junit.Assert.*;

public class LinkedListTest {

    private LinkedList<Integer> list = new LinkedList<>();

    @Test
    public void shouldBeEmpty() {
        assertEquals(0, list.size());
        list.printContent();
    }

    @Test
    public void shouldHaveAddedElements() {
        list.add(1);
        assertEquals(1, list.size());
        list.printContent();

        list.add(42);
        assertEquals(2, list.size());
        list.printContent();

        list.add(2);
        list.add(3);
        assertEquals(4, list.size());
        list.printContent();
    }
}

Now, when we run the above tests they will output something similar to (order may be different, due to the different execution order):

[1]
[1,42]
[1,42,2,3]
[]

• Algorithms and Data Structures Tutorial