An efficient way to delete an item from a dynamic list

by Dr. Osama M. Khaled last modified 2022-07-19T05:23:42+01:00
It is sometimes tricky working with linked lists if you are searching for an item to delete it.

So, if you are searching from the first index to the last position in the linked list and while you are deleting items, the index position of items change and if you are looping on the initial size, you may find yourself skipping some items since their position changes after deletion but you still incrementing the index.

Consider this simple algorithm for a list = ["2", "3", "1", "1","6"]

for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("1"))
list.remove(i);
}

This algorithm can find the first "1", but will not be able to find the second "1" as its position will change after removal, but i still increments.

you could fix the above algorithm by keeping i variable aligned with the current item position by reducing i without exceeding 0, but it is still not that efficient.  It is an extra step taking more time.

A better way to do the search is to start from the last element and even if you remove an element, your index will still keep the same position as the item in the list

for (int i = list.size()-1; i >=0; i--) {
if (list.get(i).equals("1"))
list.remove(i);
}