Easiest way to Rotate a List in c#

Question

Lists say I have a list List<int> {1,2,3,4,5}

Rotate means:

=> {2,3,4,5,1} => {3,4,5,1,2} => {4,5,1,2,3}

Maybe rotate is not the best word for this, but hope you understand what I means

My question, whats the easiest way (in short code, c# 4 Linq ready), and will not be hit by performance (reasonable performance)

Thanks.

Solution 1

You could implement it as a queue. Dequeue and Enqueue the same value.

**I wasn't sure about performance in converting a List to a Queue, but people upvoted my comment, so I'm posting this as an answer.

Solution 2

List<T>

The simplest way (for a List<T>) is to use:

int first = list[0];
list.RemoveAt(0);
list.Add(first);

Performance is nasty though - O(n).

Array

This is basically equivalent to the List<T> version, but more manual:

int first = array[0];
Array.Copy(array, 1, array, 0, array.Length - 1);
array[array.Length - 1] = first;

LinkedList<T>

If you could use a LinkedList<T> instead, that would be much simpler:

int first = linkedList.First;
linkedList.RemoveFirst();
linkedList.AddLast(first);

This is O(1) as each operation is constant time.

Queue<T>

cadrell0's solution of using a queue is a single statement, as Dequeue removes the element and returns it:

queue.Enqueue(queue.Dequeue());

While I can't find any documentation of the performance characteristic of this, I'd expect Queue<T> to be implemented using an array and an index as the "virtual starting point" - in which case this is another O(1) solution.

Note that in all of these cases you'd want to check for the list being empty first. (You could deem that to be an error, or a no-op.)

Solution 3

I use this one:

public static List<T> Rotate<T>(this List<T> list, int offset)
{
    return list.Skip(offset).Concat(list.Take(offset)).ToList();
}

Solution 4

It seems like some answerers have treated this as a chance to explore data structures. While those answers are informative and useful, they are not very Linq'ish.

The Linq'ish approach is: You get an extension method which returns a lazy IEnumerable that knows how to build what you want. This method doesn't modify the source and should only allocate a copy of the source if necessary.

public static IEnumerable<IEnumerable<T>> Rotate<T>(this List<T> source)
{
  for(int i = 0; i < source.Count; i++)
  {
    yield return source.TakeFrom(i).Concat(source.TakeUntil(i));
  }
}

  //similar to list.Skip(i-1), but using list's indexer access to reduce iterations
public static IEnumerable<T> TakeFrom<T>(this List<T> source, int index)
{
  for(int i = index; i < source.Count; i++)
  {
    yield return source[i];
  }
}

  //similar to list.Take(i), but using list's indexer access to reduce iterations    
public static IEnumerable<T> TakeUntil<T>(this List<T> source, int index)
{
  for(int i = 0; i < index; i++)
  {
    yield return source[i];
  }
}

Used as:

List<int> myList = new List<int>(){1, 2, 3, 4, 5};
foreach(IEnumerable<int> rotation in myList.Rotate())
{
  //do something with that rotation
}

Solution 5

How about this:

var output = input.Skip(rot)
                  .Take(input.Count - rot)
                  .Concat(input.Take(rot))
                  .ToList();

Where rot is the number of spots to rotate - which must be less than the number of elements in the input list.

As @cadrell0 answer shows if this is all you do with your list, you should use a queue instead of a list.

View more solutions

Comments

[Servy]

The only performance issues would be if the OP is doing anything else, because switching to a queue means that accessing anything but the first/last items are inefficient.

[Jon Skeet]

Have added the actual calls to my answer, as you hadn't included them and mine is pretty much collecting implementations :) Hope you don't mind.

[Servy]

I'd go with queue over linked list. A circular array just generally performs better in the average case, and in either situation all of the details are abstracted away by the language anyway.

[cadrell0]

@JonSkeet Not at all. Pure laziness is the reason I left it out of mine.

[Jon Skeet]

@Servy: Yup, that's fair comment. A linked list allows the reverse rotation more easily, as .NET doesn't have a deque :( You could obviously build one easily though...

[Pero P.]

Isn't 'RemoveFirst()` void? The docs actually shows an example of exactly what the OP has asked: msdn.microsoft.com/en-us/library/ms132181.aspx. You have to get hold of the first node initially using linkedList.First?

[Jon Skeet]

@PeroPejovic: Apologies, yes. I wrote the example then checked, was disappointed to find that it wouldn't work, and forgot to fix it.

[Servy]

@JonSkeet Again, it's not the built in functionality, but it would be easy enough to make a circular array 'reverse' itself. You have pointers to the first and last, you just need to flip them and keep a boolean that indicates whether you're moving 'up' or 'down' in the array. It would add a fair bit of extra code mess, which is why I'm sure it's not done, but on a conceptual level reversing a circular array is still a very fast O(1) operation.

[Servy]

@JonSkeet Just realzied you meant reverse as in take from the back and put on the front, not reverse all elements. In either case, easy enough to implement with a circular array if you wanted, but not available through the exposed 'Queue' class. Agreed Deques would be nice though.

[nawfal]

Indeed yours look more convoluted than Jon's list.Add(list.RemoveAt(0));

[Cabuxa.Mapache]

Smart, elegant and easy... best solution so far... only keep in mind you must store value for offset to pass the correct one in each call.

[Enigmativity]

There's no mention of console input in the question. For this to be a valid answer you need to start with List<int> {1,2,3,4,5} and show how your code can do the rotation.

[Naphstor]

I believe the question says "Lets say i have a list". It does not say how the list is prepared. What I am trying to show is while preparing your input list, or basically while adding data to your input list itself you can use modular arithmetic and solve the problem. Even if you want to work with existing list, you can still use above logic to prepare new rotated list.

[Enigmativity]

I would suggest that you explicitly show how to do this from the list. Showing something extra is probably not worthwhile.

[Naphstor]

I agree on that. But I was just giving an idea of implementing the solution in different way.

[Enigmativity]

Showing it in a different way is probably not worthwhile. You have an interesting answer but it is hard to understand how it applies to the question given that it doesn't show how to do it from the list.

[Thomas]

This is the best example of the influence a Collection can have over Big-O I have ever seen. Did a bit of digging and question asking to understand it, but really awesome. Thanks @JonSkeet

[Vasilii Muravev]

Add some comments to your answer, please.

[Gert Arnold]

And when a question already has this many answers you need to explain what makes your answer unique among them.

[Gert Arnold]

Please add some explanation to your code to help readers understand why this solves the problem. Also, does this really add anything to the existing answers?

[Sefa Şahinoğlu]

Really nice and elegant solution, thank you very much.