Append

• Adds element at the end of linked list

Case: Linked list is empty

You simply need to create a new node with provided value and point head and tail to the created node. Since you added a node, increment the linked list as well.

public class LinkedList {
    
    public Node append(int value) {
        // Create new node from given value
        Node node = new Node(value);
        if (length == 0) {
            head = node;
            tail = node;
        }
        length++;
        return node;
    }
}

Case: Linked List is not empty

Consider the following linked list.

First you need to point the last node to newly created node. For this simply set the tail node’s next reference to the newly created node.

tail.next = node;

Now make the tail reference to the newly created node as it now becomes the tail node.

tail = node;

public class LinkedList {
    
    public Node append(int value) {
        Node node = new Node(value);
        if (length == 0) {
            head = node;
            tail = node;
        }
        tail.next = node;
        tail = node;
        length++;
        return node;
    }
}

Testing

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class LinkedListTest {

    @Test
    public void append() {
        LinkedList linkedList = new LinkedList();
        linkedList.append(1); // append when length equals 0
        assertEquals(1, linkedList.getLength());
        assertEquals(List.of(1), convertToArrayList(linkedList));
        linkedList.append(2); // append when length greater than 0
        linkedList.append(3);
        linkedList.append(4);
        assertEquals(4, linkedList.getLength());
        assertEquals(List.of(1, 2, 3, 4), convertToArrayList(linkedList));
    }
    
    public List<Integer> convertToArrayList(LinkedList linkedList) {
        List<Integer> list = new ArrayList<>();
        LinkedList.Node temp = linkedList.getHead();
        while (temp != null) {
            list.add(temp.value);
            temp = temp.next;
        }
        return list;
    }
}

Time complexity

Since appending an element requires creating a new node and rearranging references so, this operation has a constant worse-case time complexity of O(1).