# In defense of linked lists

DevFeed: [In defense of linked lists](<https://devfeed.tech/articles/in-defense-of-linked-lists-20629.md>)

Original publisher: [Read original article](<http://antirez.com/news/138>)

Author: Antirez

Published: 2022-11-04T18:46:29Z

Content type: opinion

Language: en

Sources: [Antirez](<https://devfeed.tech/sources/antirez.md>)

Topics: [Data structures](<https://devfeed.tech/topics/data-structures.md>), [Programming](<https://devfeed.tech/topics/programming.md>), [Skiplists](<https://devfeed.tech/topics/skiplists.md>)

Tags: [blog](<https://devfeed.tech/tags/blog.md>), [blog-post](<https://devfeed.tech/tags/blog-post.md>), [buffer](<https://devfeed.tech/tags/buffer.md>), [cache](<https://devfeed.tech/tags/cache.md>), [coding](<https://devfeed.tech/tags/coding.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [educational](<https://devfeed.tech/tags/educational.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [insert](<https://devfeed.tech/tags/insert.md>), [interviews](<https://devfeed.tech/tags/interviews.md>), [linked-list](<https://devfeed.tech/tags/linked-list.md>), [node](<https://devfeed.tech/tags/node.md>), [order](<https://devfeed.tech/tags/order.md>), [pointers](<https://devfeed.tech/tags/pointers.md>), [recursion](<https://devfeed.tech/tags/recursion.md>), [rust](<https://devfeed.tech/tags/rust.md>), [skip-list](<https://devfeed.tech/tags/skip-list.md>), [space](<https://devfeed.tech/tags/space.md>), [time](<https://devfeed.tech/tags/time.md>)

## AI overview

The author argues that linked lists have value beyond coding interviews: they teach how constant-time additions and linear traversal make time and order tradeoffs tangible. Lists can be augmented with backward or "far" pointers, or multiple items per node, to create structures with different properties. Their constant-time split and join can support practical designs: the author cites Redis combining a threaded operation's output buffer with a real client's buffer, and the Linux kernel's embedded-list macros. The text also presents linked lists as useful for incremental ordering and movement, and simple to implement from memory.

## Source excerpt

A few days ago, on Twitter (oh, dear Twitter: whatever happens I'll be there as long as possible - if you care about people that put a lot of energy in creating it, think twice before leaving the platform). So, on Twitter, I was talking about a very bad implementation of linked lists written in Rust. From the tone of certain replies, I got the feeling that many people think linked lists are like a joke. A trivial data structure that is only good for coding interviews, otherwise totally useless. In a word: the bubble sort of data structures. I disagree, so I thought of writing this blog post full of all the things I love about linked lists. So, get ready to read a sentimental post about a data structure, and don't tell I didn't warn you. Linked lists are educational. When your teacher, or the page of a book, or anything that exposes you for the first time to linked lists shows you this little circle with an arrow pointing to another circle, something immense happens in your mind. Similar to what happens when you understand recursion for the first time. You get what data structures made of links truly are: the triviality of a single node that becomes a lot more powerful and complex once it references another one. Linked lists show the new programmer fundamental things about space and time in computation: how it is possible to add elements in a constant time, and how order is fundamentally costly, because if you want to insert an element "in place" you have to go from one node to the other. You immediately start thinking of ways to speed up the process (preparing you for the next things), and at the same time you understand, deeply, what O(1) and O(N) really mean. Linked lists are augmentable. Add a pointer to the previous element, and now it is possible to go both sides. Add "far" pointers from time to time, and you have a skip list with completely different properties. Change every node to hold multiple items and your linked list becomes unrolled, providing very diff