A single linked list is a linked list in which all nodes are connected with each other in sequence. Each node of a singly linked list has two fields. The first field is used to store the data, and the second field is used to link or pointer to the next field.

The doubly linked list is also called a two-way list in which every node is divided into three fields.

1. The first field of the linked list is called the previous pointer field, which holds the address of the previous element of the list.
2. The second field of the linked list stores the information.
3. The third field of the linked list is called next pointer, which points to the next element of the linked list.

Two pointer variables are used in the doubly linked list which contains the address of the first element of the list and the last element of the list. If the previous part of the first element of the linked list remains NULL, that it indicates that there is no other node behind this node. If the next part of the last element of the linked list remains NULL,it indicates that there is no node next to it. The doubly link list can be traversed in both directions.

Suppose user wants to store integer value in linked list. For this, the doubly linked list structure must be in memory, so the structure will define.

Node Structure:

```struct node
{
int info;
struct node * prev, *next;
};  ```

### Insert a node at the beginning

This algorithm is for adding a new node at the beginning:

```Step 1: Allocate the memory for the new node.   struct node* new = malloc(size of ( struct node))
Step 3: Insert the data item into the information part of the new node.      New -> info = item
Step 4: NULL the previous part of the new node.         New -> prev = NULL
Step 5: Enter the head address in the next part of the new node.          New -> next = head
Step 6: It will check whether the head is NULL or not. If the head is NULL, then execute
step7; otherwise, it will not.
Step 7: Insert a new node in the head; therefore, the head will point to the new node.
Step 8: Enter the address of the new node in the previous part of the head.     Head -> prev = new Step9: EXIT  ```

Function:

```Insertatfirst (struct node ** head, int item)
{
struct node*new = malloc (sizeof (struct node));
new -> info = item;
new -> prev = NULL;
else
{
}
}  ```

### Traversing the Doubly Linked list

• In order Traversal: For this, the following step is followed.

Step 1: The Linked list pointer will proceed until the head is NULL.

Step 2: It will print every information part of the linked list and keep moving the head.

• Reverse Order Traversal: For this, the following step is followed.

Step 1: The Linked list pointer will proceed until the tail is NULL.

while (tail != NULL)

Step 2: It will print every information part of the linked list and keep moving the tail.

print tail -> Info

tail = tail -> next

Delete a node at the beginning

If the doubly linked list is empty, then it will return the linked list; Otherwise, we will delete the node that indicates the head pointer. For this, the following step is followed.

```Step 1: Take a temporary pointer, in which you will enter the address of the head.                     struct node *temp = head
Step 2: You will check the head is NULL or not. If the head is NULL, then it will be returned.                     if (head = = NULL)    return
Step 4: The head, which is pointing to the node, assign the NULL in its previous part.                           head -> prev = NULL
Step 5: Exit  ```

Function:

```deletefromfirst (struct node *head)
{
return;
free (temp);
}  ```

### Delete a node at the end

To delete the last node of the linked list, you will check three conditions.

• If the doubly linked list is empty, then it will return the linked list.
• If there is only one node in the linked list, you will delete it, and insert NULL in the head.
• If there is more than one item in the linked list, it will reach the last node first and then delete the last node. For this, the following step is followed.
```Step 1: Take a temporary pointer, in which you will enter the address of the head.   struct node *temp = head
Step 2: You will check the head is NULL or not. If the head is NULL, then it will be returned.                       if (head = = NULL)    return
Step 3: You will check the next node of the head is NULL or not. If the next node of the head is                     NULL, then you will repeat the steps from 4 to 6.
Step 5: Free the temporary pointer.        free(t)
Step 6: return
Step 7: You will run the temp until the next part of temp is NULL.                                             while (temp -> next == NULL)                                             temp = temp -> next
Step 8: Insert the NULL in the previous of the temp.    temp -> prev -> next = NULL
Step 9: Free the temp       free(temp)
Step 10: exit```

Function:

```deletefromlast (struct node *head)
{
struct node * temp = head;
return;
if (head -> next = = NULL)
{
free (temp);
return;
}
while (temp -> next != NULL)
temp = temp -> next;
temp -> prev -> next = NULL;
free (temp);
}```