Question
Program to insert elements in Doubly-Linked List and Display them.
— Submitted By Ubaid Ahmad
What is doubly Linked List?
 A doubly linked list is a linear collection of nodes, which can be traversed from either side, i.e. from left to right and from right to left.
Everything in this is the same as a singly linked list, the only difference being we can also traverse from right to left.
Â
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
Advantages over arrays
1) Dynamic sizeÂ
2) Ease of insertion/deletion
Drawbacks:Â
1) Random access is not allowed. We have to access elements sequentially starting from the first node(head node). So we cannot do binary search with linked lists efficiently with its default implementation. Read about it here.Â
2) Extra memory space for a pointer is required with each element of the list.Â
3) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.
Share code with your friends
Share on whatsapp
Share on facebook
Share on twitter
Share on telegram
Code
public class DoublyLinkedList
{
class Node
{
int data;
Node next;
Node previous;
public Node(int data)
{
this.data = data;
}
}
// creating the head of the linkedlist. This represents the first node of the
// list.
public Node head = null;
public Node tail = null;
// adds node to the front of the list
public void insertFront(int data)
{
Node newNode = new Node(data); // creates a new node and fills it data attribute by the value passed.
// if the linkedlist is empty we make the head and tail equal to the node we
// created
if (head == null)
{
head = tail = newNode;
newNode.next = newNode.previous = null;
return;
}
// if the list is not empty we add the node to the front of the list and make it
// the new head
newNode.next = head;
newNode.previous = null;
head.previous = newNode;
head = newNode;
}
// adds a node to the end of the list
public void insertLast(int data)
{
Node newNode = new Node(data);
// if linkedlist is empty
if (head == null)
{
newNode.previous = newNode.next = null;
head = tail = newNode;
return;
}
// if the list is not empty we simply add the node at the end of the list
newNode.previous = tail;
tail.next = newNode;
tail = newNode;
}
// printing the linkedlist
public void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// printing the linkedlist in reverse order
public void printListReverse()
{
Node temp = tail;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.previous;
}
System.out.println();
}
public static void main(String[] args)
{
// creating a SinglyLinkedList object names linkedList to represent the
// linkedlist
DoublyLinkedList linkedList = new DoublyLinkedList();
// inserting elements
linkedList.insertFront(1);
linkedList.insertFront(2);
linkedList.insertFront(3);
linkedList.insertFront(4);
linkedList.insertFront(10);
linkedList.insertLast(50);
linkedList.insertLast(4);
linkedList.insertLast(3);
linkedList.insertLast(30);
linkedList.insertLast(1);
// prints the linkedlist
linkedList.printList();
linkedList.printListReverse();
}
}
Coding Store
Code Explanation
class Node
{
int data;
Node next;
Node previous;
public Node(int data)
{
this.data = data;
}
}
Since we are making a doubly-linked list, we take a class called DoublyLinkedList and make a nested class Node in it. This nested class will have three attributes
Node next : to store the location of the next node
Node previous: to store the location of the previous nodeint data: to store the data of the current node.
In the node class, we make a constructor that will be used when we instantiate the objects.
public void insertFront(int data)
{
Node newNode = new Node(data); // creates a new node and fills it data attribute by the value passed.
// if the linkedlist is empty we make the head and tail equal to the node we
// created
if (head == null)
{
head = tail = newNode;
newNode.next = newNode.previous = null;
return;
}
// if the list is not empty we add the node to the front of the list and make it
// the new head
newNode.next = head;
newNode.previous = null;
head.previous = newNode;
head = newNode;
}
Now, in the DoublyLinkedList class, we make a function that will add the nodes at the front
insertFront(int):
The insertLast function accepts the data to be inserted as an argument and makes an object of class Node.
Now there are two scenarios-
The LinkedList is empty:
If it is empty, then we make the new node as the head and tail node and exit from the function
Â
The LinkedList has nodes:
If the list is not empty, make this node point to the head node and then make the head node the new node.
// adds a node to the end of the list
public void insertLast(int data)
{
Node newNode = new Node(data);
// if linkedlist is empty
if (head == null)
{
newNode.previous = newNode.next = null;
head = tail = newNode;
return;
}
// if the list is not empty we simply add the node at the end of the list
newNode.previous = tail;
tail.next = newNode;
tail = newNode;
}
And one to insert at the end of the list.
insertLast(int):
The insertLast function accepts the data to be inserted as an argument and makes an object of class Node.
Now there are two scenarios-
The LinkedList is empty:
If it is empty, then we make the new node as the head and tail node and exit from the function
The LinkedList has nodes:
If the list is not empty, make the tail point to this node and then make this node as the tail of the list.
// printing the linkedlist
public void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
printList():
In this function, we just traverse till the end of the list and keep on printing the data field of each object.
// printing the linkedlist in reverse order
public void printListReverse()
{
Node temp = tail;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.previous;
}
System.out.println();
}
printListReverse():
In this function, we just traverse till the start of the list and keep on printing the data field of each object.
public static void main(String[] args)
{
// creating a SinglyLinkedList object names linkedList to represent the
// linkedlist
DoublyLinkedList linkedList = new DoublyLinkedList();
// inserting elements
linkedList.insertFront(1);
linkedList.insertFront(2);
linkedList.insertFront(3);
linkedList.insertFront(4);
linkedList.insertFront(10);
linkedList.insertLast(50);
linkedList.insertLast(4);
linkedList.insertLast(3);
linkedList.insertLast(30);
linkedList.insertLast(1);
// prints the linkedlist
linkedList.printList();
linkedList.printListReverse();
}
