# double linked list

Doubly Linked Lists are also a sequential data structure with the only difference from single linked list is that the doubly linked lists contain two pointers instead of one to store the address of both next node and previous node respectively.

*Each node contains two pointers, one pointing to the next node and the other pointing to the previous node.

*The prev of Head node is NULL, as there is no previous node of Head.

*The next of last node is NULL, as there is no node after the last node.

below is a sample of double linked list node:

c++:

struct Node { int data; struct Node* next; // Pointer to next node in DLL struct Node* prev; // Pointer to previous node in DLL };

```
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
}
```

**Advantages of doubly linked lists over singly linked list:**

**Disadvantages of doubly linked lists over singly linked list:**

```
// A linked list node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// This function prints contents of Doubly linked
// list starting from the given node
void printList(struct Node* node)
{
struct Node* last;
// Traverse the linked list in forward direction
// using the next node's pointer present
// at each node
cout<<"\nTraversal in forward direction \n";
while (node != NULL) {
cout<<node->data<<" ";
last = node;
node = node->next;
}
// Traverse the linked list in reverse direction
// starting from the last node using the previous
// node's pointer present at each node
printf("\nTraversal in reverse direction \n");
while (last != NULL) {
cout<<last->data<<" ";
last = last->prev;
} }
void append(struct Node** head_ref, int new_data) //function enters new node at the end
{
/* 1. allocate node */
Node* new_node = new Node;
struct Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
}
```

```
// A complete working Java program to demonstrate
// Doubly Linked List
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
// Add a node at the end of the list
void append(int new_data)
{
/* 1. allocate node
2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5 */
/* 3. This new node is going to be the last node, so
make next of it as NULL */
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// This function prints contents of linked list
// starting from the given node
public void printlist(Node node)
{
Node last = null;
// Traverse the linked list in forward direction
// using the next node's pointer present
// at each node
System.out.println("Traversal in forward Direction");
while (node != null) {
System.out.print(node.data + " ");
last = node;
node = node.next;
}
System.out.println();
// Traverse the linked list in reverse direction
// starting from the last node using the previous
// node's pointer present at each node
System.out.println("Traversal in reverse direction");
while (last != null) {
System.out.print(last.data + " ");
last = last.prev;
}
}
```