Создание циклически связанного списка в С#?

Ответ 1

Поскольку большинство из этих ответов фактически не затрагивают суть вопроса, просто намерение, возможно, это поможет:

Насколько я могу судить, единственная разница между Linked List и Circular Linked List - это поведение итераторов при достижении конца или начала списка. Очень простой способ поддерживать поведение Circular Linked List состоит в том, чтобы написать метод расширения для LinkedListNode, который возвращает следующий node в списке или первом, если такой node не существует, и аналогично для получения предыдущего node или последний, если такой node не существует. Следующий код должен выполнить это, хотя я его не тестировал:

static class CircularLinkedList {
    public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
    {
        return current.Next ?? current.List.First;
    }

    public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current)
    {
        return current.Previous ?? current.List.Last;
    }
}

Теперь вы можете просто вызвать myNode.NextOrFirst() вместо myNode.Next, и у вас будет все поведение кругового связанного списка. Вы все равно можете выполнять постоянное удаление времени и вставлять до и после всех узлов в списке и т.п. Если у вас есть еще один ключевой бит кругового связанного списка, я не знаю, дайте мне знать.

Ответ 2

Вероятно, будет плохой вывод из класса BCL LinkedList. Этот класс предназначен для некруглого списка. Попытка сделать ее круговой вызовет только проблемы.

Вам, вероятно, гораздо лучше писать свои собственные.

Ответ 3

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

Ответ 4

У вас есть специальное требование использовать циклически связанный список (например, домашнее задание)? Если нет, я бы предложил использовать простой класс List<T> для хранения ваших контактов.

Ответ 5

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

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

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

Цель кругового буфера - скорость, и массив просто не может быть избит для скорости в контексте кругового буфера. Даже если вы сохраните указатель на свой последний элемент связанного списка, массив будет по-прежнему более эффективным. Списки имеют возможности динамического изменения размера (служебные данные), которые не нужны для циклических буферов. Сказав это, я думаю, что круговой буфер, вероятно, не является подходящей структурой для приложения (список контактов), который вы упомянули.

Ответ 6

class CircularArray<T> : IEnumerator<T>
{
    private readonly T[] array;
    private int index = -1;
    public T Current { get; private set; }

    public CircularArray(T[] array)
    {
        Current = default(T);
        this.array = array;
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }

    public bool MoveNext()
    {
        if (++index >= array.Length)
            index = 0;
        Current = array[index];
        return true;
    }

    public void Reset()
    {
        index = -1;
    }

    public void Dispose() { }
}

Ответ 7

Решение на основе модуля.

Если циклический буфер реализован как необработанный массив (или любой другой вид коллекции для чего он имеет значение)

T[] array;

и мы сохраняем в int current_index индекс текущего элемента, мы можем циклически перемещать вверх и вниз по буфере следующим образом:

T NextOrFirst()
{
    return array[(current_index + 1) % array.Length];
}

T PreviousOrLast()
{
    return array[(current_index + array.Length - 1) % array.Length];
}

Такой же подход можно использовать с любой коллекцией привязки XAML.

Ответ 8

Как насчет этого круговой список на основе CLIST.

Ответ 9

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

Ответ 10

class Program
{
    static void Main(string[] args)
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };

        IEnumerable<int> circularNumbers = numbers.AsCircular();

        IEnumerable<int> firstFourNumbers = circularNumbers.Take(4); // 1 2 3 4
        IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers
            .Skip(4).Take(7); // 4 5 6 7 1 2 3 
    }
}

public static class CircularEnumerable
{
    public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source)
    {
        if (source == null)
            yield break; // be a gentleman

        IEnumerator<T> enumerator = source.GetEnumerator();

        iterateAllAndBackToStart:
        while (enumerator.MoveNext()) 
            yield return enumerator.Current;

        enumerator.Reset();
        if(!enumerator.MoveNext())
            yield break;
        else
            yield return enumerator.Current;
goto iterateAllAndBackToStart;
    }
}

Если вы хотите пойти дальше, сделайте CircularList и удерживайте того же перечислителя, чтобы пропустить Skip() при вращении, как в вашем примере.