An introduction to Linked Lists [Data Structure]

An introduction to Linked Lists [Data Structure]

Introduction

What is a Linked List? This is the first question we should answer before we move on and see come code. This will be a quick introduction into Linked Lists, for more detailed infos i will link to some great resources at the end of this article.

Linked List in a nutshell

Linked List are a data structure and are very similar to arrays. The difference is that a linked list is more dynamic. You dont need to pick a fixed size for an array like in many programming languages. Also a Linked List is not stored sequential in memory like an array. They consist of nodes. Each node hold a value (like a string, integer, etc.) and a "next" value. The "next" value is a reference to the next node. Thats the reason why a Linked List doesnt need to be stored sequential in memory. Let me show you this picture:

Linked List

Whenever i use Linked Lists i use this image as it describes it very well.

The first node is called head. Its the most important node because its hold the reference to all other nodes behind it. Like i said above each node has data and a next value where the reference to the next node is stored. The last node is called tail.

Linked List in action

Lets dive into some javascript code to see Linked List in action.

First we define a node class: Alt Text

Each node we will create has a data and a next property. In data we can store anything we want like string, numbers etc. In next we store the reference to the next node. When we are at the end of a linked list the next value is null. If the next value is null we know "AHA! Here the Linked List is at the end".

The next step is to create a class for the Linked List: Alt Text

The Linked List class has a head property to define the head (the beginning) of the linked list and a size property to keep track of the overall size. Like the .length for arrays.

All other methods where we want to add/delete/update nodes in the Linked List will be put into this class.

Lets see some methods to alter our Linked List.

I encourage you to take this code, try to understand it and play around with it. Learning by doing is just the best way to learn in my opinion. I tried to document the code as good as possible for you to understand whats happening. If you stuck try first to copy the code and see what it does and more important WHY. Feel free to implement more methods to alter the Linked List! Have Fun!

Insert at the beginning Alt Text

Insert at the end Alt Text

Insert at specific index Alt Text

Method to log our Linked List Alt Text

Test the Code Alt Text Alt Text

Big O

See here about the Time Complexity for Linked List: bigocheatsheet.com

The good thing about Linked Lists are that you can insert a new node at the beginning with O(1). If you want to insert a node at the end its O(n) because we have to start at the head and then go from there till the end to append a new node.

Great Resources for more information about Linked List

Traversy Media: youtube.com/watch?v=ZBdE8DElQQU I learned a lot about Linked List from him and the code you saw above is mainly his code. A great teacher!

Hackerrank Youtube: youtube.com/watch?v=njTh_OwMljA

Summary

I hope you know have a basic understanding of what a Linked List is and how to use them. Feel free to drop comments if you have questions or find a mistake. I love to develop myself each day and whats better for improving than mistakes? :) Also this is my very first article so feel free to also comment what ive done good and where i can improve. Thank you very much, have a wonderful day and stay safe!