Création d'une liste chaînée en C#?

Question

Quel serait le meilleur moyen de créer une liste circulaire en C#. Dois-je le dériver de la collection LinkedList < T>? Je prévois de créer un simple carnet d'adresses en utilisant cette liste liée pour stocker mes contacts (ça va être un carnet d'adresses, mais je m'en fous parce que je serai le seul à l'utiliser). Je veux principalement créer la liste de manière cruciale afin de pouvoir l'utiliser à nouveau dans d'autres projets.

Si vous ne pensez pas que la liste liée est la bonne façon de procéder, faites-moi savoir quelle serait la meilleure solution.

Answer 1

Comme la plupart de ces réponses ne reçoivent pas vraiment au fond de la question, mais simplement l'intention, peut-être cela vous aidera:

Pour autant que je peux dire la seule différence entre une liste, et une circulaire Linked List est le comportement des itérateurs à la fin ou au début d'une liste. Un moyen très simple de prendre en charge le comportement d'une liste circulaire est d'écrire une méthode d'extension pour un LinkedListNode qui renvoie le nœud suivant dans la liste ou le premier si aucun nœud n'existe, et de même pour récupérer le nœud précédent ou le dernier un si ce noeud n'existe pas. Le code suivant doit accomplir, même si je ne l'ai pas testé:

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

Maintenant, vous pouvez simplement appeler myNode.NextOrFirst() au lieu de myNode.Ensuite, vous aurez tout le comportement d'une liste circulaire liée. Vous pouvez toujours effectuer des suppressions de temps constant et insérer avant et après tous les nœuds de la liste et autres. S'il y a un autre élément clé d'une liste chaînée circulaire qui me manque, faites le moi savoir.

Answer 2

Je ne pense pas qu'une liste chaînée circulaire est la bonne structure de données pour une liste de contacts. Une simple liste <> ou Collection > devrait suffire.

Answer 3

Ce serait probablement une mauvaise idée de dériver de la classe BCL LinkedList. Cette classe est conçue pour être une liste non-circulaire. Essayer de le rendre circulaire ne vous causera que des problèmes.

Vous êtes probablement beaucoup mieux d'écrire les vôtres.

Answer 4

Avez-vous une exigence spécifique d'utiliser une liste liée circulairement (c'est-à-dire les devoirs)? Sinon, je suggère d'utiliser la classe List<T> pour stocker vos contacts.

Answer 5

Que diriez-vous de ce CList based circular list.

Answer 6

Les listes à liens circulaires sont souvent implémentées en utilisant des tableaux qui les rendent très rapides et qui, de par leur nature, ne requièrent pas de redimensionnement dynamique. Vous avez juste besoin d'un contrôle rapide sur les index de lecture et d'écriture pour voir s'ils sont tombés de la fin et si oui, réinitialisez-le à zéro (ou un, peu importe). Cependant, ils sont généralement utilisés pour des choses comme les tampons d'entrée, où les données n'ont pas de valeur réelle une fois lues. Les listes de contacts ont une valeur durable et de nouveaux contacts écraseront les anciens contacts une fois que la liste se remplira, ce qui pourrait être acceptable à moins d'écraser votre grand-mère qui vous laisse un tas d'argent dans son testament.

---

Je ne pense pas qu'une liste chaînée soit la manière la plus efficace d'opter pour un tampon circulaire (la question d'origine).

Le but d'un tampon circulaire est la vitesse et un tableau ne peut tout simplement pas être battu pour la vitesse dans le contexte d'un tampon circulaire. Même si vous gardez un pointeur sur votre dernier élément de liste lié, un tableau sera toujours plus efficace. Les listes ont des capacités de redimensionnement dynamique (overhead) inutiles pour les buffers circulaires. Cela dit, je pense qu'un tampon circulaire n'est probablement pas la bonne structure pour l'application (liste de contacts) que vous mentionnez.

Answer 7

Je pense que la structure de données la plus correcte pour ce problème est une liste circulaire à double liaison. Avec cette structure de données, vous pouvez librement vers le haut et vers le bas à travers la liste des contacts

Answer 8

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() { } 
} 

Answer 9

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

Si vous voulez aller plus loin, faire un CircularList et maintenir la même recenseur pour sauter le Skip() lors de la rotation comme dans votre échantillon.

Answer 10

Une solution à base de module.

Si la mémoire tampon circulaire est utilisé comme une matrice brute (ou tout autre type de collection pour ce qu'il importe)

T[] array; 

et nous stockons dans int current_index l'indice de l'élément en cours, nous le cycle peut et descendre le tampon comme suit:

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

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

La même approche peut être utilisée avec n'importe quelle collection de liaison XAML.