devlazar

Posted on

# Elementary Data Structures with JavaScript - Linked Lists - PART 1π

* π€ INTRODUCTION
* π¨π»βπ¬OPERATIONS
* ππ»PSEUDOCODES
* π THANK YOU

## π€ INTRODUCTION

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:

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.

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.

• Circular lists
• Noncircular lists
• Sorted lists
• Unsorted lists

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

• 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

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

``````
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
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

``````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
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

``````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
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.

``````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.

``````1 new => getNode() //get a new empty node
2 info(new) => E  //populate our new node
3 if(LOC=null) then
5    START => new  //E is inserted as a new Node
6 else
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

``````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.

``````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

``````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.

References:
School notes...
School books...