Linked List is a simple data structure. Implementing it from scratch helps to understand its properties. We’ll implement Linked List add, size, and print its contents.

## Linked List construction

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... }

## Print content of Linked List

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); }

## Add element to the end of Linked List

The algorithm has to handle two cases:

- The list is empty. In this case we have to set the new element as the
**head of list**. - 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.

## Count number of elements in Linked List

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; }

## Unit tests

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] []