Implement Linked List

Implement a singly linked list of integers with the following operations. Build it from nodes yourself; do not store the values in an array.

Implement the LinkedList class:

• LinkedList() creates an empty list.
• addFirst(val) inserts val at the front.
• addLast(val) inserts val at the back.
• removeFirst() removes the first element and returns its value, or -1 if the list is empty.
• getFirst() returns the first value, or -1 if the list is empty.
• getLast() returns the last value, or -1 if the list is empty.
• size() returns the number of elements.
• clear() removes every element.
• toArray() returns the values from first to last as an array.

All stored values are non-negative, so -1 is never a real value. addFirst, addLast, removeFirst, getFirst, getLast and size should run in O(1).