Does code exist, for shifting List elements to left or right by specified amount, in C#?
It is tricky code, it will take some time to write and test special cases, I would rather reuse something if it exists.
Thanks
asked Aug 12, 2013 at 6:43
5 Answers
Something like this for shift left...
public static void ShiftLeft<T>(List<T> lst, int shifts)
{
for (int i = shifts; i < lst.Count; i++)
{
lst[i - shifts] = lst[i];
}
for (int i = lst.Count - shifts; i < lst.Count; i++)
{
lst[i] = default(T);
}
}
For shift right it's a little more tricky, because we must copy in reverse
public static void ShiftRight<T>(List<T> lst, int shifts)
{
for (int i = lst.Count - shifts - 1; i >= 0; i--)
{
lst[i + shifts] = lst[i];
}
for (int i = 0; i < shifts; i++)
{
lst[i] = default(T);
}
}
With arrays it's a lot more simple, because Array has very powerful methods:
public static void ShiftLeft<T>(T[] arr, int shifts)
{
Array.Copy(arr, shifts, arr, 0, arr.Length - shifts);
Array.Clear(arr, arr.Length - shifts, shifts);
}
public static void ShiftRight<T>(T[] arr, int shifts)
{
Array.Copy(arr, 0, arr, shifts, arr.Length - shifts);
Array.Clear(arr, 0, shifts);
}
And yes, Array.Copy is protected against overleap: If sourceArray and destinationArray overlap, this method behaves as if the original values of sourceArray were preserved in a temporary location before destinationArray is overwritten.
-
@hvd stackoverflow.com/a/2381397/613130 Someone benchmarked them...
Array.Copyis faster (or at least it was).Array.ConstrainedCopyGuarantees that all changes are undone if the copy does not succeed completely. I'll say that must have a little cost.– xanatosCommented Aug 12, 2013 at 7:20 -
@hvd He tested only on
int?. Perhaps it depends on the type (you would have to test at leastbyte,int,int?,DateTime,Guid,object, (random object) to be sure... And in various sizes... 1, 16, 100, 1000, 10000.) In the end probably the difference is nearly 0.– xanatosCommented Aug 12, 2013 at 7:27 -
I was going to ask why these were not extension methods, but then I saw the code below. Commented Apr 2, 2015 at 15:29
-
instead of filling the range [lst.Count - shifts, lst.Count ) with default(T), I'm going to set the list Count to (Count - shifts), and I will leave the Capacity untouched since my list can grow again !– AminosCommented Nov 3, 2021 at 9:46
-
Below are a couple of extension methods that will shift the list either right or left. The methods will return a list.
public static class ShiftList
{
public static List<T> ShiftLeft<T>(this List<T> list, int shiftBy)
{
if (list.Count <= shiftBy)
{
return list;
}
var result = list.GetRange(shiftBy, list.Count-shiftBy);
result.AddRange(list.GetRange(0,shiftBy));
return result;
}
public static List<T> ShiftRight<T>(this List<T> list, int shiftBy)
{
if (list.Count <= shiftBy)
{
return list;
}
var result = list.GetRange(list.Count - shiftBy, shiftBy);
result.AddRange(list.GetRange(0, list.Count - shiftBy));
return result;
}
}
Here's an example of how to call it.
class Program
{
static void Main(string[] args)
{
List<int> test = Enumerable.Range(0, 10).ToList();
test = test.ShiftLeft(1);
PrintList(test);
Console.WriteLine("");
PrintList(test.ShiftRight(2));
Console.ReadLine();
}
private static void PrintList(List<int> test)
{
for (int i = 0; i < test.Count; i++)
{
Console.WriteLine(test[i]);
}
}
}
Like nerdybeardo posted, but a modern way:
public static class ShiftList
{
public static List<T> ShiftLeft<T>(this List<T> list, int shiftBy)
{
if (list.Count <= shiftBy)
{
return list;
}
return list.Skip(shiftBy).Concat(list.Take(shiftBy)).ToList();
}
public static List<T> ShiftRight<T>(this List<T> list, int shiftBy)
{
if (list.Count <= shiftBy)
{
return list;
}
return list.ShiftLeft(list.Count - shiftBy);
}
}
Keep it simple by taking the first part and second part and flipping them. Same thing but flip other way for the ShiftRight
public static List<int> ShiftLeft(List<int> a, int d)
{
if (a.Count > d)
{
var beginingPart = a.GetRange(0, d);
var remainingPart = a.GetRange(d, a.Count - d);
return remainingPart.Concat(beginingPart).ToList();
}
else if (a.Count < d)
{
var mod = d % a.Count;
if (mod != 0)
{
return rotLeft(a, mod);
}
}
return a;
}
-
I don't see a similar code snippet, can you tell me which user has similar? Also I'm not sure what question 2 is, I only see one question mark in the op post. If you mean nerdybeardo post, some parts are similar but mine uses recursion and handles an edge case that his doesn't.– conterioCommented Sep 19, 2021 at 4:55
Given that "iterations" is the times you want to shift and "numbers" is the List
Shift left:
static void ShiftLeft(int iterations)
{
for (int i = 0; i < iterations; i++)
{
numbers.Add(numbers[0]);
numbers.RemoveAt(0);
}
}
ShiftRight:
static void ShiftRight(int iterations)
{
for (int i = 0; i < iterations; i++)
{
numbers.Insert(0, numbers[numbers.Count - 1]);
numbers.RemoveAt(numbers.Count - 1);
}
}
-
This is simple code but have you considered the performance implications? Each call to
RemoveAt()/Insert()causes the rest of the list to be shifted 1 element, and you're passing the worst case, index0. Ifiterationsis1000then instead of shifting each element by 1,000 positions 1 time this will shift each element by 1 position 1,000 times; more shifts are expensive, bigger shifts are not/free. Also, ifnumbers.Count == numbers.Capacitythis will cause the internal array to be resized (doubled) just to hold that one extra element that exists beforeRemoveAt()is called. Commented Jun 18, 2022 at 18:29
list[0]returns what waslist[1], etc" or "for each element in the list, perform some shift operation upon it"?Listis rather expensive - but both is actually really simple..