Какой хороший способ вставить что-то в середину списка?

Question

Это, наверное, простой вопрос. Допустим, у меня есть небольшой список с примерно 20-50 записями или около того. Что-то вроде:

class Item
{
   int ItemNumber;
   int OrderNumber;
   string Name;
}

stored in something like
List<Item>

Это хранится либо в общем списке, либо в массиве, где OrderNumber идет от 1, 2,3,4, .... 50. Чтобы упростить задачу, давайте предположим, что OrderNumber уже отсортирован в списке с помощью QuickSort где-то еще (если это не усложняет ситуацию).

Допустим, я хочу переместить Item.OrderNumber = 30 в место, занятое Item.OrderNumber = 20 или что-то в этом роде. Когда я делаю это, все, что выше 20, теперь нужно сместить так, чтобы старое 20 теперь было 21, 21 теперь 22, и т. Д., Пока я не достигну 30. Это также должно пойти другим путем, когда Item.OrderNumber = 30 перемещается в Item.OrderNumber = 34 и все должно быть смещено вниз.

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

РЕДАКТИРОВАТЬ: Просто чтобы вы знали. Результаты в конечном итоге должны быть сохранены в базе данных, в некотором типе транзакции.

Answer 1

Должно ли это быть List<T>? Если нет, вы можете рассмотреть возможность использования SortedList<TKey, TValue> или SortedDictionary<TKey, TValue>. Затем вы можете использовать OrderNumber в качестве ключа и просто позволить коллекции выполнить свою работу.

В качестве альтернативы, для List<T> вы можете использовать List<T>.BinarySearch с соответствующим IComparer<T>, который сравнивается по номеру заказа - вы получите:

int position = list.BinarySearch(newOrder, orderComparer);
list.Insert(position >= 0 ? position : ~position, newOrder);

Вы можете использовать один и тот же экземпляр IComparer<T> во всем коде, так как он не будет содержать состояния.

РЕДАКТИРОВАТЬ: Это решение не изменяет OrderNumber любой из других записей, как предлагается в ответ Роберта Вагнера .

Answer 2

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

Это можно сделать, обернув список и реализовав свои собственные операции (функции перемещения / вставки / удаления, которые выполняли следующие действия:

Вставить Переберите все элементы и увеличьте номер заказа на единицу, где номер заказа> = номер заказа нового элемента Добавить товар в список

Удалить Удалить предмет Переберите все элементы и уменьшите номер заказа на единицу, где номер заказа> номер заказа удаленного элемента

Move Удалить предмет Перенумеровать предмет Вставьте элемент

Answer 3

Просто сортируйте после заполнения списка и заполняйте, вставляя вещи в конец. Если вам нужно все время сортировать, делайте то, что говорит Скит.

Answer 4

если вы используете двойной связанный список, вы можете сделать очень недорогую вставку OrderNumber = 30 в местоположение после 19 или до 20. Затем выполните итерацию до OrderNumber, который меньше 30, и увеличьте каждый заказ на 1. И выполните обратное перемещение элемента выше в списке.

Answer 5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Class1
{                     
    static void Main()
    {
        var beatles = new LinkedList<string>();

        beatles.AddFirst("John");                        
        LinkedListNode<string> nextBeatles = beatles.AddAfter(beatles.First, "Paul");
        nextBeatles = beatles.AddAfter(nextBeatles, "George");
        beatles.AddAfter(nextBeatles, "Ringo");


        LinkedListNode<string> paulsNode = beatles.NodeAt(1); // middle's index
        LinkedListNode<string> recentHindrance = beatles.AddBefore(paulsNode, "Yoko");
        recentHindrance = beatles.AddBefore(recentHindrance, "Aunt Mimi");
        beatles.AddBefore(recentHindrance, "Father Jim");


        Console.WriteLine("{0}", string.Join("\n", beatles.ToArray()));

        Console.ReadLine();                       
    }
}

public static class Helper
{
    public static LinkedListNode<T> NodeAt<T>(this LinkedList<T> l, int index)
    {
        LinkedListNode<T> x = l.First;

        while ((index--) > 0) x = x.Next;

        return x;
    }
}