I implemented a linked list data structure in Swift. It seemed like a good idea for porting the Linkage source code from C++ to Swift but I’ve also read that using a linked list is a terrible idea. This is a bit of a rant on that subject…

While you’re right that linked lists are a fairly standard data structure, in practice most of that standardisation comes from their prevalence in CS and algorithmics classes. Linked lists have useful properties that make them helpful for framing discussions about algorithmic complexity, and they are straightforward enough to understand that they are a great building block for early data structures work. However, in practical design I can think of very few cases where linked lists are useful.

Cory Benfield

I feel like I disagree with this. The first thing to understand is that I learned to write C and C++ code in the late 1980s and performance was a critical factor back when a processor ran at 6 to 8 Mhz. Yes, that’s 6 to 8 million clock ticks per second. With processors running at around 4 Ghz, there are almost 1000 times more clock ticks per second to do the work. Because of my background, the idea of inserting or deleting data from an array by moving the rest of the data around it seems like a terrible idea. In fact, I would argue that it being common to waste CPU cycles is one of the worse things that has happened in computer programming in recent decades. Programmers can certainly get more done when they are not worrying about how much CPU time they are using; But doesn’t CPU time take power, maybe from a coal power plant or from a battery that needs to save some power for emergency phone calls? And why with faster processors am I always sitting around waiting for my computer to do stuff? Is it because programmers are lazy and have no concern for performance?

But maybe Cory is right. I don’t work with programmers that are at the top in their field anymore. I have not worked with people significantly smarter than me in fifteen years. I don’t know what is state-of-the-art anymore.

A linked list makes sense to me in any situation where an element is going to be inserted or removed from the data structure at a location that is not the very end. It also makes sense to be when the amount of space needed for the data is not known ahead of time. Adding to the end of an array might require an allocation and removing an element from the beginning of an array might cause all the data after it to be moved in memory (or copied). With a lot of extra CPU available for this type of thing, there is certainly no problem where a user is sitting waiting for things to finish. But that should not be the main concern in a world where we are burning fossil fuels to power these computers and to cool them as their CPUs overheat due to having far too much wasteful work to do.

The Linkage source code uses linked lists for all the elements in a mechanism. There are lists of connectors, links, and splines. When the user drops an element into their mechanism, a new element is added to the end of a list. More importantly, when they delete an element, it is deleted from the list. these are not things where the user will notice a performance hit because this is not a First Person Shooter or racing game where we are striving for 60 FPS rendering of a detailed landscape. in the case of the Linkage software, an array (in Swift) seems acceptable. In C++, there are no built-in mechanisms for removing an element from the middle of an array so I would have ended up writing that stuff myself. That alone is a good reason to use a linked list since MFC (Microsoft Foundation Classes) comes with a linked list data structure.

I almost wonder if the linked list data structure is not useful in practical design because any time you need something more complicated than an array, you then probably need something more complicated than a linked list. A game with rendering might need a quadtree or other more complicated data structure but when that’s not needed, a simple array might do. Still, I want the Linkage source code to not waste CPU cycles deleting elements for the middle of arrays. But I also like the simplicity of using indexes to keep track of the current location in the array and all the other benefits that come from not using an extra structure in memory that holds the “next” and “previous” pointers.

In the end, I decided to skip using my generic linked list and just use arrays. There is no point during the running of the software where the performance of a list/array is important enough to justify it. And I want to be compliant with current programming paradigms; There’s no need to buck the system here.

One note to anyone who reads this and makes a claim about a linked list being used only in CS algorithm classes, or any other similar claim: Make sure you can back up your claim. You might be the person who is mistaken if you don’t have any solid proof that you are right about this. Many real-world programmers do a lot of stuff that you may not be aware of because you don’t work in their industry. In the biotech industry where algorithms are written to compare huge sets of data as quickly as possible, I would have profiled my code and tried both arrays and linked lists to compare their performance. If the performance of the linked list was 1% better, you can be damned sure that I would have used a linked list. Heck, I once had to write assembly language in order to use SIMD instructions to get a 25% improvement in algorithm speed just for one special use of the algorithm. How’s that for using a more complicated less-common way of programming in order to get my employer a better-selling product? It might just be the case that a data structure like a linked list is not used because programmers have less-performative ways of doing things and they can be lazy and ignore that they are wasting battery life when so much is available to them.

[Addendum]

Ok, so I did a test. Here’s the code (for the test, not for the linked list):

    class Temp {
        var derp: Int = 0
    }

    var testArray = [Temp]( repeating: Temp(), count: 12000 )
    var testList = LinkedList<Temp>()
    for _ in 0..<12000 {
        testList.append( Temp() )
    }

    // Speed test...

    let start = clock()
    for _ in 0..<10000 {
        testArray.remove( at: 1100 )
        testArray.insert( Temp(), at: 1100 )
    }
    let result = clock() - start
    print( "result 1 = \(result)" )

    let node = testList.node( at: 1100 )
    let start2 = clock()
    for _ in 0..<10000 {
        testList.remove( node!.next! )
        testList.insert( Temp(), after: node! )
    }

    let result2 = clock() - start2
    print( "result 2 = \(result2)" )

The array manipulation runs faster than the linked list manipulation. That tells me that there is no reason to use a linked list. I have guesses about what’s slow but since they are just guesses and there’s no easy way to optimize the linked list code to make it fast enough to justify, I’m definitely switching to using an array.

Leave a comment