 # Complete Guide To Linked Lists

Linked list is a linear data structure that means it is traversed in a specific sequence or order.
In simple words it is a list consisting of items in which each item knows the location of the next item.
A piece of list data and the location of the next item (node) is contained in an item called node. A pointer in each node determines the order of a linked list. It is only the address in memory of the next node. A linked list can be visualized as a chain of nodes where each node contains the location of the next node. Structure of a node ### Terminology

Head node: It is the first node of the linked list. Different operations can be performed on the linked list through head node. The reference of the head node of the linked list is generally known in problems.

Link: (of a node) is the location or address of the next node.

Null: The last node of the linked list points to null (none) which indicates that it is the last node.

• Unlike arrays, elements in a linked list are not stored at contiguous memory locations.
• In an array, memory is assigned during compile time while in a Linked list, memory allocation occurs during execution or runtime.

• Linked Lists addresses some of the limitations of arrays of having a fixed size because Linked Lists are dynamic in nature.This dynamic nature allows memory allocation whenever required.

Following are the types of linked list:

In a singly linked list, the node consists of one data field and one address field. Structure of a node ##### Representation of a node:
``````class Node {
int data // stores the data of the node
Node next//stores address of the next node
}
``````
##### Creating a linked list of 3 elements :
``````node *head;
node *n1 = NULL;
node *n2 = NULL;
node *n3 = NULL;

//Allocating memory
n1 = new Node();
n2 = new Node();
n3 = new Node();

// Assigning data values
n1->data = 1;
n2->data = 2;
n3->data = 3;

//Connecting nodes
n1->next = two;
n2->next = three;
n3->next = NULL;

``````

A doubly linked list is a data structure in which each node contains one data link and two link fields. Thus there is a pointer to the next as well as the previous node in a sequence. node in a doubly linked list

##### Representation of node:
``````struct node
{
int data;
node next; //reference to the next node in a sequence
node prev; //reference to the previous node in a sequence
}

`````` ##### Creating a linked list of 3 elements :
``````node *head;
node *n1 = NULL;
node *n2 = NULL;
node *n3 = NULL;

// Allocating memory
n1 = new node();
n2 = new node();
n3 = new node();

// Assigning data values
n1->data = 1;
n2->data = 2;
n3->data = 3;

// Connecting nodes
n1->next = n2;
n1->prev = NULL;

n2->next = n3;
n2->prev = n1;

n3->next = NULL;
n3->prev = n2;

`````` It is a linked list which has no null values. It can be traversed from any node and in any direction.
The pointer in the last node contains the address of the first node of the list.
In a circular linked list, there is a need to define both the head and the last(or end) node.

Structure of a circular linked list

`````` struct Node
{
int data;
node next;
};
node* head = NULL;// defining first and last node of the list
node* end = NULL;
``````

### 1. Traversing a linked list

To print the list or search for a specific node in the list, we need to go through the entire list from beginning to end.

Steps

• Go to the next node if it exists and access its information.

• Continue till the null node is reached.

Code

``````void traverse(Node* head)
{
while(temp != NULL)
{
print(temp.data)
temp = temp.next
}
}
``````

### 2. Insertion in a linked list

2.1. Insertion from front Steps

• Finding the end of the list is not required here

• If the list is empty, a new node is made as the head of the list.

• Otherwise, the new node is connected to the current head of the list.

Code

``````// returns the head of the singly linked-list
{
temp = new Node(x)//creating new node

return temp
else // insert the node at the beginning
{
return temp
}
}
``````

2.2. Insertion at the end: Steps

• Traverse the list until last node is found.
• Insert the new node to the end of the list.
• If the list is empty, return the updated head of the linked list since the inserted node is the first as well as the last node of the linked list. (only one element)

Code

``````Node insertEnd(Node head, int x)
{
if( head == NULL )//condition for empty list
{
newNode = new Node(x)
}
// traversing the list to get the last node
while( temp.next != NULL )
{
temp = temp.next
}
newNode = new Node(x)
temp.next = newNode
}
``````

2.3.Insertion at the nth position Steps

• The reference to a node is given, and the new node is inserted after the given node.
• If the address of the prevNode is not given, then it can be found by traversing to that node by finding the data value.

Code

``````void Insert(Node prevNode, int x)
{
newNode = new Node(x)

newNode.next = prevNode.next
prevNode.next = newNode
}
`````` Steps
To delete a node from a linked list, the following steps are to be followed:

• Find the previous node of the node to be deleted.
• Change the next pointer of the previous node
• Free the memory of the deleted node.
In the deletion, there is a special case in which the first node is deleted. In this, the head of the linked list must be updated.

Code

``````Node deletion(Node head, Node del)
{
{
return head.next // special case for the first Node
}

while( temp.next != NULL )
{
if(temp.next == del) // finding the node to be deleted
{
temp.next = temp.next.next
delete del // freeing the memory of that Node
}
temp = temp.next
}
}
``````

### 4. Searching

Code

``````bool search(Node head, int x)
{
Node temp = head // creating a temp variable which points to the head

while( temp != NULL) // traversing
{
if( temp.data == x )
return true
temp = temp.next
}
return false
}
``````

### 5. Updating a node

To update the value of the node, set the data part equal to the new value.

Code

``````void update(Node head, int x, int newx)
{
while(temp != NULL)
{
if( temp.data == x)
{
temp.data = newx
return
}
temp = temp.next
}
``````

## Time Complexities

Operation Time Complexity
Insert from front O(1)
Insert from back O(n)
Insert after nth position O(1)
Insert before nth position O(n)
Deletion O(n)
Find Element O(n)