Linked List

Linked List:

So far, we have studied arrays and pointers. We see, whenever we make an arrays we have to declare its size. i.e my_array[10] or some thing like my_array[10][10] (2D array). We solve this problem by using pointers. We used to ask size of array from user and then, make dynamic memory of that size. We did something like int* my_array = new int[size]. Where size is given by user. Now let discuss what is its demerit of using this process of creating dynamic memory. Let say, user want to make array of size 20. Using dynamic memory we will create array of size 20 easily, but now let say, user wants to add one more item to this array. i.e he/ she wants to grow this array. What we can do using this strategy, we will make an array of size 21 or more then, transfer the data of previous array the delete the previous array. What's wrong with using this type of implementation? Lets consider, we have made an array of size 10,000,000. Now we want to grow this array to 10,000,001. Using the above implementation will take very long time to grow this array, because we need to copy data from old array of size 10,000,000 to new array of size 10,000,001 which require much time. Now here, comes the use and requirement of Linked List.

One more thing, I want to add is that, when we allocate memory using 'new', we get contiguous memory. For example, if we want to get dynamic memory of size 100, we will get a block of memory of size 100. The memory slots will be adjacent to each other. Lets take an example to understand this:


                       int* my_array  =  new int[100]; 


 Memory will be allocated from 0th index to 99th index


                       array[0]     . . . .      array[50]    . . . . .    array[99]

                            ðŸ‘†                           ðŸ‘†                              👆

                         0x0100                     0x0104                     0x0108

                        Gap of 4 bytes. As size of int is 4 bytes

Using linked list, we do not get contiguous memory, we only keep track of the address where our data is stores. Lets take an example to understand this:


                          data1               data2                  data3

                           ðŸ‘†                    👆                       ðŸ‘†

                       0x0186              0x6123               0x9715

                           ðŸ‘†                    👆                       ðŸ‘†

                   we store their addresses to keep track of our data.

Above is the data and below is their addresses, we see clearly, our data is stored at random addresses and we will just keep the track of that addresses.


Basic Idea:

The basic idea and concept of linked list is to solve the above mentioned problem and to grow any array in O(1) time. If we have an array of size 10,000,000 and we want to grow it to 10,000,001 we will be able to do this in just O(1) time.


Hope so, you have read the above article carefully, and you are familiar with the need, importance and advantages of using Linked List.

Now wee will see its implementation.


Implementation:

We make two classes, first class is Node class and the second class is Linked_list class.

Node class:

Node class is basically, used to store data. Generally, it includes data of any type int, char, float or any other user defined class type and a pointer of type Node(itself).

Here is the code for Node class. We have made it template class to make it generic.

Code:

template<typename T>

class Node

{

T data;                                                                     //  data

Node* nextptr;                                                       //  pointer to next data

public:

template <class x>friend class List;                     // make List class friend of Node class

Node()                                                                   //  default constructor

{

nextptr = nullptr;

}

Node(T data, Node* ptr = 0)                                //  parameterized constructor

{

this->data = data;

nextptr = ptr;

}

~Node()                                                                //  destructor

{

}


};


Linked List Class:

The linked list class provide functionalities to user like add data to list, remove data from list, update any data from list. Linked list class uses Node class to perform these functionalities.

Linked list class generally have two pointer of type Node. One is often called as head and the second is often called as tail. Head stores the starting Node of the list and tail stores the ending address of the Node.

Here is the code for List class.

Code:


