# Algorithm and data structure [Java]: bidirectional linked list

1. When the one-way linked list needs to operate on the tail of the list, it needs to get the tail nodes through traversal, which is a waste of time
2. For programs that need to use the deleteFromTail() and addToTail() methods frequently, the program efficiency will be very low
3. The bi-directional linked list stores the nodes in front of each node. When the tail is operated, it is very convenient to obtain the node information of the tail, to operate the tail, and to greatly improve the program efficiency
4. However, double linked list stores more references of an object than single linked list, which leads to higher space complexity
Here is the Java code:

```package com.DoublyLinkedList;

//DNode Class
int length;	//Length of linked list

//Constructor
length = 0;
}

//Judge whether the list is empty
int isEmpty(){
}

//Determine whether the linked list contains a value
int contains(int value){
//Traverse the linked list to find the value
if (now.value == value)
return 1;
return 0;
}

//If the list is empty, add it directly
head = tail = new Node(value, null, null);
else
length++;
}

//Add a node to the end of the list
//If the list is empty, add it directly
head = tail = new Node(value, null, null);
else{
tail = tail.next = new Node(value, tail, null);
}
length++;
}

//Add a node to the specified subscript
//If the specified subscript is illegal, return directly
if (index > length+1 || index <= 0)	return ;
//If the list is empty and the specified subscript is not 1, return directly
return ;
//If the list is empty, you need to add a new node
head = tail = new Node(value, null, null);
}
//If the list is not empty, you need to add nodes in the header
else if (index==1)
else {
int cnt = 0;
//Find the previous node to join
for(cnt=1; cnt+1<index; cnt++)
//If a node is added after the tail, update the tail
tail = tail.next = new Node(value, tail, null);
//Otherwise, join directly
else
}
length++;
}

//Delete the first node of the linked list
Node deletedNode = null;
//If the list is empty, return directly
return -1;
//If there is only one node in the linked list, delete the node and update the head and tail
//Delete normal
else{
}
length--;
return deletedNode.value;
}

//Delete the last node of the linked list
int deleteFromTail(){
Node deletedNode = null;
//If the list is empty, return directly
return -1;
//If there is only one node in the linked list, delete the node and update the head and tail
}
//Other circumstances
else{
deletedNode = tail;
tail = tail.pre;
tail.next = null;
}
length--;
return deletedNode.value;
}

//Delete node according to given subscript
int deleteNode(int index){
//If the given index is obviously illegal, return directly
if (index<=0 || index>length)
return -1;
//Nodes to delete
//If the list is empty, return directly
if (head == null) return -1;
//If there is only one element in the linked list and other elements need to be deleted, return directly
if (head == tail && index != 1)
return -1;
//If there is only one element in the linked list and the element needs to be deleted, update the head and tail
if (head == tail && index == 1){
}
//If the chain header node needs to be deleted
else if(index == 1){
}
//If you need to delete the end node of the list
else if(index == length){
deletedNode = tail;
tail = tail.pre;
tail.next = null;
}
//Other circumstances
else{
int cnt;
deletedNode.pre.next = deletedNode.next;
deletedNode.next.pre = deletedNode.pre;
}
length--;
return deletedNode.value;
}

//Print list
//Print from front to back and from back to front to ensure that the forward and backward pointers are completely correct
void printSelf(){
System.out.print(now.value + " ");
System.out.print("]	Backside front: [");
for (Node now=tail; now!=null; now=now.pre)
System.out.print(now.value + " ");
System.out.print("]\n\t\t");
System.out.print(str);

}

//Test function
static public void main(String[] argv) {

list.deleteFromTail();list.printSelf();
list.deleteFromTail();list.printSelf();
System.out.print("\n\n");
//list.deleteNode(1);list.printSelf();
System.out.println("empty?:" + list.isEmpty());
System.out.println("123456?: " + list.contains(123456));
System.out.println("10000?: " + list.contains(10000));
}

}

//Two way linked list node class
class Node{
int value;	 	//Node data
Node pre;		//Reference to previous node
Node next;		//Reference to the next node

//Constructor 1, most commonly used
public Node(int aValue){
value = aValue;
pre = null;
next = null;
}

//Constructor 2
public Node(int aValue, Node aPre, Node aNext){
value = aValue;
pre = aPre;
next = aNext;
}
}```  79 original articles published, 53 praised, 40000 visitors+

Keywords: Java

Added by Yanayaya on Sun, 26 Jan 2020 16:45:03 +0200