c# - resueltos - listas enlazadas en c insertar elementos

¿Creando una lista enlazada circularmente en C#?

Question

¿Cuál sería la mejor manera de crear una lista enlazada circularmente en C #? ¿Debería derivarlo de la colección LinkedList <T>? Estoy planeando crear una libreta de direcciones simple usando esta Lista Vinculada para almacenar mis contactos (será una libreta de direcciones muy mala, pero no me importa porque seré la única en usarla). Principalmente solo quiero crear la lista de enlaces cruciales para poder usarla de nuevo en otros proyectos.

Si no cree que la Lista Vinculada es la manera correcta de hacerlo, avíseme de qué manera sería mejor.

Answer 1

¿Qué tal esta lista circular basada en CList .

Answer 2

¿Tiene un requisito específico para usar una lista enlazada circularmente (es decir, tarea)? Si no es así, sugeriría usar la clase simple List<T> para almacenar sus contactos.

Answer 3

Como la mayoría de estas respuestas no llegan a la esencia de la pregunta, simplemente la intención, quizás esto ayude:

Hasta donde puedo decir, la única diferencia entre una Lista Vinculada y una Lista Circular Vinculada es el comportamiento de los iteradores al llegar al final o al principio de una lista. Una forma muy fácil de admitir el comportamiento de una lista enlazada circular es escribir un método de extensión para un LinkedListNode que devuelve el siguiente nodo en la lista o el primero si no existe dicho nodo, y de manera similar para recuperar el nodo anterior o el último uno si no existe tal nodo. El siguiente código debería lograr eso, aunque no lo he probado:

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

Ahora solo puede llamar a myNode.NextOrFirst () en lugar de myNode.Next y tendrá todo el comportamiento de una lista enlazada circular. Aún puede realizar eliminaciones de tiempo constantes e insertar antes y después de todos los nodos en la lista y similares. Si faltaba algún otro elemento clave de una lista enlazada circular, avíseme.

Answer 4

Creo que la estructura de datos más correcta para este problema es una lista circular doblemente enlazada. Con esta estructura de datos puedes subir y bajar libremente a través de la lista de contactos

Answer 5

Las listas enlazadas circularmente a menudo se implementan utilizando matrices que las hacen muy rápidas y, por su naturaleza, no requieren un cambio de tamaño dinámico. Solo necesita una comprobación rápida de los índices de lectura y escritura para ver si se cayeron del final y, de ser así, restablézcalos a cero (o uno, lo que sea).

Sin embargo, generalmente se usan para cosas como buffers de entrada, donde los datos no tienen un valor real una vez leídos. Las listas de contactos tienen un valor duradero y los nuevos contactos sobrescribirán los contactos más antiguos una vez que la lista se llene, lo que podría estar bien a menos que usted sobrescriba a su abuela, que le está dejando un montón de efectivo en su testamento.

No creo que una lista enlazada sea la forma más eficiente de obtener un búfer circular (la pregunta original).

El propósito de un búfer circular es la velocidad y una matriz simplemente no puede ser superada por la velocidad en el contexto de un búfer circular. Incluso si mantiene un puntero al último elemento de la lista enlazada a la que ha accedido, una matriz seguirá siendo más eficiente. Las listas tienen capacidades de cambio de tamaño dinámico (sobrecarga) que no son necesarias para los búferes circulares. Dicho esto, creo que un búfer circular probablemente no sea la estructura correcta para la aplicación (lista de contactos) que menciona.

Answer 6

No creo que una lista enlazada circular sea la estructura de datos correcta para una lista de contactos. Una simple Lista <> o Colección <> debería ser suficiente.

Answer 7

Probablemente sería una mala idea derivar de la clase BCL LinkedList. Esa clase está diseñada para ser una lista no circular. Tratar de hacerlo circular solo te causará problemas.

Probablemente estés mucho mejor escribiendo el tuyo.

Answer 8

Una solución basada en módulo.

Si el búfer circular se implementa como una matriz en bruto (o cualquier otro tipo de colección por lo que importa)

T[] array;

y almacenamos en int current_index el índice del elemento actual, podemos subir y bajar el búfer de la siguiente manera:

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

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

El mismo enfoque se puede utilizar con cualquier colección de enlaces XAML.

Answer 9

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

Si desea ir más lejos, haga una CircularList y mantenga presionado el mismo enumerador para omitir el Skip() cuando gire como en su muestra.