Learning Linked Lists

I'll start by going over the basics. What is a linked list?

A linked list is a form of data structure. In a linked list the data in the structure is connected together in a sequence of objects. Take a look at this diagram from Wikipedia to better understand.

Each segment (or what is commonly referred to as a node) has two parts. The data it stores, and a pointer that references the next element in the chain.

Fun fact, a node is defined as "a place where a leaf and stem join on a plant."

This makes sense when thinking about data structures, each node is a new path that originates from the same structure.

Now that all of this makes sense in theory, how does it look when we implement it in code? Well a node could look like this.

Then to create nodes all we would need to do is something like node1 = new Node(5) node2 = newNode(4). Now we have two nodes, one containing the integer 5 and the other containing the integer 4, but they both have no form of connection. To manage our nodes a good solution is to create another class for the list itself.

Now we have a class for the list but no way to add in any of our nodes. So let's add it a method that utilizes our node class.

Let's go through what this is doing step by step. We pass in the data that we want to add to our list. We then create a new node containing that data. We see if the linked list has any nodes, if it doesn't we assign that node to be the head (the name for the first node in a linked list). If there is already a head we initialize a current variable that will help us keep track of which node we are looking at and set it to be the head. We then iterate through the list to the end with a while loop. Then we add in our new node to the end of the list.

This is only the bare bone functionality that needs to be in a linked list. What if we wanted to remove an node from the list? Count how many nodes there are in the list? Insert a node in a specific index in the list. Think about how you could implement these methods in the LinkedList class.

Another thing to think about. You probably noticed that because the nodes in a linked list only reference the next node, it's impossible to navigate backwards through the list.

There's actually another structure called a doubly linked list that, you guessed it, contains two pointers. One pointing to the next node, and on pointing to the previous node.

Think about how you would implement this in the code examples that we went over and what new functionality you could add!

If you want to start with the code from this post, you can get it here.