Как лучше всего вставить что-нибудь в середину списка?
Это, наверное, простой вопрос. Допустим, у меня есть небольшой список из 20-50 записей или около того. Что-то вроде:
class Item
{
int ItemNumber;
int OrderNumber;
string Name;
}
stored in something like
List<Item>
Он хранится либо в общем списке, либо в массиве, где OrderNumber идет от 1, 2, 3, 4, .... 50. Чтобы упростить задачу, предположим, что OrderNumber уже отсортирован в List с помощью QuickSort в другом месте (если это не усложняет ситуацию).
Допустим, я хочу переместить Item.OrderNumber = 30 на место, занимаемое Item.OrderNumber = 20 или чем-то в этом роде. Когда я это сделаю, все, что выше 20, теперь нужно сдвинуть, так что старые 20 теперь 21, 21 теперь 22 и т. д., Пока я не дойду до 30. Также нужно идти другим путем, поэтому, когда Item.OrderNumber = 30 перемещается в Item.OrderNumber = 34, и все должно быть сдвинуто вниз.
Я думаю о том, чтобы пролистать список несколько раз, но надеюсь, что есть лучший способ сделать это. Несмотря на то, что размер списка невелик, для разных вещей нужно много делать.
Обновлено: Просто чтобы вы знали. В конечном итоге результаты должны быть сохранены в базе данных в транзакциях определенного типа.
Ответы 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;
}
}
если вы используете список с двойной связью, вы можете очень недорого вставить OrderNumber = 30 в место после 19 или раньше 20. Затем перейдите к OrderNumber, который меньше 30, и увеличьте каждый порядок на 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 любой из других записей, как предлагается в Ответ Роберта Вагнера.
Это просто обычный двоичный поиск по списку, поддерживаемому массивом.
Просто отсортируйте после того, как заполните список, и заполните, приклеивая вещи в конце. Если вам нужно постоянно сортировать, делайте то, что говорит Скит.
Если я правильно понимаю, вы пытаетесь сохранить OrderNumber внутри объекта (по какой-либо причине), но вам нужно иметь возможность добавить новый объект в список и заставить все другие объекты настроить свой OrderNumber, чтобы новый подходил. Также фактический порядок пунктов в списке не имеет (обязательно) значения.
Это можно сделать, заключив список в оболочку и выполнив свои собственные операции (функции перемещения / вставки / удаления, которые выполняли следующие действия:
Вставлять Прокрутите все элементы и увеличьте номер заказа на единицу, где номер заказа> = номер заказа нового элемента. Добавить товар в список
Удалять Удалить предмет Прокрутите все элементы и уменьшите номер заказа на единицу, где номер заказа> номер заказа удаленного элемента.
Двигаться Удалить предмет Перенумеровать элемент Вставьте элемент
является ли List <T> .BinarySearch интерфейсом к имплицитному списку пропуска?