template<typename T>
class List
{
Node<T>* head;                        // stating node of the list
Node<T>* tail;                        // ending node of the list

public:
List()                               // default constructor 
{
head = nullptr;
tail = nullptr;
}
void insertAtStart(T const element)      // insert data at the start of the list
{
if (head == tail && tail == nullptr)   // if the list is empty. head and tail will be at same node
{
head = new Node<T>(element);
tail = head;
}
else
{
Node<T>* temp = new Node<T>(element);    // list contains one or more Node
temp->nextptr = head;
head = temp;
}
}
void insertAtEnd(T const element)         // insert data at the end of the list
{
if (head == tail && tail == nullptr)    // if the list is empty. head and tail will be at same node
{
head = new Node<T>(element);
tail = head;
}
else
{
Node<T>* temp = new Node<T>(element);    // list is not empty
tail->nextptr = temp;
tail = tail->nextptr;
}
}
void print() const                    // print all the data in the list
{
for (Node<T>* temp = head; temp != nullptr; temp = temp->nextptr)  // starting from the head and end at tail
{
cout << temp->data << "   ";
}
cout << endl;
}
bool search(T const& element) const         // search for any data in the list
{
for (Node<T>* temp = head; temp != nullptr; temp = temp->nextptr)  // starting from the head and end at tail if element(data not found)
{
if (temp->data == element)
return true;
}
return false;
}
bool insertAfter(T const v1, T const v2)      // insert data v1 after data v2
{
Node<T>* temp = head;
bool val = false;
for (; temp->data != v2 && temp->nextptr != nullptr; temp = temp->nextptr)   // starting from the head and end before the node which contain v1(if present otherwise run till tail)
{
if (temp->nextptr->data == v2)
val = true;
}
if (val)                                                // if found
{
Node<T>* temp2 = temp->nextptr;
temp->nextptr = new Node<T>(v1, temp2);
}
return val;
}
void deleteFromStart()               // delete teh data which is in the start of the list
{
if (head == tail && tail != nullptr)        // only one element in the list
{
delete head;
head = tail = nullptr;
}
else                                             // more than onr elements in the list
{
Node<T>* temp = head;
head = head->nextptr;
delete temp;
temp = nullptr;
}

}
void DeleteAtEnd()                        // delete the data which is at the end of the list
{
if (head == tail && tail != nullptr)        // only one element in the list
{
delete head;
head = tail = nullptr;
}
else                                     // more than onr elements in the list
{
Node<T>* temp = head;
for (; temp->nextptr->nextptr != nullptr; temp = temp->nextptr);
Node<T>* temp2 = temp->nextptr;
delete temp2;
temp2 = nullptr;
temp->nextptr = nullptr;
}
}
void deleteValue(T v1)                // delete the data v1 (if present in the list) from the list
{
bool val = false;
if (head == tail && tail != nullptr && head->data == v1)           // only one element in the list and that element is v1.
{
delete head;
head = tail = nullptr;
}
else                                  // more than onr elements in the list
{
Node<T>* temp = head;
for (; temp->nextptr->data != v1 && temp->nextptr != nullptr; temp = temp->nextptr)
{
if (temp->nextptr->nextptr->data == v1)
val = true;
}
if (val)
{
Node<T>* temp2 = temp->nextptr;
temp->nextptr = temp2->nextptr;
delete temp2;
temp2 = nullptr;
}
}
}
~List()                             // destructor
{
Node<T>* temp = head;
while (temp != nullptr)           // staring from head delete one by one all data till tail
{
head = head->nextptr;
delete temp;
temp=head ;
}
head = nullptr;
      }


};

Happy coding.😊

Comments

Post a Comment

Feel free to comment or ask something related to games.

Popular posts from this blog

Community Detection Algorithm (Leiden Algorithm in Python)

Community Detection Algorithm (Leiden Algorithm in Python) The Leiden algorithm is a powerful community detection algorithm that is based on the concept of modularity. It is an improvement over the Louvain algorithm, which is a popular algorithm for community detection. The Leiden algorithm is able to identify communities of different sizes and densities and is able to identify overlapping communities. The first step in the Leiden algorithm is to initialize the communities. This can be done randomly or by using some other method. The next step is to calculate the modularity of the network. The modularity is a measure of the density of links within a community compared to links between communities. The higher the modularity, the better the clustering of the network. Once the modularity is calculated, the Leiden algorithm then proceeds to optimize the clustering. It does this by moving nodes between communities in a way that increases the modularity. The algorithm repeats this process un...
Read more

Stack and Queues

Image
What is Stack? The basis of stack is first in last out(FILO) Or last in first out (LIFO). To understand stack, consider example of plats. We place plats one over another. Let say we have 5 plats, named as p1, p2, p3, p4, and p5. Assume they are arranged in such a way that p2 is placed on p1, p3 is placed on p2, p4 on p3, and p5 on p4. As shown in the diagram.   Now you are clear with, what is stack. Now we will see where it is used and how we implement stack in c plus plus programming language. Why Stack? We see the functionality of forward and backward operations in our browsers. Similarly, we see functionalities like undo, redo in our text editor or any application like photo editors. The functionality of undo, redo is very common. It is used in many applications like in word, excel, photoshop, browsers, paint, and many other applications. Now if we think about what will be the best way to implement undo, redo functionality in our application, we will see the best data structure ...
Read more

How To Earn Money Online

 There are different ways through which you can earn money online with out any investment. Here, I will discuss almost all the possible ways through which you can earn money online. Here, list of different methods of earning money online along with their introduction is given below: 1) Earn money through YouTube channel: As you all knows that the world is moving towards digital media. The people prefer everything on their mobile phone. The trend of watching cable Television and cable channels are reducing day by day. Now a days, it is good to launch a YouTube channel and earn money through it. It is very simple to create a YouTube channel. If you have G-mail account, you can make your YouTube channel through it. It will take almost 2-3 months hard work to make your YouTube channel successful. Now, I will also tell you how to make your YouTube channel successful. First thing that you should know is video editing. There are a lot of software like adobe which will help you in this reg...
Read more