Elementary Data Structures with JavaScript - Linked Lists - PART 1🚀
Tags: javascript, programming, codequality, webdev
Published: 2021-02-10 18:56:52

Table Of Contents
        * 🤓 [INTRODUCTION](#intro)
        * ❔ [ABOUT LINKED LISTS](#about)
        * 1️⃣[SINGLY-LINKED LIST](#singly)
        * 👨🏻‍🔬[OPERATIONS](#operations)
        * 🖖🏻[PSEUDOCODES](#pseudo)
        * 🙏 [THANK YOU](#thank-you)


## 🤓 INTRODUCTION <a name="intro"></a>

Welcome, my dear code-dudes and code-dudettes!🚀 Welcome to yet another blog article about elementary data structures. 

If you missed the previous article you can check it out here:


{% link https://dev.to/codespresso/elementary-data-structures-with-javascript-stacks-10no %}

Today, we are going to discuss a new data structure called **Linked Lists**. Because the topic of the linked list has many operations that we need to explain and understand through simple English words and pseudocode, this is going to be a two-part article so that you can enjoy it and not find it overwhelming.

Also, please feel free to connect with me via [Twitter](https://twitter.com/lazar_dev), [Instagram](https://www.instagram.com/codespressoweb/) or [LinkedIn](https://www.linkedin.com/in/lazar-stankovic-44a199177/)

![linked](https://media.giphy.com/media/QvXe5wq8w94A0/giphy.gif)


## ❔ ABOUT LINKED LISTS <a name="about"></a>
A **linked list** is a data structure in which the objects are arranged in a linear order. But, online an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets.

The **size** of the list is the number of elements in the list.
A list can be a sorted list or an unsorted list.

### LINKED LIST TYPES
- Singly-linked lists
- Doubly-linked lists
- Circular lists
- Noncircular lists
- Lists with the heading
- Lists without the heading
- Sorted lists
- Unsorted lists


## 1️⃣ SINGLY-LINKED LIST<a name="singly"></a>
This type of a linked list is a data structure that contains a sequence of **nodes**. Each **node** has two fields: **info** and **link**. 

An info field - remembers an element of a list or an address of an element of a list
A link field - remembers an address of the next node in the list


## 👨🏻‍🔬 OPERATIONS <a name="operations"></a>
- Traversal
- Finding an element in the list
- Adding a node to the list
- Deleting a node from the list
- Deleting the list
- Copying the list
- Concatenating the list


## 🖖🏻 PSEUDOCODES <a name="pseudo"></a>
The pseudocode of the many operations that we will learn is a good starting point.

### TRAVERSAL
This algorithm goes through the list on every element
It applies an operation "PROCESSING"
A pointer POINT always points to the node that will get processed next
```pseudocode

1 POINT => START //POINT - the first element in the list
2 while(POINT is not NULL)
3    PROCESS(info(node)) //do what ever you want with the info
4    POINT => link(POINT) //set point the the next element stored 
5                          //in the link field
6 endwhile
7 exit
```

### SEARCH NON SORTED LIST
This algorithm will search an element E in an unsorted linked list, and it will return the location of an element is found
LOC = NULL (location is NULL) if search failed

```pseudocode
1 POK => START
2 while (POK is not NULL AND info(POK) is not someValue)
3    POK => link(POK) //go to the next element in the list
4 endwhile
5 if info(POK) is equal to someValue
6 then
7    LOC => POK //Success
8 else
9    LOC => NULL //Element not found
10 exit procedure
```

### SEARCH SORTED LIST
This algorithm will search an element E in a sorted linked list, and it will return the location of an element is found
LOC = NULL (location is NULL) if search failed

```pseudocode
1 POK => START
2 while(POK is not NULL)
3    if (info(POK) is equal to someValue)
4       LOC => POK
5       exit procedure //element found
6    else if (someValue is less than info(POK)) then
7       LOC => NULL
8       exit procedure //element not found
9    else
10      POK => link(POK) //go to the next element
11   endif
12 endwhile
13 LOC => NULL
14 exit procedure
```

### INSERT AT THE START OF THE LIST
This algorithm will insert an element E at the start of the linked list.
```pseudocode
1 new => getNode()  //Get a new empty node
2 info(new) = E  //write element into our newly created node
3 link(new) => START  //connect a new node
4 START => new
5 exit procedure
```

### INSERT IN THE SPECIFIC LOCATION IN THE LIST
This algorithm will insert an element E behind the node LOC. If LOC is null, E is inserted as a first element in the list.
```pseudocode
1 new => getNode() //get a new empty node
2 info(new) => E  //populate our new node
3 if(LOC=null) then
4    link(new) => START
5    START => new  //E is inserted as a new Node
6 else
7    link(new) => link(LOC)
8    link(LOC) => new   //E is inserted after the node LOC
9 exit procedure
```

### INSERT INTO SORTED LIST
This algorithm will insert an element E into a sorted linked list
```pseudocode
1 call findA(start, E, loc) //find the location of the node that 
2                          //precedes node E
3 call insertAfterLoc(start, E, loc) //insert E after node loc
4 exit procedure
```

### INSERT INTO SORTED LIST METHOD "findA"
This algorithm finds a location LOC of the last node in the sorted list that has info(LOC) less than E, Or it returns LOC is null if a search fails.
```pseudocode
1 if (START is null) then
2   LOC => null
3   return      //Empty list
4 if (E < info(START)) then
5   LOC => null
6   return   //borderline case
7 spoint => START //start pointer
8 npoint => link(START) //next pointer
9 while (point is not NULL)
10   if (E less than info(npoint)) then
11      LOC => spoint
12      return
13   spoint => npoint
14   npoint => link(npoint)   //updating indexes
15 endwhile
16 LOC => spoint
17 return
```

### DELETING FROM THE BEGINNING OF THE LIST
This algorithm will delete an element E from the beginning of the linked list
```pseudocode
1 point => START //set the pointer to the beginning of the list
2 START => link(point) //change the beginning of the list
3 E => info(point)  // read the value of an element E
4 freenode(point)   //free the node
5 exit procedure    //end of an algorithm
```

It's quite a bit, right? 😲 Yes, so for that reason I encourage you to sit and analyze these pseudocodes before we continue to an actual **JavaScript** code implementation. Try going step by step and understanding what every pseudocode does, remember this is just an abstraction but we will get into serious JavaScript coding in the next part of this article.

# 🙏 THANK YOU FOR READING!<a name="thank-you"></a>
References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me! 

☕ SUPPORT ME AND KEEP ME FOCUSED!
<a href='https://ko-fi.com/Z8Z33D1HJ' target='_blank'><img height='36' style='border:0px;height:36px;' src='https://cdn.ko-fi.com/cdn/kofi4.png?v=2' border='0' alt='Buy Me a Coffee at ko-fi.com' /></a>

Have a nice time hacking! 😊