sparr | Linked lists don't exist (Reply)

Last night I was trying to show someone my implementation of a linked list, and I realized linked lists don't exist.

Sure, you might have an object that contains some additional metadata about a linked list such as the type of its contents or its length, and methods such as an iterator or deletion or insertion, but the list itself is a purely abstract concept.

What exists are the nodes and the links between them. Without unnecessary metadata, a reference to a linked list is really just a reference to the head node.

When you find the middle element of the list and set node.next=null (or your language's equivalent), you've only performed an operation on a node, and suddenly you've truncated the list and created a whole new list starting at the next node. Magic!

Just like strings in C don't exist. A string in C is just a pointer to a character in memory, and you have to walk forward until you hit a null to find out what's in it or even how long it is. There are plenty of ways, and plenty of approaches in other languages, that wrap additional metadata and methods around this concept, but without them you're left with just a pointer. And if you drop a null byte in the middle of where a "string" used to be, you suddenly have two separate strings.