Insert(newElement)
    Find node in linked list e
    If e.numElements < e.data.size
        e.data.push(newElement)
        e.numElements ++
    else
        create new Node e1
        move final half of e.data into e1.data
        e.numElements = e.numElements / 2
        e1.data.push(newElement)
        e1.numElements = e1.data.size / 2 + 1

Delete(element)
    Find element in node e
    e.data.remove(element)
    e.numElements --
    while e.numElements < e.data.size / 2
        put element from e.next.data in e.data
        e.next.numElements --
        e.numElements ++
    if e.next.numElements < e.next.data.size / 2
        merge nodes e and e.next
        delete node e.next

/**
 * Created by on 3/24/2018.
 */
public class UnrolledLinkedList {
    private Node head;
    private Node tail;
    private int sizeNode;
    private int nNode;

    public UnrolledLinkedList(int capacity){
        head = null;
        tail = null;
        this.sizeNode = capacity + 1;
        nNode = 0;
    }

    public UnrolledLinkedList() {
        this(16);
    }
    public boolean isEmpty () {
        return head == null;
    }

    public int size(){
        return nNode;
    }

    public void clear() {
        head = null;
        tail = null;
        nNode = 0;
    }

    public void insert(int val) {
        nNode++;
        // if the linked list is emmpty, just generate the
        // the head
        if (head == null) {
            head = new Node(sizeNode);
            head.array[0] = val;
            head.numElements++;
            tail = head;
            return;
        }

        // if the tail node has room to store new element
        //just insert to the tail node

        if (tail.numElements + 1 < sizeNode) {
            tail.array[tail.numElements] = val;
            tail.numElements++;
        } else {
            Node cur = new Node(sizeNode);
            // move half the elements from the tail to the nex tnode
            int j = 0;
            for(int i = tail.numElements / 2 + 1; i < tail.numElements; i++) {
                cur.array[j++] = tail.array[i];
            }
            cur.array[j] = val;
            cur.numElements = j + 1;
            tail.numElements = tail.numElements / 2 + 1;
            tail.next = cur;
            tail = tail.next;
        }

    }

    public boolean search(int val) {
        if (head == null) {
            return false;
        }

        Node cur = head;
        while(cur != null) {
            for(int i = 0; i < cur.numElements; i++) {
                if(cur.array[i] == val) {
                    return true;
                }
            }
            cur = cur.next;
        }
        return false;
    }
    /*
    Delete(element)
    Find element in node e
    e.data.remove(element)
    e.numElements --
            while e.numElements < e.data.size / 2
                put element from e.next.data in e.data
                e.next.numElements --
                e.numElements ++
            if e.next.numElements < e.next.data.size / 2
    merge nodes e and e.next
    delete node e.next
    */

    public void delete(int val) {
        if (head == null) {
            return ;
        }

        Node cur = head;
        while(cur != null) {
            for(int i = 0; i < cur.numElements; i++) {
                if(cur.array[i] == val) {
                    for(int j = i; j < cur.numElements - 1; j++) {
                        cur.array[j] = cur.array[j + 1];
                    }
                    cur.numElements--;
                    return;
                }
            }
            cur = cur.next;
        }
        if (cur == null) {
            return;
        }

        //if the cur.numElement < sizeNode / 2, move the next node data to cur
        while (cur.numElements < sizeNode/ 2) {
            cur.array[cur.numElements++] = cur.next.array[cur.next.numElements - 1];
            cur.next.numElements--;
        }
        if (cur.next.numElements < sizeNode / 2) {
            // merge cur and next data
            for(int i = 0; i < cur.next.numElements; i++) {
                cur.array[cur.numElements++] = cur.next.array[i];
            }
            cur.next = cur.next.next;
        }
    }

    class Node {
        int numElements;
        int[] array;
        Node next;
        public Node (int n) {
             next = null;
             this.numElements = 0;
             array = new int[n];
        }
    }
}