CODEWITHSUNDEEP
c#.netperformancedata-structures
Joan Venge
Joan Venge

Reputation: 331250

Choosing the right data structure for this problem: circular linked list, list, array or something else

The requirement I have is for every type T, I have a number of elements (between 1-30+) and at first I need random item, then I need the next, and when I reach the last item, it should return the first one and so on.

So say T is Icon, and the collection is Images (instance).

I want to have:

// program start:

Icon icon = RandomIcon(); // say 5th one for this case

// user clicks next icon:

icon = current++; (6, 7, 8, 1, 2, ...)

To me a circular linked list makes sense, except that I have to do O(n) where n is the random index.

I want to have the cleanest, best implemenation, hence the question.

Upvotes: 1

Views: 1277

Answers (4)

Reed Copsey
Reed Copsey

Reputation: 564631

I would consider using a custom class containing an array or a List<T> internally, and making a custom enumerator that starts at any index, and enumerates around the loop.

The main reason I think this would be better than a LinkedList has to do with this line:

Icon icon = RandomIcon(); // say 5th one for this case

It is much easier and more performant to get a random item from an indexible collection than a linked list.... And with 30 elements, enumerating will be quick in either case.

To handle the iteration in a circle, all you need is something like this:

class CircularlyEnumerableList<T>
{
    private List<T> list;

    // Implement whatever you need for list...

    IEnumerable<T> EnumerateFromElement(int index)
    {
        for (int i=index; i<list.Count; ++i)
             yield return list[i];

        for (int i=0; i<index; ++i)
             yield return list[i];
    }
}

Upvotes: 2

Gavin Miller
Gavin Miller

Reputation: 43845

Another possible solution is to create a linked list with the underlying data structure being an array. This way you can index in at O(1) while maintaining your "circularity"

public class myLL
{
    private T[] items;
    private int i;
    private int max_size;

    public T GetCurrent() {
        return items[i];
    }

    public T GetNext() {
        i = i++ % max_size;
        return items[i];
    }
}

Upvotes: 5

Eyal
Eyal

Reputation: 5848

Why use a linked list at all? Use an array and store the index of the current item. When a function is called to get the next item, increment the index. If the index is greater than the number of elements, set the index to zero.

Upvotes: 1

nik
nik

Reputation: 13460

  • Circular list is good
  • Since you have around 30 elements (and not like 3000, say), you could consider an indexed table rather than a linked list
    • This will work straight away if your elements do not keep getting added and removed
  • If you have dynamically inserted and deleted elements, you could still write some code to handle that (coz, small list)
  • If all this works for you, all that remains is a random between 1-N.
  • If your item count per list is small, it would be an over kill to implement a lined list
  • However, if you choose to do so, you could still afford a first traversal down the list to the randomly picked start point

Upvotes: 1

Related Questions