class ChunkedList<E> {
  
  private int size;
  private int maxChunkSize;
  public CNode<E> front;
  public CNode<E> backChunk;
  public CNode<E> back;
  
  /** Construct a ChunkedList using chunks of size no more than maxChunkSize
    * and no two adjacent chunks each of size less than maxChunkSize.
    * Precondition: maxChunkSize >= 1.
    * @param maxChunkSize the maximum chunk size
    * @throws IllegalArgumentException if maxChunkSize < 1 */
  public ChunkedList(int maxChunkSize) {
    if (maxChunkSize < 1) throw new IllegalArgumentException();
    this.maxChunkSize = maxChunkSize;
  }
  
  public int size() { return size; }
  
  public E get(int index) {
    if (index < 0 || index > size - 1) throw new IndexOutOfBoundsException();
    return locate(index).next.data;
  }
  
  public void add(int index, E data) {
    if (index < 0 || index > size) throw new IndexOutOfBoundsException();
    
    // Make node with data to add
    CNode<E> add = new CNode<E>(); add.data = data;
    
    // Empty: handle completely.
    if (front == null) {
      front = back = backChunk = add;
      add.chunkSize = 1;
      size++;
      return;
    }
    
    // Add as front of front chunk, or after node at index-1 in its chunk
    //
    CNode<E> chunk; // resulting chunk, for later adjustment
    if (index == 0) {
      // Doubly link
      add.next = front; // add.previous = null redundant
      front = add;
      add.next.previous = add;
      // Chunk
      add.chunkSize = add.next.chunkSize + 1;
      linkChunks(add, add.next.nextChunk);
      chunk = add;
    } else {
      CNode<E> location = locate(index-1);
      chunk = location.nextChunk;
      CNode<E> previous = location.next;
      // Doubly link
      add.previous = previous;
      add.next = previous.next;
      previous.next = add;
      if (add.next == null) back = add; else add.next.previous = add;
      // Chunk
      chunk.chunkSize++;
    }
    size++;
    
    // If added to maximum have size violation.
    // Move one to adjacent short, else make new 1-element chunk.
    if (chunk.chunkSize == maxChunkSize + 1) {
      if (chunk.nextChunk != null &&
          chunk.nextChunk.chunkSize < maxChunkSize) {
        takePrevious(chunk.nextChunk);
      } else if (chunk.previousChunk != null &&
                 chunk.previousChunk.chunkSize < maxChunkSize) {
        takeNext(chunk.previousChunk);
      } else {
        linkChunks(chunk.next, chunk.nextChunk);
        linkChunks(chunk, chunk.next);
        chunk.nextChunk.chunkSize = chunk.chunkSize - 1;
        chunk.chunkSize = 1;
      }
    }
  }
  
  public E remove(int index) {
    if (index < 0 || index > size - 1) throw new IndexOutOfBoundsException();
    
    // What we're removing.
    CNode<E> location = locate(index);
    CNode<E> chunk = location.nextChunk;
    CNode<E> node = location.next;
    
    // Remove from doubly-linked.
    if (node.previous == null) front = node.next;
    else node.previous.next = node.next;
    if (node.next == null) back = node.previous;
    else node.next.previous = node.previous;
    
    chunk.chunkSize--;
    size--;
    
    // If removing a chunk node, relink chunks around it:
    //   chunk.previousChunk - chunk.next - chunk.nextChunk
    // Special case: chunk.ChunkSize == 1, chunk.next == chunk.nextChunk
    if (chunk == node) {
      linkChunks(chunk.previousChunk, chunk.next);
      // if removed a whole chunk we're done.
      if (chunk.next == chunk.nextChunk) return node.data;
      linkChunks(chunk.next, chunk.nextChunk);
      chunk.next.chunkSize = chunk.chunkSize;
      chunk = chunk.next;
    }
    
    // Repair any previous or next adjacency size violation.
    //
    // Restores this chunk to maximum by taking from co-violator,
    //  so only need to fix one violation.
    if (chunk.chunkSize < maxChunkSize) { // actually == maxChunkSize - 1
      if (chunk.previousChunk != null &&
          chunk.previousChunk.chunkSize < maxChunkSize) {
        takePrevious(chunk);
      } else if (chunk.nextChunk != null &&
                 chunk.nextChunk.chunkSize < maxChunkSize) {
        takeNext(chunk);
      }
    }
    
    return node.data;
  }
  
  /* Return a new node with: .nextChunk the chunk containing that node
   *                         .next the node at the index. */
  public CNode<E> locate(int index) {
    CNode<E> result = new CNode<E>();
    CNode<E> node;
    
    // Find chunk, from front or backChunk based index vs size
    if (index <= size / 2) {
      node = front;
      while (index >= node.chunkSize) {
        index -= node.chunkSize;
        node = node.nextChunk;
      }
    } else {
      node = backChunk;
      index = size - 1 - index;
      while (index >= node.chunkSize) {
        index -= node.chunkSize;
        node = node.previousChunk;
      }
      index = node.chunkSize - 1 - index;
    }
    result.nextChunk = node;
    
    // Find inside chunk, from its front or back based on index vs size
    if (index <= node.chunkSize / 2) {
      for (int i = 0; i < index; ++i) node = node.next;
    } else {
      index = node.chunkSize - 1 - index;
      node = (node.nextChunk == null) ? back : node.nextChunk.previous;
      for (int i = 0; i < index; ++i) node = node.previous;
    }
    result.next = node;
    
    return result;  
  }
  
  /* Link chunks c1 and c2.
   * c1/c2 == null means front/backChunk variable. */
  private void linkChunks(CNode<E> c1, CNode<E> c2) {
    if (c1 != null) c1.nextChunk = c2; else front = c2;
    if (c2 != null) c2.previousChunk = c1; else backChunk = c1;
  }
  
  /* Move end of previous chunk to beginning of chunk. */
  private void takePrevious(CNode<E> chunk) {
    // Makes: chunk.previousChunk - chunk.previous - chunk.nextChunk
    // Special case: chunk.previousChunk == chunk.previous
    if (chunk.previousChunk != chunk.previous) {
      linkChunks(chunk.previousChunk, chunk.previous);
      chunk.previousChunk.chunkSize--;
    }
    linkChunks(chunk.previous, chunk.nextChunk);
    chunk.previous.chunkSize = chunk.chunkSize + 1;
  }
  
  /* Move beginning of next chunk to end of chunk. */
  private void takeNext(CNode<E> chunk) {
    // Makes: chunk - chunk.nextChunk.next - chunk.nextChunk.nextChunk
    // Special case: chunk.nextChunk.next == chunk.nextChunk.nextChunk
    if (chunk.nextChunk.next != chunk.nextChunk.nextChunk) {
      linkChunks(chunk.nextChunk.next, chunk.nextChunk.nextChunk);
      chunk.nextChunk.next.chunkSize = chunk.nextChunk.chunkSize - 1;
    }
    linkChunks(chunk, chunk.nextChunk.next);
    chunk.chunkSize++;
  }
  
}