Creazione di un elenco collegato in modo circolare in C#?

Question

Quale sarebbe il modo migliore per creare un elenco circolare collegato in C#. Dovrei derivarlo dalla collezione T> LinkedList <? Sto pensando di creare una semplice rubrica usando questa lista collegata per memorizzare i miei contatti (sarà una rubrica di successo, ma non mi interessa perché sarò l'unica ad usarla). Voglio principalmente creare l'elenco collegato in modo cruciale in modo da poterlo riutilizzare in altri progetti.

Se non pensi che l'Elenco collegato sia il modo giusto per andare fammi sapere quale sarebbe la soluzione migliore.

Answer 1

Come la maggior parte di queste risposte non sono stati veramente alla sostanza della questione, solo l'intenzione, forse questo aiuterà:

Per quanto posso dire l'unica differenza tra una lista concatenata e una circolare Elenco collegato è il comportamento degli iteratori al raggiungimento della fine o dell'inizio di un elenco. Un modo molto semplice per supportare il comportamento di un elenco collegato circolare è scrivere un metodo di estensione per un oggetto LinkedList che restituisce il nodo successivo nell'elenco o il primo se questo non esiste, e allo stesso modo per recuperare il nodo precedente o l'ultimo uno se non esiste un tale nodo. Il seguente codice dovrebbe realizzare che, anche se non ho provato:

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

Ora si può chiamare myNode.NextOrFirst() al posto di myNode.Avanti e avrai tutto il comportamento di un elenco circolare circolare. È comunque possibile eseguire rimozioni a tempo costante e inserire prima e dopo tutti i nodi nell'elenco e simili. Se c'è qualche altro elemento chiave di una lista circolare circolare che mi manca, fammi sapere.

Answer 2

Non penso che un elenco circolare collegato sia la struttura dati corretta per un elenco di contatti. Una semplice lista <> o collezione <> dovrebbe essere sufficiente.

Answer 3

Probabilmente sarebbe una cattiva idea derivare dalla classe BCL LinkedList. Quella classe è progettata per essere una lista non circolare. Cercare di renderlo circolare ti causerà solo problemi.

Probabilmente stai molto meglio scrivendo il tuo.

Answer 4

Hai un requisito specifico per utilizzare un elenco collegato in modo circolare (ad esempio i compiti)? In caso contrario, suggerirei di utilizzare la semplice classe List<T> per memorizzare i contatti.

Answer 5

Che ne dici di questo CList based circular list.

Answer 6

Gli elenchi collegati in modo circolare sono spesso implementati utilizzando matrici che li rendono molto veloci e, per loro natura, non richiedono il ridimensionamento dinamico. Hai solo bisogno di un rapido controllo degli indici di lettura e di scrittura per vedere se cadono dalla fine e, in tal caso, resettarlo a zero (o uno, qualunque sia).

Tuttavia, vengono generalmente utilizzati per cose come i buffer di input, dove i dati non hanno un valore reale una volta letti. Gli elenchi dei contatti hanno un valore duraturo e nuovi contatti sovrascriveranno i contatti più vecchi una volta che la lista si riempie, il che potrebbe andar bene a meno che non sovrascrivi tua nonna che ti lascia un mucchio di soldi nel suo testamento.

---

Non penso che un elenco collegato sia il modo più efficiente per ottenere un buffer circolare (la domanda originale).

Lo scopo di un buffer circolare è la velocità e un array semplicemente non può essere battuto per la velocità nel contesto di un buffer circolare. Anche se mantieni un puntatore al tuo ultimo elemento di elenco collegato, una matrice sarà comunque più efficiente. Le liste hanno capacità di ridimensionamento dinamico (overhead) non necessarie per i buffer circolari. Detto questo, penso che un buffer circolare non sia probabilmente la struttura giusta per l'applicazione (elenco di contatti) che menzioni.

Answer 7

Penso che la struttura dati più corretta per questo problema sia una lista circolare doppiamente collegata. Con questa struttura dati si può liberamente su e giù attraverso la lista dei contatti

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

Se si vuole andare oltre, fare una CircularList e tenere premuto lo stesso enumeratore di saltare la Skip() durante la rotazione come nel campione.

Answer 10

Una soluzione basata su modulo.

Se il buffer circolare è implementato come un array grezzo (o qualsiasi altro tipo di raccolta per quello che conta)

T[] array; 

e memorizzare in int current_index l'indice dell'elemento corrente, si può ciclo e giù il buffer come segue:

Lo stesso approccio può essere utilizzato con qualsiasi raccolta di binding XAML.