Table Of Contents
* 🤓 INTRODUCTION
* ❔ ABOUT LINKED LISTS
* 1️⃣SINGLY-LINKED LIST
* 👨🏻🔬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:
Article No Longer Available
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, Instagram or LinkedIn
❔ ABOUT LINKED LISTS
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
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
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
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
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.
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
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
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.
🙏 THANK YOU FOR READING!
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!
Have a nice time hacking! 😊
Top comments (0)