I became inquisitive and at the same time enthusiastic, i really needed to know and understand what Data structure and Algorithms are all about. Recently, i tweeted that, the concept of linked list was confusing to me because i couldn't really wrap my head around it or understood what the heck was node and what the next one might be. it turns out that a comical video made by @theannalytical opened my eyes and i saw the light :-).
In this write up i am going to explain how i finally knitted the whole parts together. To give it a real life application or say use case scenario, would be using a music player that contains and plays several songs, so the songs represent the nodes while the music player is the Linked List. so we would be using the music player as an example to represent the real life scenario of the term, Linked List.
So we will progress by talking about:
- What is Linked List
- What are nodes and why are we linking them
- Implement the music player Linked List
- Conclusion
- References and credit
what is a Linked List
it is a sequential collection of elements, each element is called a node. Each node has two key important information in it; a key that points to the value of the node and the other key pointing to the next node. on the other hand, the linked list has a head and a tail node, i.e representing the first and last element amidst intermediate nodes chained together by links. the head node points to the second node that points to the third node that point to the tail that points to null indicating the end of the list. There are three (3) type of linked list:
- Single Linked List: Has one pointer to the next node
- Doubly Linked List: has pointer to the next node and another pointer to the previous node
- Circular Linked List: Has the tail node points to the head node
For our example of the music player list, the circular type of the linked list fits perfectly into the model whereby the last song in the player list can point to the first song in the list. The linked list is used to store data just as the the arrays. It is language agnostic meaning it can be implemented in just about every other programming language.
Choosing the Linked List over regular arrays is a matter of choice on how they are accessed and stored in memory. Each data structure object has its unique use cases. unlike arrays, linked list are stored in memory in a sequential manner at anywhere in memory which is why you can't use an index to access the items in the list, you would need to traverse the list starting from the head to the tail until you find the item you are looking for, but with arrays, it is allocated a contiguous block of memory where each item in the array is located next to each other which is why you can access any item in the array by simply using the index.
Because of this, you can't jump to any position in the linked list collection, you have to step through each item in the list to get to the position you want. That explains why, for a music player, to select a song we have to trigger next action, till we get to the song we want. This is a drawback for Linked list compared to arrays, however, because items can be stored anywhere in memory, adding and removing items is much faster than the arrays.
While Linked List might really be bad at direct access to items, it really does shine in inserting and removing items in the list.
What are nodes and why are we linking them
So far, we have been using the music player as our example, to define node will be the same thing as saying the song in the player list that represents and explains a typical example of a node. it is an object that contains properties, in this case, a track of a song as its current value and a property that points to the song in the list.
Each song will represent our node object. so we can just keep adding songs as long the memory permits or we can choose to remove songs from the list.
Implement the music player Linked List
without much ado, let's now implement the Music Player Linked List whereby we can add song to the end of the list or to the beginning of the list, or we can delete the first song in the list or delete the last. we can even delete the song in the middle of the list and search for songs in the list.
//lets first of all create the song
class SongNode {
constructor(song, nextSong, previousSong){
this.song = song;
this.nextSong = nextSong;
this,previousSong = previousSong
}
}
class MusicPlayerLinkedList{
constructor(){
/*linkedlist contains two key important properties,
the head node and tail node, so we assume its empty
when we initialize it*/
this.head = this.tail = null;
}
//let add a new song list
addNewSongAtTheEnd(song){
//check for the last song in the list
if(!this.tail){
//if it is empty, assign the new song to both the head node
//and tail
this.head = this.tail = new SongNode(song);
}else{
//if not, that means there is a last song
//which might also be the only song in the list
//so we keep track of it
let currentSong = this.tail;
//now new song to be added
this.tail = new SongNode(node);
//since the current song exists point its next node to the new song added
currentSong.nextSong = this.tail;
//and the new song previous song property should point to the current song
this.tail.previousSong = currentSong
}
}
//lets add another new song but this time at the beginning of the list
addNewSongAtTheStart(song){
if(!this.head){
this.head = this.tail = new SongNode(node);
}else{
let currentSong = this.head;
this.head = new SongNode(node);
currentSong.previousSong = this.head;
this.head.nextSong = currentSong
}
}
//delete the first song in the list\
deleteFirstSong(){
if(!this.head){
return null;
}else{
//track the song you are deleting
const songTobeDeleted = this.head;
if(this.head === this.tail){
this.head = this.tail = null;
}else{
this.head = this.head.nextSong;
this.head.previousSong = null
}
}
return songToBeDeleted.song
}
//delete the last song in the list\
deleteFirstSong(){
if(!this.tail){
return null;
}else{
//track the song you are deleting
const songTobeDeleted = this.tail;
if(this.head === this.tail){
this.head = this.tail = null;
}else{
this.tail = this.head.previousSong;
this.tail.nextgSong = null
}
}
return songToBeDeleted.song
}
//search for songs in the list
searchSong(song){
let currentSong = this.head;
if(currentSong.song === song){
return currentSong;
}
currentSong = currentSong.nextSong
return null;
}
}
Conclustion
The knowledge of data structure and algorithms are very vital to a developers' journey in the dev community. Apart from the seemingly super power you would possess, it will also allow you to write performant code that are fast and that solves business needs speedly. The step i took was to identify the node and what is the meaning of it, in this case the track of song which is just a JavaScript class or any other programming language class construct that contains properties that includes: the track of song, the pointer to the previous song, if there is none, it will return null and a pointer the the next song, if it is empty, it will return null.
it is usually difficult most times for developers to wrap their head around the concept of data structure and algorithm, it is even more challenging when you try to understand other types of data structures other than linked list and try to make sense of why you might need them in practice. the music player example clearly demonstrates that data structure knowledge is key, if not how would you store the data we are constantly collecting from different sources and how do we arrange it in memory to be able to guarantee unlimited and quick accessibility.
I plan to write on other data structures and also follow it up with algorithms. you can follow me @ibearua on twitter to get notifications when i publish the other articles.