Linked List

Posted by

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

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.