Linked List

What is it ? : Plain old data structure, no random access, fast add front O(1)

It is a list of nodes which are linked together. A node contains data and next .

• First node is Head, there is no pointer
• Node
• Last node is Tails , and the next is null

Disadvantage :

• No random access
• Get/Set is linear or O(n)

Advantage

• Super fast insert/deletes O(1)
• Can grow incrementally which mean there is no fixed capacity

Example code

public class LinkedList {

    private Node head;

    public void addFront(String data){
        //Create new node
        Node newNode = new Node(data);

        if(head == null) {
            head = newNode;
            return;
        }
        // set new node to current head
        newNode.next = head;

        // set current head to new node
        this.head = newNode;
    }

    public String getFirst() {
        return this.head.data;
    }

    public String getLast() {
        if(head == null) {
            throw new IllegalStateException("Empty list");
        }
        Node current = head;
        while (current.next != null) {
            current = current.next; // O(n)
        }
        // at tail
        return current.data;
    }

    public void addBack(String data) {
        Node newNode = new Node(data);
        if(head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next !=null) {
            current = current.next;
        }
        current.next = newNode;
    }

    private static class Node {
        String data;
        Node next;
        public Node(String data) {
            this.data = data;
        }
    }
}

import com.cankube.monoexample.datastuctures.LinkedList;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class LinkedListTest {

    private LinkedList objectUnderTest;

    @BeforeEach
    void setUp() {
        objectUnderTest = new LinkedList();
    }

    @Test
    void addFront() {
        objectUnderTest.addFront("1");
        objectUnderTest.addFront("2");
        objectUnderTest.addFront("3");
        Assertions.assertEquals("3", objectUnderTest.getFirst());
        Assertions.assertEquals("1", objectUnderTest.getLast());
    }

    @Test
    void getFirst() {
        objectUnderTest.addFront("1");
        Assertions.assertEquals("1", objectUnderTest.getFirst());
    }

    @Test
    void getLast() {
        objectUnderTest.addFront("1");
        objectUnderTest.addFront("2");
        objectUnderTest.addFront("3");
        Assertions.assertEquals("1", objectUnderTest.getLast());
    }

    @Test
    void addBack() {
        objectUnderTest.addBack("1");
        objectUnderTest.addBack("2");
        objectUnderTest.addBack("3");
        Assertions.assertEquals("1", objectUnderTest.getFirst());
        Assertions.assertEquals("3", objectUnderTest.getLast());
    }
}

Summary:

• addFront O(1)
• addBack O(n)
• delete O(n)
• No random access
• No fixed capacity
• Always the right size

Download code at here