Indeed Coding Round 2 - Unrolled Linked List

Indeed Round 2
mail@pastecode.io avatar
unknown
java
2 years ago
2.1 kB
1
Indexable
Never
/*

head
  v
{ size 3 } -> [I, O, S, _, _]
  v
{ size 2 } -> [A, J, _, _, _]
  v
null

get(0) -> I
get(1) -> O
get(4) -> J


head
  v
{ size 5 } -> [I, O, H, W, _]
  v
{ size 1 } -> [S, _, _, _, _]
  v
{ size 3 } -> [T, A, J, _, _]
  v
null

insert(2, H) get(2)->H
insert(4, T) 
insert(3, W)
insert(1, W)
insert(1, W)
*/

class Node {
    Node next;
    char[] values;
    int size;
}
class UnrolledLinkedList {
    Node head;
    int length;
    
    public char get(int index) {
        if (head == null) {
            throw new IndexOutOfBoundsException();
        }
        Node curr = head;
        while (index >= curr.size) {
            index -= curr.size;
            if (curr.next != null) {
                curr = curr.next;
            } else {
                throw new IndexOutOfBoundsException();
            }
        }
        
        char[] currValues = curr.values;
        if (currValues[index] != 0) {
            return currValues[index];
        } else {
            throw new IndexOutOfBoundsException();
        }
    }
    
    public void insert(int index, char c) {
        if (head == null) {
            throw new IndexOutOfBoundsException();
        }
        Node curr = head;
        while (index >= curr.size) {
            index -= curr.size;
            if (curr.next != null) {
                curr = curr.next;
            } else {
                throw new IndexOutOfBoundsException();
            }
        }
        
        // IsFull
        int n = curr.values.length;
        if (curr.size == n) {
            Node newNode = new Node();
            newNode.values[0] = curr.values[n-1];
            newNode.size++;
            newNode.next = curr.next;
            curr.next = newNode;
        } else {
            curr.size++;
        }
        
        for (int i = n-1; i > index; i--) {
            curr.values[i] = curr.values[i-1];
        }
        curr.values[index] = c;        
    }
    
    //  { size 5 } -> [I, S, H, , O]
    //   v
    // { size 1 } -> [W, W, W, _, _]
    //   v
    
    // insert(1, W)
    
}