Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Linked List add element at the end

farenda 2017-05-28 0

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:

  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.

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

References:

  • Algorithms and Data Structures Tutorial
Share with the World!
Categories Algorithms Tags algorithms, java, lists
Previous: Create Java Streams
Next: Linked List – insert element at position

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok