Discovering Data Structures – Linked Lists

As I’m preparing for different code challenges, I’m coming across different concepts that fall under the umbrella of Data Structures and Algorithms. For instance, I’m going through different questions on HackerRank and LeetCode, and come across certain questions that have us traverse through a LinkedList.

I’m going to be completely honest, it took me a while to remember what that was. I took a programming class in college many years ago and I remember the term but had to look it up to refresh my memory on the details. Before I get into what linked lists are, let’s talk about what data structures are.

Data Structures briefly explained

Wikipedia describes it as a data organization, management, and storage format that enables efficient access and modification. In other terms, it’s a collection of data values that have relationships with each other in some way. This data can be manipulated in some way through methods or operations. If you’re thinking arrays, you may have heard some such as push(), pop() or shift(), to name a few. Other operations may not be abstracted as clearly, depending on the language you’re using, such as inserting, deleting or sorting.

Now, on to linked lists

Linked lists is a linear data structure, consisting of nodes between a head node and a tail node. Each node stores a data value and has a reference pointer to the next node, and in the case of a doubly-linked list, has a pointer to the previous node as well.

They’re often compared to arrays, which is also a linear data structure. However, they’re different in the sense that the data stored in a linked list is not stored contiguously in memory, or in other words, next to each other.

What this means is, say for example I want to get rid of node “C” in the picture above and have node “B” point to “D” instead. What I would do is before deleting node “C”, I would have node “B”‘s next pointer set to the value of node “C”‘s next pointer, which in this case is to “D”. I didn’t have to do any other memory allocation or shifting of the other elements.

This is the advantage of linked lists. Let’s say I deleted an element in an array. That means I would have to shift a bunch of memory around to shift all the elements.

Some disadvantages

Now, like all data structures, they all serve their purposes and have both advantages and disadvantages. Unlike arrays, random access is not allowed. If I wanted to get information from a list, I’d have to traverse through the list sequentially. Therefore, some search algorithms are slower or not available to the linked list.

Implementation in JavaScript

As of late, I’ve been programming almost exclusively in JavaScript to simplify some of my learning experiences. Jumping around languages got confusing. That’s not to say I won’t touch Python again, but it’s going on a short hiatus.

Some languages, like Java, C++ or Python, have built-in classes for linked lists. Javascript does not!

This article from GeeksForGeeks, which was referenced in my last post, has been a big help in understanding how to implement the different classes and functions needed for linked lists to work. For instance, a node class would look something like this:

 class Node { 
	// constructor 
	constructor(element) 
	{ 
		this.element = element; 
		this.next = null
	} 
} 

Since a LinkedList is comprised of nodes, then a LinkedList class would look something like this:

// linkedlist class 
class LinkedList { 
	constructor() 
	{ 
		this.head = null; 
		this.size = 0; 
	} 
} 

In the code snippet above, we’re assuming that it’s an empty list, so the head is at first null, and the size of this list is first set to zero. Subsequent helper methods like add or delete would alter the value of this object property accordingly.

I encourage you to explore the article I linked and keep programming and exploring other data structure types. Tune in next time!