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

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

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

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

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

static class CircularLinkedList { public static LinkedListNode NextOrFirst(this LinkedListNode current) { return current.Next ?? current.List.First; } public static LinkedListNode PreviousOrLast(this LinkedListNode current) { return current.Previous ?? current.List.Last; } } 

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

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

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

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

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

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

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


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

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

 class CircularArray : IEnumerator { 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() { } } 

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

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

 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.

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

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

 class Program { static void Main(string[] args) { int[] numbers = { 1, 2, 3, 4, 5, 6, 7 }; IEnumerable circularNumbers = numbers.AsCircular(); IEnumerable firstFourNumbers = circularNumbers.Take(4); // 1 2 3 4 IEnumerable nextSevenNumbersfromfourth = circularNumbers .Skip(4).Take(7); // 4 5 6 7 1 2 3 } } public static class CircularEnumerable { public static IEnumerable AsCircular(this IEnumerable source) { if (source == null) yield break; // be a gentleman IEnumerator 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() при вращении, как в вашем примере.

Давайте будем гением компьютера.