Data Structures: Linked List

Photo by Fré Sonneveld on Unsplash

Last week I dove in to the hash table data structure, and while the implementation is pretty straight-forward, it often hinges on another popular data structure, the linked list. The concept of a linked list has boundless applications and variations to help you organize data in useful ways. I’ll go through some of these variations and how they can help you in creating complex algorithmic solutions.

Linked List Basics

A linked list is a relatively simple set of objects. They are typically set up as an object class, with a data attribute and a next attribute, pointing to the next item in the list.

Linked List Example

You can think of each of these objects as a ‘node’, with their own data, and a reference to the next item in the list. Your node class can look something like this:

class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}

Now we can create a few nodes in our list:

const nodeOne = new ListNode(’foo’)
const nodeTwo = new ListNode(’bar’)
const nodeThree = new ListNode(’pan’)
nodeOne.next = nodeTwo
nodeTwo.next = nodeThree

and our linked class can be set up like this:

class LinkedList {
constructor(head = null) {
this.head = head
}
}

Let’s put our whole list object together:

const list = new LinkedList(nodeOne)

We are setting out first node as the head of the linked list, and we effectively have an object that looks like this:

// list{
head: {
value: ’foo’
next: {
value: ’bar’
next: {
value: ’pan’
next: null
}
}
}
}
}

Linked List Benefits

What does organizing our data like this do for us? Well since our list is not organized by indeces, we can add or remove items easily without reorganizing and rebuilding the entire list. With an array, this wouldn’t be possible.

Linked List Drawbacks

On the other side of the coin, because we don’t have and index associated with each item, we can’t use random lookup strategies for retrieval. We always need to start at the head node, and iterate down the list until we reach the node we are interested in. We also need to store the ‘pointer’ in memory as we iterate, so this extra memory needs to be allocated.

Other Types of Linked Lists

  1. Circular Linked List
Circular Linked List

If our final node references the first node, then it allows us to start from anywhere in the list and loop around, as long as we are sure to stop when we reach the node we started at.

These become incredibly useful if you need to loop around a list and perform as action on each node. For example, if an operating system needs to loop through a number of running applications, and give each one an allocation of time to perform its actions, it will keep these in a linked list. We can always return to the top of the list by referencing the next of the final node.

2) Doubly Linked List

Doubly Linked List

If we add a prev attribute to our nodes, we gain the ability to move in either direction along our linked list. This doesn’t add much more complexity to the nodes, but gives us more flexibility in how we deal with the object.

Deletion from a doubly linked list is more efficient, and inserting a node behind a particular node now becomes much easier, as we don’t need to traverse through the entire list again to reach it.

However, even more memory will need to be allocated for the extra pointer using the doubly linked list. We would need to modify previous as well as next pointers for every operation, compared to a singly linked list.

Conclusion

Linked lists in all of thier forms can be useful to implement in our solutions. I hope you enjoyed this introduction to the data structure and happy coding!

--

--

--

Software Engineer at Thrive TRM. Specializing in Ruby on Rails, React/Redux and JavaScript.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Counting Objects

How To Create an Angular Application (Basic Structure)

React: Native versus Web

Svelte : fetch image source

DmRef: Testing Cards

Practical data fetching with React Suspense that you can use today

Correct file ownership when mounting local folders in Docker on Linux

ReactJS Basics|Crack the code

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rick Moore

Rick Moore

Software Engineer at Thrive TRM. Specializing in Ruby on Rails, React/Redux and JavaScript.

More from Medium

Data Structures and How To Build It From Scratch Series #0

Data Structures, Algorithms, And Big O Notation! A Beginners Guide.

Big O Notation: part 2

2 Factors Slowing Down Your Code Debugging and How To Improve