JacksonDunstan.com

Contrary to what you may have learned in a data structures class, linked lists are virtually always slower than just using arrays. The same goes for array wrapper classes like List. Today’s article discusses why this is the case and tests it out with a C# Unity app to make sure that the real world validates the theory.

Every computer science curriculum includes a data structures class where you learn about arrays and linked lists. Invariably, you learn the supposed advantages and disadvantages of each along with the advice that both are just tools suited to different tasks. The lesson usually includes a discussion of the time complexity (a.k.a. “Big O notation”) of various operations with each data structure.

For example, accessing a random element of an array of length N is O(1), meaning it’s at worst just one step. This is due to being able to use an index to immediately find the element. For a linked list of length N, the worst case is N so it is O(N). This is because you have to look through each element until you find it and the one you want could be the very last one. Advantage: array.

Then there’s a discussion of inserting new elements. For an array of fixed size you need to allocate a new array and copy all the existing elements to it then add the new element. That’s N copies, so you get O(N). For a list you can just modify the “next” and “previous” pointers of the nodes before and after the place to insert the element and leave the rest of the list alone. That’s just a constant number of operations, so it’s called O(1) as well. Advantage: linked list.

Something is left out of the linked list operation though. While your linked list class is likely to have a pointer to the head and possibly the tail of the list, it almost certainly won’t have pointers to all the middle elements. So how do you know which nodes’ “next” and “previous” pointers to modify? The answer is that you need to effectively access a random element of the linked list, which we’ve seen is O(N). This means that both the array and the linked list are O(N) for insertions. The same goes for removals and various other operations that supposedly involve these surgical changes to single nodes in the list.

What’s worse is that these academic discussions rarely take actual hardware into account. Real apps run on actual hardware though and actual hardware has a preference. It wants to load blocks of memory into its L1, L2, and L3 caches so that it can be accessed orders of magnitude faster than going all the way out to main system RAM. Linked lists are allocated one node at a time though, so their contents are spread all over RAM. This makes it impossible to load large blocks of the linked list into the cache.

Consider this small memory map for five int elements:

This array can all be loaded into cache in one fell swoop and accessed in order: 0, 4, 8, 12, 16. The linked list, however, isn’t laid out to take advantage of that. Its first element (at 252) is loaded in and processed, but the next element wasn’t loaded since it was too far away at 1000, so it has to be loaded in now before processing. The same goes for the third, fourth, and fifth elements. In this worst-case scenario, each list access is its own RAM fetch and the cache is essentially ignored entirely.

So how does this all translate to C# code for Unity apps? Well, we get to use two main classes representing arrays and linked lists. System.Collections.Generic.List<T> represents arrays and System.Collections.Generic.LinkedList<T> represents linked lists. Since, as we’ve seen above, most operations come down to iterating over the lists, let’s just do a little test to iterate over a List and a LinkedList. For good measure, we’ll throw in arrays and iterate over them in the normal way and the “unsafe” way as demonstrated in the previous article.

Here’s the test script:

using System.Collections.Generic;
using System.Reflection;
using System.Runtime;
 
using UnityEngine;
 
public class TestScript : MonoBehaviour
{
	private string report;
 
	void Start()
	{
		GCSettings.LatencyMode = GCLatencyMode.LowLatency;
		report = string.Join(
			"\n",
			new string[]{
				"Test,Array Time,Array (unsafe) Time,List Time,LinkedList Time",
				Test(1000000),
				Test(2000000),
				Test(3000000),
				Test(4000000),
				Test(5000000),
				Test(6000000),
				Test(7000000),
				Test(8000000),
				Test(9000000),
				Test(10000000)
			}
		);
	}
 
	string Test(int length)
	{
		var stopwatch = new System.Diagnostics.Stopwatch();
		var array = new int[length];
		var list = new List<int>();
		var linkedList = new LinkedList<int>();
		for (var i = 0; i < length; ++i)
		{
			array[i] = i;
			list.Add(i);
			linkedList.AddLast(i);
		}
 
		int sum;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		for (var i = 0; i < length; ++i)
		{
			sum += array[i];
		}
		var arrayTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		unsafe
		{
			fixed (int* p = &array[0])
			{
				for (int* cur = p, end = p+length; cur < end; ++cur)
				{
					sum += *cur;
				}
			}
		}
		var arrayUnsafeTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		for (var i = 0; i < length; ++i)
		{
			sum += list[i];
		}
		var listTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		foreach (var i in linkedList)
		{
			sum += i;
		}
		var linkedListTime = stopwatch.ElapsedMilliseconds;
 
		return string.Join(
			",",
			new string[] {
				length.ToString(),
				arrayTime.ToString(),
				arrayUnsafeTime.ToString(),
				listTime.ToString(),
				linkedListTime.ToString()
			}
		);
	}
 
	void OnGUI()
	{
		GUI.TextArea(new Rect(0, 0, Screen.width, Screen.height), report);
	}
}

If you want to try out the test yourself, simply paste the above code into a TestScript.cs file in your Unity project’s Assets directory and attach it to the main camera game object in a new, empty project. Then build in non-development mode for 64-bit processors and run it windowed at 640×480 with fastest graphics. I ran it that way on this machine:

• 2.3 Ghz Intel Core i7-3615QM
• Mac OS X 10.10.3
• Unity 5.1.0f3, Mac OS X Standalone, x86_64, non-development
• 640×480, Fastest, Windowed

And got these results:

There’s a clear difference in trends between arrays and linked lists here. Linked list times grow linearly at about a 45 degree angle. That’s exactly what we’d expect from an O(N) algorithm. Arrays, on the other hand, are optimized by the CPU cache. They grow linearly too, but at a lot less steep of an incline.

Less important is the difference between List and raw arrays. Yes, the raw arrays are faster, but the trend is what counts here. List simply has some overhead that you can easily eliminate with QuickList or GetBackingArray() as shown in the previous article.

So when should you consider using a linked list? It’s hard to come up with an example, but there may be extreme cases that exist. If you can think of any or have any other thoughts about linked lists and arrays, let me know in the comments!