What's a good way to insert something in the middle of a list?

Question

This is probably a simple question. Let's say I have a small list with around 20-50 entries or so. Something like:

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

stored in something like
List<Item>

This is stored either in a generic list or array in where the OrderNumber goes from 1, 2,3,4,....50. To makes things easier, let's assume that the OrderNumber has already be sorted in the List by QuickSort somewhere else (unless that makes things more complicated).

Let's say I want to move Item.OrderNumber = 30 into the spot taken by Item.OrderNumber = 20 or something like that. When I do that, everything above 20 now needs to be shifted so that the old 20 is now 21, 21 is now 22, etc until I makes it to 30. It also needs to go the other way so when Item.OrderNumber = 30 is moved to Item.OrderNumber = 34 and everything has to be shifted downwards.

I'm thinking about bubbling the list a few times, but I'm hoping there's a better way to do this. Although the list size is small, this needs to done a lot for various different things.

EDIT: Just to let you know. The results eventually have to be stored in a database, in some type of transaction.

Answer 1

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

Answer 2

if you use a double linked list, you can do a very inexpensive insertion of OrderNumber = 30 into the location after 19 or before 20. Then iterate to the OrderNumber that is less than 30 and increase each order by 1. And do the reverse for moving an item higher in the list.

Answer 3

Does it have to be a List<T>? If not, you might consider using a SortedList<TKey, TValue> or a SortedDictionary<TKey, TValue>. You could then use the OrderNumber as the key, and just let the collection do the work.

Alterantively, for List<T> you can use List<T>.BinarySearch with an appropriate IComparer<T> which compares by order number - you'd have:

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

You can use the same IComparer<T> instance throughout your code, as it would be stateless.

EDIT: This solution doesn't change the OrderNumber of any of the other entries, as suggested in Robert Wagner's answer.

Answer 4

Just sort after you populate the list, and populate by sticking things on the end. If you need it sorted at all times, do what Skeet says.

Answer 5

If I understand correctly, you are trying to keep the OrderNumber inside the object (for whatever reason), but need to be able to add a new object to the list and make all the other objects adjust their OrderNumber to make the new one fit. Also the actual order of the items in the list does not (necessarily) matter.

This could be done by wrapping the list and implementing your own operations (Move/Insert/Remove functions, which did the following:

Insert Loop through all the items and increase the ordernumber by one where the ordernumber >= new item's order number Add the item to the list

Remove Remove the item Loop through all the items and decrease the ordernumber by one where the ordernumber > removed item's order number

Move Remove the item Renumber the item Insert the item