Why last node remove operation in array have O(n)?

Why removing the last node in the array is O(n) since we don’t traverse the array while removing the last node and there is no left shit.

I’m a beginner myself so take this with a grain of salt but I’m assuming that removing the last element in an array without knowing it’s index (i.e not knowing how many elements are in said array) then the time complexity would be O(n). If we know the index of course it’s O(1).

As for removing the last node of a linked list I think that’s incorrect, since a linked list always holds a reference to it’s last node then the time complexity to remove that node at the end should be O(1).

Hopefully someone more experienced can chime in to verify.

Mosh made a mistake here when transferring “deletion is O(n)” to the three cases “beginning”, “middle” and “end”. Deletion in an array is generally O(n) but the edge case of deleting the last item is O(1).

True for doubly linked lists but not for singly liked lists. With a singly linked list you have to traverse the list from the beginning to get the reference of the second last item so you can update the reference to the last node.

2 Likes

Thanks SAM that slipped my mind. You do need the 2nd to last node, which of course requires you to traverse the list.

Thanks for raising this. I was wondering myself as I wrote it as :

public void removeAt(int index) throws Exception {
if (index + 1 == size) {
this.remove();
}

}

public void remove() {
this.items[size] = 0;
size–;
}

So no shifting and O(1)