Finding the lowest unused unique id in a list

Question

Say there's a list. Each item in the list has a unique id.

List [5, 2, 4, 3, 1]

When I remove an item from this list, the unique id from the item goes with it.

List [5, 2, 3, 1]

Now say I want to add another item to the list, and give it the least lowest unique id.

What's the easiest way to get the lowest unique id when adding a new item to the list?

Here's the restriction though: I'd prefer it if I didn't reassign the unique id of another item when deleting an item.

I realise it would be easy to find the unique id if I reassigned unique id 5 to unique id 4 when I deleted 4. Then I could get the length of the list (5) and creating the new item with the unique id with that number.

So is there another way, that doesn't involve iterating through the entire list?

EDIT:

Language is java, but I suppose I'm looking for a generic algorithm.

Answer 1

Its equivalent to a search, just this time you search for a missing number. If your ID's are sorted integers, you can start going from bottom to top checking if the space between two ID's is 1. If you know how many items in the list and its sorted you can implement a binary search.

Answer 2

I don't think you can do this without iterating through the list.

When you say

'Now say I want to add another item to the list, and give it the least highest unique id. '

I assume you mean you want to assign the lowest available ID that has not been used elsewhere.

You can do this:

private int GetLowestFreeID(List list){
    for (int idx = 0; idx < list.Length; ++i){
        if ( list[idx] == idx ) continue;
        else return idx;
    }
}

this returns the lowest free index.

This assumes your list is sorted, and is in C# but you get the idea.

Answer 3

An easy fast way is to just put your deleted ids in a priority queue, and just pick the next id from there when you insert new ones (or use size() + 1 of the first list as id when the queue is empty). This would however require another list.

Answer 4

You could maintain a list of available ID's.

Declare a boolean array (pseudo code):

boolean register[3];
register[0] = false;
register[1] = false;
register[2] = false;

When you add an element, loop from the bottom of the register until a false value is found. Set the false value to true, assign that index as the unique identifier.

removeObject(index)
{
    register[index] = false;
}

getsetLowestIndex()
{
    for(i=0; i<register.size;i++)
    {
      if(register[i]==false)
      {
           register[i] = true;
           return i;
      }
    }

    // Array is full, increment register size
    register.size = register.size + 1;
    register[register.size] = true;
    return register.size;
}

When you remove an element, simply set the index to false.

You can optimise this for larger lists by having continuality markers so you don't need to loop the entire thing.

This would work best for your example where the indexes are in no particular order, so you skip the need to sort them first.

Answer 5

The data structure that would be used to do this is a Priority Binary Heap that only allow unique values.

Answer 6

How about keeping the list sorted. and than you can remove it from one end easily.