DATA STRUCTURES & ALGORITHMS

Linear Linked list is the default linked list and a linear data structure in which data is not stored in contiguous memory locations but each data node is connected to the next data node via a pointer, hence forming a chain.

The element in such a linked list can be inserted in 2 ways:

- Insertion at beginning of the list.
- Insertion at the end of the list.

Hence while writing the code for Linked List we will include methods to insert or add new data elements to the linked list, both, at the beginning of the list and at the end of the list.

We will also be adding some other useful methods like:

- Checking whether Linked List is empty or not.
- Searching any data element in the Linked List
- Deleting a particular Node(data element) from the List

Before learning how we insert data and create a linked list, we must understand the components forming a linked list, and the main component is the **Node**.

A Node in a linked list holds the data value and the pointer which points to the location of the next node in the linked list.

In the picture above we have a linked list, containing 4 nodes, each node has some data(A, B, C and D) and a pointer which stores the location of the next node.

You must be wondering **why we need to store the location of the next node**. Well, because the memory locations allocated to these nodes are not contiguous hence each node should know where the next node is stored.

As the node is a combination of multiple information, hence we will be defining a class for `Node`

which will have a variable to store **data** and another variable to store the **pointer**. In C language, we create a structure using the `struct`

keyword.

```
class Node
{
public:
// our linked list will only hold int data
int data;
//pointer to the next node
node* next;
// default constructor
Node()
{
data = 0;
next = NULL;
}
// parameterised constructor
Node(int x)
{
data = x;
next = NULL;
}
}
```

We can also make the `Node`

class properties `data`

and `next`

as **private**, in that case we will need to add the getter and setter methods to access them(don't know what getter and setter methods are: Inline Functions in C++ ). You can add the getter and setter functions to the `Node`

class like this:

```
class Node
{
// our linked list will only hold int data
int data;
//pointer to the next node
node* next;
// default constructor same as above
// parameterised constructor same as above
/* getters and setters */
// get the value of data
int getData()
{
return data;
}
// to set the value for data
void setData(int x)
{
this.data = x;
}
// get the value of next pointer
node* getNext()
{
return next;
}
// to set the value for pointer
void setNext(node *n)
{
this.next = n;
}
}
```

The `Node`

class basically creates a node for the data to be included into the Linked List. Once the object for the class `Node`

is created, we use various functions to fit in that node into the Linked List.

As we are following the complete OOPS methodology, hence we will create a separate class for **Linked List**, which will have all the methods like insertion, search, deletion etc. Also, the linked list class will have a pointer called `head`

to store the location of the first node which will be added to the linked list.

```
class LinkedList
{
public:
node *head;
//declaring the functions
//function to add Node at front
int addAtFront(node *n);
//function to check whether Linked list is empty
int isEmpty();
//function to add Node at the End of list
int addAtEnd(node *n);
//function to search a value
node* search(int k);
//function to delete any Node
node* deleteNode(int x);
LinkedList()
{
head = NULL;
}
}
```

Steps to insert a Node at beginning :

- The first Node is the Head for any Linked List.
- When a new Linked List is instantiated, it just has the Head, which is Null.
- Else, the Head holds the pointer to the first Node of the List.
- When we want to add any Node at the front, we must make the head point to it.
- And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first Node of the List.
- The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.

int LinkedList ::addAtFront(node *n) { int i = 0;//making the next of the new Node point to Headn->next = head;//making the new Node as Headhead = n; i++;//returning the position where Node is addedreturn i; }

Steps to insert a Node at the end :

- If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
- If the Linked List is not empty then we find the last node, and make it' next to the new Node, hence making the new node the last Node.

int LinkedList ::addAtEnd(node *n) {//If list is emptyif(head == NULL) {//making the new Node as Headhead = n;//making the next pointe of the new Node as Nulln->next = NULL; } else {//getting the last nodenode *n2 =getLastNode(); n2->next = n; } } node* LinkedList ::getLastNode() {//creating a pointer pointing to Headnode* ptr = head;//Iterating over the list till the node whose Next pointer points to null//Return that node, because that will be the last node.while(ptr->next!=NULL) {//if Next is not Null, take the pointer one step forwardptr = ptr->next; } return ptr; }

In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the **data** of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on.

node* LinkedList ::search(int x) { node *ptr = head; while(ptr != NULL && ptr->data != x) {//until we reach the end or we find a Node with data x, we keep movingptr = ptr->next; } return ptr; }

Deleting a node can be done in many ways, like we first search the Node with **data** which we want to delete and then we delete it. In our approach, we will define a method which will take the **data** to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.

To remove any Node from the list, we need to do the following :

- If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted.
- If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.

node* LinkedList ::deleteNode(int x) {//searching the Node with data xnode *n =search(x); node *ptr = head; if(ptr == n) { ptr->next = n->next; return n; } else { while(ptr->next != n) { ptr = ptr->next; } ptr->next = n->next; return n; } }

We just need to check whether the **Head** of the List is `NULL`

or not.

int LinkedList ::isEmpty() { if(head == NULL) { return1; } else { return0; } }

Now you know a lot about how to handle List, how to traverse it, how to search an element. You can yourself try to write new methods around the List.

If you are still figuring out, how to call all these methods, then below is how your `main()`

method will look like. As we have followed OOP standards, we will create the objects of **LinkedList** class to initialize our List and then we will create objects of **Node** class whenever we want to add any new node to the List.

int main() { LinkedList L;//We will ask value from user, read the value and add the value to our Nodeint x; cout << "Please enter an integer value : "; cin >> x; Node *n1;//Creating a new node with data as xn1 = new Node(x);//Adding the node to the listL.addAtFront(n1); }

Similarly you can call any of the functions of the LinkedList class, add as many Nodes you want to your List.