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.
- Singly-linked lists
- Doubly-linked lists
- Circular lists
- Noncircular lists
- Lists with the heading
- Lists without the heading
- 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
- 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
The pseudocode of the many operations that we will learn is a good starting point.
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
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
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
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
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
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
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
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
Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!
Have a nice time hacking! 😊