CODEWITHSUNDEEP
javaalgorithm
user283559
user283559

Reputation: 83

How does this delete an element from an array?

I am using this book data structures and algorithms in java to learn about (you guessed it) - data structures and algorithms. This piece of code confuses me. I have tested it and it works but i don't see where in the code we specify to delete 55 exactly?

I see that we search for it in the array and move data elements up the index but don't see where we tell the compiler to delete 55.

    searchKey = 55; // delete item with key 55
    for(j=0; j<nElems; j++) // look for it
      if(arr[j] == searchKey)
        break;
    for(int k=j; k<nElems-1; k++) // move higher ones down
      arr[k] = arr[k+1];
    nElems--; // decrement size

Upvotes: 2

Views: 85

Answers (3)

dimo414
dimo414

Reputation: 48824

For the sake of example, suppose:

searchKey = 3
arr = {1,2,3,4,0,0,0}
nElems = 4

This means we have an array with seven slots, but the last three elements of the array are unused by the surrounding data structure.

The first for loop is simply looking for the index, j, that contains searchKey (searchValue would have been a better name, but alas). Once it finds the correct index, it breaks, leaving j set. In our example, j = 2 at the end of the first loop. Nothing has been changed yet, we've just found the index we want to clear.

The second for loop does the actual leg work by shifting everything after our found element down one index (and overwriting the found index in the process), so arr[2] is set to arr[3] and arr[3] is set to arr[4] and so on. At the end of the second loop we have

arr = {1,2,4,4,0,0,0}

Finally, we decrement nElems by one, so that there are now only three elements in the data structure. The last four elements in the array (4,0,0,0) are all now garbage that will get written over if more elements are added.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726629

To be precise, this code does not delete an array element; it overrides it.

Note how j is declared outside the first loop, and used in the second loop to initialize the value of k. The first loop walks j through the array, until j "points" to the element with the value of 55. When this happens, the code exits the loop through break, so when the second loop reads j, it still points to the location in the array where 55 is stored. Now the second loop copies elements from k+1-st location into k-th, "overriding" the value of 55 on the first iteration, and then moving the rest of the values in the consecutive iterations.

Consider this example:

Index:  0  1  2  3  4  5
Value: 30 40 55 60 70 80

After the first loop j is set to 2. Each iteration of the second loop changes the array as follows:

Index:        0  1  2  3  4  5
Iteration 0: 30 40 55 60 70 80
Iteration 1: 30 40 60 60 70 80
Iteration 2: 30 40 60 70 70 80
Iteration 3: 30 40 60 70 80 80

At this point nElems is decremented, making sure that the last element (i.e. 80) is disregarded if the program runs again.

Upvotes: 1

D.R.
D.R.

Reputation: 21194

It is overwritten by the first iteration of the second for loop.

Upvotes: 0

Related Questions