Doubly linked list is a variation of linked list. Each node has references to the previous and next node. You can define both head and tail nodes, thus allowing the traversal in a bi-directional fashion. Java API LinkedList is implemented as doubly linked list. Please note that reference and pointer can be used interchangeably here.

Table of Content


Define classes

The Node class has three variables: data stores the value, next is the reference to the next node, and prev is the reference to the previous node. DoublyLinkList class has variables of head, tail and length. The head always points to the first node. The tail always points to the last node. The length keeps track of number of nodes in the list.

Java

Javascript

Python


Add element

InsertFirst: To add an element, create a new node with the value first. When add a node at the front, the next pointer points to head first. Then move the head to the new node.

Java

Javascript

Python

Doodle

doubly linked list insert first

InsertLast: when adding a node at the end, the new node’s prev pointer points to the tail first. Then move the tail to the new node.

Java

Javascript

Python

Doodle

doubly linked list insert last


Delete element

DeleteFirst: To delete element at the front, you have to check three cases: the list is empty, the list has one node, in which head and front point to the same node; or list has more than one node.

Java

Javascript

Python

Doodle

doubly linked list delete first

DeleteLast: The same as deleting an element at front, to delete an element at the end, you have to consider three situations, and move the head and tail pointers accordingly.

Java

Javascript

Python

Doodle

doubly linked list delete last

Delete by key: To delete an element by the key, it is easier to define a method to delete node first. To delete a node, you have to set the next and prev from both side. To delete the key, starting from the head, compare each node’s value with the key. If the data is not equal to the key, move to the next node. Repeat until you find the node with the value the same as the key. Backup the node’s next to next variable. Delete the node and assign the next to the current node.

Java

Javascript

Python

Doodle

double linked list delete


Search by key

In doubly linked list, to search by key is the same as search in linked list. Assign the current node reference to head. Compare the data with the key. If they are not equal, move the reference to the next node. Repeat until you find the node with value the same as the key. Return this node. If no node is found when the reference reaches the end, return null.

Java

Javascript

Python

Doodle

doubly linked list search


Print elements

To print doubly linked list, you shall print forward and backward. First starting from the head, print the value of each node, then move to its next node. Repeat until you reach the end. Next starting from the tail, print each node, and move to its prev node. Repeat until you reach the head.

Java

Javascript

Python

Doodle

double linked list print

Download Java, JavaScript and Python code
Doubly linked list animated
Data structures and Java collections