CS1.3 | Linked List Technical Article

What is a linked list?
A linked list is a chain of nodes linked to each other.

Unlike an array, a linked list is dynamic so it doesn't need the extra data space to store indexes of an array which could be used in a variety of different data structures. ie. stacks, hash tables, etc…

Before you learn about linked lists, you NEED to know about the pieces of the list: Nodes.

Yep! That's it! Pretty simple don't you think?
A node is a simple object that holds data about itself and points to the next node, extend this by pointing to the next node and you will find yourself a linked list.

How does a linked list work?
If a linked list was a pocket chain on a person:

The head starts the chain, it is where you start iterating from.

The latest node is the latest object that you prepend into the linked list.

The previous node is the node that gets its place taken and gets pointed by the latest node.

The tail is the termination of the linked list. The value of this placement is usually N/A, None, undefined, or the like.

Now that you know how it works. How would you implement this?

A linked list contains a head and a tail so that should be initialized.

To use a linked list you need to be able to “append”, prepend, delete, and iterate through nodes.
The process of appending a new node is to 1) Create the new node with parameters. 2) If the linked list is new: simply insert the new node and point to head and tail, if not, then point the last node at the new node and the new node at the tail.

Prepending

Like appending, prepending creates a new node but instead points the head at the new node and the new node at the previous node head was pointing to.

Deleting

Officially there is no way to “delete” a node. But to a linked list, if it doesn't exist within the list, it is deleted.
To “delete” a node from a list, you simply have to skip over the node by pointing the previous node to the next node.

Iteration
I'm sure you are all tired of reading so Ill keep this one simple => Node.next

Conclusion
Hopefully, this helps you understand linked lists as well as how to implement them. Linked lists to me are an amazingly efficient way to represent certain data structures… Namely stacks, queues, hash tables, trees… Well… If you know one then you practically know them all!