# Doubly Linked List Data Structures & Algorithms

In our previous article you have seen Double-ended Linked List. Doubly linked list is another variation of Linked Lists and don’t confuse with double-ended list.

An important problem that doubly linked list solves is it provides a way to traverse backward in the list, whereas with the ordinary linked lists it is difficult to traverse backward along the list. This limitation is overcome by doubly linked list.

## Supported Operations

• insertFirst() – insert at front of the list
• insertLast() – insert at end of the list
• insertAfter() – insert data after the specified key
• deleteFirst() – delete first link
• deleteLast() – delete last link
• deleteKey() – delete link based on the key provided

A doubly linked list need not be double-ended linked list (keep a reference to the last element in the list) necessarily. But in our example below we will include reference to the last element also.

```package com.sneppets.dsalgo;

/**
*/

{
//data
public int intData;

//constructor
{
intData = iData;
}

{
System.out.print(intData + " ");
}
}

{

{
//no items on the list yet
first = null;
last = null;
}

//return true if there are no links
public boolean isEmpty()
{
return (first == null);
}

//insert at front of the list
public void insertFirst(int iData)
{
if(isEmpty())
{
//if list is empty last --> newLink
}
else
{
}
}

//insert at end of the list
public void insertLast(int iData)
{
if(isEmpty())
{
//if list is empty first --> newLink
}
else
{
}
}

//insert iData after key
public boolean insertAfter(int key, int iData)
{
//start from first/begining
//until match is found
{
{
return false;
}
}
{
}
else
{
}
return true;
}

{
//check if only one item is there in the list
if(first.next == null)
{
last = null;
}
else
{
//old next --> null
first.next.prev = null;
}
//first --> old next
first = first.next;
return temp;
}

{
//check if only one item is there in the list
if(first.next == null)
{
first = null;
}
else
{
//old previous --> null
last.prev.next = null;
}
//last --> old prev
last = last.prev;
return temp;
}

//delete based on the provided key
{
//start at the beginning
//until match is found
{
{
return null;
}
}
//match is found; is that first item in the list ?
{
}
else
{
}
//match is found; is that last item in the list ?
{
}
else
{
}
}

//display items in the list starting from first to last
public void displayForward()
{
System.out.println("displayForward(): List from first to last :");
//start at the beginning
//until you reach end of the list
{
}
System.out.println(" ");
}

//display items in the list starting from last to first
public void displayBackward()
{
System.out.println("displayBackward(): List from last to first :");
//start from last
//until you reach start of the list
{
}
System.out.println(" ");
}

}

public static void main (String[] args)
{
//insert at front
//insert at end
//display list forward
//display list backward

//delete one last item and one first item

//display list forward

//insert again "10" after "20"

//display list forward

}

}
```

Output

```displayForward(): List from first to last :
70 50 20 10 30 60
displayBackward(): List from last to first :
60 30 10 20 50 70
displayForward(): List from first to last :
50 20 30
displayForward(): List from first to last :
50 20 10 30
```

## Drawback of doubly linked list

Every time you insert or delete a link you must deal with four links instead of two since each link has extra reference.

Subscribe
Notify of