Data Structures – Linked Lists

Every data structure is important; linked lists are one of the fundamental building blocks of more advanced structures. Let’s get into the basics.

 

The Basics

The linked list is a concept in Computer Science, where a group of nodes is linked together forming a chain. This chain is created by “linking” a node to another node. Now, a “link” is simply a reference to another node; it’s not some wild new concept. The main idea is an object referencing another object. That’s the concept, but as programmers, we have to be able to effectively represent that in the computer. So, let’s construct that representation for linked lists and doubly linked lists.

 

The Representation

A representation is simply recreating a concept inside a computer. To do that effectively, we need to write some code that captures the actions and structure of a linked list. In my opinion, these are very straightforward. These include:

  • Linked List: A class for containing the important linked list information and methods (how to traverse the list)
  • Node: An element on the list that contains data
  • setNext(): Links a node to the next node
  • setPrev(): Links a node to the previous node
  • getNext(): gets the next linked node
  • getPrev(): gets the previously linked node
  • getData(): gets the data contained within a node

With this list of classes and methods, we can create linked lists. But, this alone is not enough to really traverse a list. We need a traversal method to go through each node (reference) until it reaches the end of the list. This is where the linked list class will come in handy. Let’s begin the coding portion. This will be in JavaScript, but the structure of the code should be similar in other languages. Using JavaScript, also allows you to test it in the browser. Let’s begin.

 

You can test this code in your browser and it should work as well. You can test it by right clicking on a webpage, clicking inspect (Chrome), and opening the JavaScript console. Now, let’s break this down.

 

Breakdown

As you can see, we create the basic linked list and doubly linked list classes. Each one has minor differences, but the most important thing to pay attention to is the addNode method which adds a node to the tail end of the list and removeNode which removes the node at the tail end of the list. To make it easier to add nodes multiple times, we simply return the newly created class and use chaining. The process of adding a node is what we need to focus on. First, we create a node, then we set the next reference of the tail to be the new node; this allows the tail to “link” to the new node. Afterward, the new node is the tail, so we simply say `this._tail = node;`. Changing the tail to reference the new node, instead of the old tail. The same rules are applied to the doubly linked list. In this case, we’re only working with adding nodes at the tail end of a linked list, but you could be more flexible and add nodes after the head if you wrote a similar method. Anyway, let’s illustrate the linked list addNode method.

 

LinkedListExample

 

As you can see, first we created our new linked list in code; this is line 120. Afterward, we add nodes; this is how a node is added. The new node becomes the new tail. Once we have completed that, the old tail (the head in this case), uses setNext to link to the new node, forming a chain between them. For each subsequent node, this process is repeated. This is how nodes are added to the tail end of the linked list. The only difference between this and the doubly linked list is that we also set the new node to link back to the previous node so we can reference (link) previous nodes.

I hope this post helps you understand linked lists a bit better; take time to play with the code yourself and you’ll start to understand the concept a bit better. It can make sense on a whiteboard, but understanding how to code it is also important.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s