Создание циклически связанного списка в C #? - PullRequest
Новая
       60

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

23 голосов
/ 04 апреля 2009

Что было бы лучшим способом для создания циклически связанного списка в C #. Должен ли я получить его из коллекции LinkedList ? Я планирую создать простую адресную книгу с использованием этого связанного списка для хранения моих контактов (это будет плохая адресная книга, но мне все равно, потому что я буду единственным, кто будет ее использовать) В основном я просто хочу создать чрезвычайно связанный список, чтобы снова использовать его в других проектах.

Если вы не считаете, что Связанный список - это правильный путь, дайте мне знать, какой путь будет лучше.

Ответы [ 10 ]

78 голосов
/ 19 апреля 2010

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

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

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, и у вас будет все поведение круглого связанного списка. Вы все еще можете выполнять постоянное удаление и вставлять до и после всех узлов в списке и т.п. Если есть какой-то другой ключевой бит в круговом связанном списке, который мне не хватает, дайте мне знать.

6 голосов
/ 04 апреля 2009

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

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

4 голосов
/ 04 апреля 2009

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

4 голосов
/ 04 апреля 2009

Я не думаю, что круговой связанный список - это правильная структура данных для списка контактов. Достаточно простого списка <> или коллекции <>.

3 голосов
/ 26 февраля 2012 
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() { }
}
3 голосов
/ 04 апреля 2009

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

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

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

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

2 голосов
/ 19 мая 2016

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

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

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.

1 голос
/ 04 апреля 2009
0 голосов
/ 31 марта 2012 
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() при вращении, как в вашем примере.

0 голосов
/ 13 ноября 2011

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

...