The basics of ordered linked lists in C

My C lecturer said my linked list implementation was the best linked list code he'd seen written under exam conditions in his career. True story. The question involved writing a linked list in C to manage books in a bookshelf (each book was an instance of a struct). But unlike my fellow students who took time to memorise linked list code, I didn't bother as I was too busy playing Civilization. Priorities people!

If you're sitting a C exam that has linked lists, you can expect a generic question about linked lists. The question is usually in the form "You have a bunch of (objects) in a (collection). Write a linked list to store this data." The objects are usually something like

• books in a bookshelves
• words in a sentence
• phone numbers in a phone book
• spells in a spellbook if your lecturer likes Harry Potter.

The logic behind each is the same, and the only thing that changes is the name of the variables and the amount of variables in the struct. If you understand one linked list, you'll understand them all.

Nodes

In algorithms and data structures terminology, the items in a linked list are called nodes. If you're having trouble conceptualising a node, think of it as a business card. Just like a business card, a node can contain a single piece of data on it (like "MIB") or it can contain multiple types of data (like a name, address, phone number).

A business card with a single piece of data

In addition to the useful data you might put in a node, each node also contains a pointer to the next node in the list. If you were a visual person, you might visualize this as a piece of string connecting two business cards.

Linking the nodes

All nodes in a linked list are connected to each sequentially using pointers. This is why they are called linked lists. The first node points to the second node. The second node points to the third node, and so on and so forth until it gets to...

The last node

If it's the last node in the list, the pointer points to NULL. This is important, because checking for NULL is the way we know we're at the end of the list.

Is there any way of skipping to the 27th node?

No. You go to the head node, and then you follow the pointer to the next node. Then you do that 26 more times.

The head node

You'll need a way to find the first node in the list. This is known as the head of a linked list. The head tells you where the linked list starts: if you lose the contents of the head node, the whole list is screwed and you're a buffoon. Don't be a buffoon! Tips for not being a buffoon:

1. When creating the first node in a linked list, the first node is the head.
   Point the head at the first node.
2. When deleting the first node in a list, point the head at the second node.

The current node

As you iterate through a linked list to look at its contents, you'll need a way of tracking which node you're looking at. This is the current node. To cycle to the next node, we change where the current node points with

Current = Current->Next