Выбор правильной структуры данных для этой проблемы: круговой связанный список, список, массив или что-то еще

Question

Требование, которое у меня есть, для каждого типа T, у меня есть несколько элементов (от 1 до 30+), и сначала мне нужен случайный предмет, затем мне нужен следующий, и когда я добираюсь до последнего предмета, он должен вернуть первый и т. д.

Так сказать, T - это Icon, а коллекция - это Изображения (экземпляр).

Я хочу иметь:

// program start:

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

// user clicks next icon:

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

Для меня круговой связанный список имеет смысл, за исключением того, что я должен сделать O (n), где n - случайный индекс.

Я хочу иметь самое чистое и лучшее исполнение, поэтому вопрос.

Answer 1

Другим возможным решением является создание связанного списка с базовой структурой данных, являющейся массивом. Таким образом, вы можете индексировать в O (1), сохраняя при этом «округлость»

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];
    }
}

Answer 2

Я хотел бы рассмотреть возможность использования собственного класса, содержащего массив или список внутри, и создание собственного перечислителя, который начинается с любого индекса и перечисляет вокруг цикла.

Основная причина, по которой я думаю, что это лучше, чем LinkedList, имеет отношение к этой строке:

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

Гораздо проще и эффективнее получить случайный элемент из индексируемой коллекции, чем связанный список .... И с 30 элементами перечисление будет быстрым в любом случае.

Для обработки итерации по кругу все, что вам нужно, это что-то вроде этого:

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];
    }
}

Answer 3

Зачем вообще использовать связанный список? Используйте массив и сохраните индекс текущего элемента. Когда вызывается функция для получения следующего элемента, увеличивайте индекс. Если индекс больше, чем количество элементов, установите индекс на ноль.

Answer 4

• Круглый список хорош
• Поскольку у вас есть около 30 элементов (скажем, не 3000), вы можете рассмотреть индексированную таблицу, а не связанный список
  • Это будетработайте сразу, если ваши элементы не будут добавляться и удаляться
• Если вы динамически вставляете и удаляете элементы, вы все равно можете написать некоторый код для обработки этого (например, небольшой список)
• Если все это работает для вас, все, что остается, является случайным числом от 1 до N.

---

• Если количество элементов в списке небольшое, это будетизбыточное уничтожение для реализации выровненного списка
• Однако, если вы решите это сделать, вы все равно можете позволить себе первый обход по списку до случайно выбранной начальной точки