Linked List Data Structures

CAN I ASK FOR A REFERENCE?

Passport office employees process peoples’ applications
Image courtesy of Global News

Navigating linked lists is a lot like spending a day applying for a passport. I’ll show you why that is.

In a linked list each box or segment can be referred to as a ‘node’. Nodes represent the information contained in a single point within a data structure.

Each node in a linked list has three things:
- some useful data or methods
- a reference to the next node in the list

So picture this. You’re at the Government Services Bureau applying for a passport. You go to the front desk, listen to the info they have to offer you, and then get referred to the next place. So you go to the next place, fill out some forms, then get referred to the next place.

Just like you would in a linked list.

SINGLE VS DOUBLE

Keep in mind that with this style of linked list, you would only be able to see the next entry in the list, but not the previous one. This is known as a ‘single linked list’ and it can be represented in code like this:

class Node 
{constructor(data, next = null) {
this.data = data;
this.next = next;
}
}

If you wanted to be able to go backward in a linked list you’d need another entry, let’s call it ‘prev’, that allows you to access the previous node. This is known as a ‘double linked list’:

class Node 
{constructor(data, next = null) {
this.data = data;
this.next = next;
// Without this you can't access the node before
this.prev = prev;
}
}

How would we go about constructing and maintaining linked lists in a way that is straightforward and efficient?

By implementing a new class called LinkedList to manipulate the Node class that we’ve created:

class Node { 
constructor(data, next = null){
this.head = head;
this.size = 0;
}
}

At the core of it, you need to be able to access the linked list and do the following:
-print out the info about stuff in the linked list
-add an entry at the front (HEAD)
-add an entry to the end (TAIL)
-insert an entry at some index
-remove an entry at some index
-clear the list

We do this with methods that are inside of the LinkedList class. I found an excellent resource full of methods like this by Brad Traversy which you can click here to visit.

CURRENT

One thing I noticed in all these linked list methods is a ‘current’ variable. It’s used to store the reference to the node you’re currently accessing.

This is very important because without a reference, once you’ve moved away from HEAD you lose access to the HEAD node unless you keep adding another .next. But then you’ll end up with code like this:

HEAD.next.next.next.next.next... 

and who the heck knows what’s going on here or how to traverse it?

SO WHY LINKED LISTS OVER ARRAYS?

One advantage of a linked list is you can add however many elements to it that you want at computing time. In an array, you would eventually fill it up. The action of creating more space in an array is imprecise and wastes memory.

A disadvantage to this is that linked lists are not indexed. To access an array you just pass it an index and you get the value instantly. For linked lists you need to start from the HEAD and traverse every single reference node until you get to the one you need.

Timewise this would mean accessing an array index takes O(1) time while accessing a linked list node takes O(n) time.

Elements are also easily removed from a linked list whereas removing elements from an array leaves an empty space. Then you have to move every single index after the removed element over by one.

Depiction of changes to an array vs changes to a linked list.
Diagram property of InterviewBit

Basically, you should use linked lists for large datasets where the total number of entries in the list is changing. If you have smaller datasets, and you know the maximum number of items that could be on the list, then you can use an array.

CONCLUSION

Studying linked lists taught me a bunch of stuff. According to this paper from Stanford University:

“you may never use a linked list in a real program, but you are certain to use lots of pointers. Linked list problems are a nice combination of algorithms and pointer manipulation. Traditionally, linked lists have been the domain where beginning programmers get the practice to really understand pointers”.

If you remember the ‘current’ variable I discuss above you’ll agree.

Linked list data structures are sure to pop up in your life as a developer. Either at a job interview or in a real world application. Studying the strengths and weaknesses of linked lists will start you on the path to considering time, space, and code issues, which will ultimately make you a better programmer.

References

(LinkedList Basics) — Stanford University: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

(LinkedList and Node classes) — Traversy Media: https://www.youtube.com/watch?v=ZBdE8DElQQU

Github Repo For Methods— Traversy Media(https://gist.github.com/bradtraversy/c38f029e5f9e56a19c393d3a3b1e1544)

(Why Linked Lists vs Arrays) — InterviewBit: https://bit.ly/38dnL1m

--

--

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