I'm trying to figure out the running time of the code below, both if the list was an arraylist and if it was a linkedlist. I appreciate any advice!
Array: I thought it would be O(n) for remove operation, and N/2 for the loop, so O(n^2)
LinkedList: Only references change, so constant time for the remove and N/2 for the loop, so O(n)
int halfSize = lst.size() / 2;
for (int i = 0; i < halfSize; i++){
lst.remove(0);
}
ArrayList: evaluation correct, due to underlying array copy
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
LinkedList: evaluation correct, node removal @zero index is constant
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With