Doubly Linked List Program in Java

2025年3月28日 | 阅读 12 分钟

双向链表程序非常复杂，因为双向链表的节点包含两个字段：前一个节点（previous）和后一个节点（next）。在 C 和 C++ 中，使用指针维护双向链表非常容易，但在 Java 中，没有指针的概念，这使得它的构建有点棘手。双向链表程序可以涉及创建双向链表、插入节点或删除节点。

让我们来理解一些双向链表的基本程序

创建双向链表

要创建节点，我们需要创建一个类来创建节点类型。该类包含三个属性，即 data、prev 和 next。数据可以是 int、String 或 float 类型，而 prev 和 next 是 Node 类型。用户存储信息，prev 和 next 指向双向链表中前一个和后一个节点。在给定的程序中，每一行代码都通过注释进行定义，以便您可以轻松理解代码。

CreateDoublyLinkedList.java

public class CreateDoublyLinkedList {  

	//Create a node for doubly linked list  
	class Node{  
		String data;  
		Node prev;  
		Node next;  

		public Node(String data) {  
			this.data = data;  
		}  
	}  

	//Initialize head and tail for the doubly linked list  
	Node head = null;
	Node tail = null;  

	//Create addNewNode() method to add a node into a list 
	public void addNewNode(String data) {  

		//Create node  
		Node newNode = new Node(data);  

		//Check whether our doubly linked list is empty or not 
		if(head == null) {
			//The newNode is pointed by both head or tail 
			head = newNode;
			tail = newNode;
			//It is first node so prev will point to null  
			head.prev = null;  
			//It is also last node so tail's next will point to null  
			tail.next = null;  
		}
		//Execute when the doubly linked list is not empty
		else {  

			//The newly created node will be the last node, so now tail's next will point to that newly created node
			tail.next = newNode;  
			//The tail is pointing to the second last node so the newly created node's prev will point to tail  
			newNode.prev = tail;  
			//The newly created node will become new tail because it is last node in the doubly linked list 
			tail = newNode;  
			//The newly created node will be the last node so tail's next will be null  
			tail.next = null;  
		}  
	}  

	//Create showData() method for displaying data of doubly linked list  
	public void showData() {
		//intialize a new node current that will point to head  
		Node current = head;  
		//Check whether the doubly linked list is empty or not
		if(head == null) {
			//Print a statement and pass the control flow into the main() method
			System.out.println("List is empty");  
			return;  
		}
		//Print a statement
		System.out.println("Nodes of doubly linked list: ");  
		//Iterate the doubly linked list using while
		while(current != null) {  
			//Print tha data on that particular node and then increment the pointer for indicating next node  
			System.out.print(current.data + "\n");  
			current = current.next;  
		}  
	}  

	public static void main(String[] args) {  

		CreateDoublyLinkedList obj = new CreateDoublyLinkedList();  

		//Add nodes into the doubly linked list 
		obj.addNewNode("New York");  
		obj.addNewNode("Los Angeles");  
		obj.addNewNode("Chicago");  
		obj.addNewNode("Houston");  
		obj.addNewNode("Houston");  

		//Call showData() method for displaying doubly linked list data  
		obj.showData();  
	}  
}

输出

将节点插入双向链表

在双向链表中，节点可以按以下方式之一插入：

在双向链表的开头。
在指定位置添加节点。
在链表末尾添加节点。

我们将逐一创建程序来理解所有这些方法。

在开头插入节点

在 CreateDoublyLinkedList 示例中，新创建的节点被添加到双向链表的末尾。当我们需要在链表开头添加节点时，需要更改头节点的值以及该头节点指向的节点。因此，我们将使用上面创建的相同示例。我们只在该程序中添加一个用于在链表开头添加节点的方法。

AddNodeInBeginning.java

public class AddNodeInBeginning {  

	//Creating a node for doubly linked list  
	class Node{  
		String data;  
		Node prev;  
		Node next;  

		public Node(String data) {  
			this.data = data;  
		}  
	}  

	//Initializing head and tail for the doubly linked list  
	Node head = null;
	Node tail = null;  
	
	public void addNewNodeInBegin(String data) {  
            //Creating node  
            Node newNode = new Node(data);  
              
            //Checking whether the list is empty or not  
            if(head == null) 
			{  
				//The newNode is pointed by both head or tail 
				head = newNode;
				tail = newNode;
				//It is first node so prev will point to null  
				head.prev = null;  
				//It is also last node so tail's next will point to null  
				tail.next = null;  
            }  
			////Execute when the list is not empty 
			else {  
				//The head's prev will point to the newNode  
				head.prev = newNode;  
				//The newNode's next will point to the head  
				newNode.next = head;  
				//The newNode's prev will point to null because it will be the first node 
				newNode.prev = null;  
				//The newNode will become new head because now the newly created node is the first node of the list 
				head = newNode;  
			}  
	}
	
	//Creating showData() method for displaying data of doubly linked list  
	public void showData() {
		//intializing a new node current that will point to head  
		Node current = head;  
		//Checking whether the doubly linked list is empty or not
		if(head == null) {
			//Printing a statement and pass the control flow into the main() method
			System.out.println("List is empty");  
			return;  
		}
		//Printing a statement
		System.out.println("Nodes of doubly linked list: ");  
		//Iterating the doubly linked list using while
		while(current != null) {  
			//Print tha data on that particular node and then increment the pointer for indicating next node  
			System.out.print(current.data + "\n");  
			current = current.next;  
		}  
	}  

	public static void main(String[] args) {  

		AddNodeInBeginning obj = new AddNodeInBeginning();  

		//Adding nodes into the doubly linked list 
		obj.addNewNodeInBegin("Emma");  
		obj.addNewNodeInBegin("Adele");  
		obj.addNewNodeInBegin("Aria");  
		obj.addNewNodeInBegin("Ally");  
		obj.addNewNodeInBegin("Paul");  
		
		
		//Calling showData() method for displaying doubly linked list data  
		obj.showData();  
	}  
}

输出

在末尾插入节点

我们也可以在链表末尾添加节点。在 CreateDoublyLinkedList 程序中，每个新创建的节点都添加到链表的末尾。因此，我们可以说插入节点到末尾的代码之前已经讨论过了。但为了更明确，我们提供了另一个示例，其中我们创建了一个单独的方法来添加节点。

AddNodeAtEnd.java

public class AddNodeAtEnd {  

	//Creating a node for list  
	class Node{  
		String data;  
		Node prev;  
		Node next;  

		public Node(String data) {  
			this.data = data;  
		}  
	}  

	//Initialize head and tail for the list  
	Node head = null;
	Node tail = null;  

	//Create firstNode() method for creating first node in the list
	public void firstNode(Node node){
		//The node will be pointed by both head and tail 
		head = node;
		tail = node;
		//It is first node so prev will point to null  
		head.prev = null;  
		//It is also last node so tail's next will point to null  
		tail.next = null;	
	}
	
	//Create addNewNodeAtEnd() method to add a node at last in the list   
	public void addNewNodeAtEnd(String data) {  
            //Creating new node  
            		Node newNode = new Node(data);  
              
            		//Check whether the list is empty or not  
            		if(head == null) 
		{  
			//Call firstNode() method to make it first node in the list
			firstNode(newNode);
			
            		}  
		////Execute when the list will not be empty 
		else {  
			//The newly created node will be the last node, so now tail's next will point to that newly created node
			tail.next = newNode;  
			//The tail will point to the second last node so the newly created node's prev will point to tail  
			newNode.prev = tail;  
			//The newly created node will become new tail because it is last node in the list 
			tail = newNode;  
			//The newly created node will be the last node so tail's next will be null  
			tail.next = null;  
		}  
	}
	
	//Creating showData() method for displaying data of list  
	public void showData() {
		//intialize a new node current that will point to head  
		Node current = head;  
		//Checking whether the list is empty or not
		if(head == null) {
			//Print a statement and pass the control flow into the main() method
			System.out.println("List is empty");  
			return;  
		}
		//Print a statement
		System.out.println("Nodes of doubly linked list: ");  
		//Iterate the list using while
		while(current != null) {  
			//Print tha data on that particular node and then increment the pointer to point to the next node  
			System.out.print(current.data + "\n");  
			current = current.next;  
		}  
	}  

	public static void main(String[] args) {  

		AddNodeAtEnd obj = new AddNodeAtEnd();  

		//Adding nodes at the end of the list 
		obj.addNewNodeAtEnd("New York");  
		obj.addNewNodeAtEnd("Chicago");  
		obj.addNewNodeAtEnd("Houston");  
		
		
		//Calling showData() method for displaying doubly linked list data  
		obj.showData();  
	}  
}  

输出

在指定位置插入节点

为了创建在指定位置添加节点的程序，我们需要关注以下四种情况：

当双向链表为空，或者指定的位置在列表中不存在。
指定位置可以是 1，因此我们需要为在链表开头添加节点创建代码，这我们上面已经讨论过了。
该位置也可以是双向链表中的最后一个索引或位置。因此，我们也需要编写在链表末尾添加节点的代码。
最后一种情况是位置在头尾之间的某个位置。

在给定的代码中，我们为每种情况创建了单独的方法，并尽量使其简单。

AddNodeAtSpecifiedLocation.java

public class AddNodeAtSpecifiedLocation {  

	//Creating a node for the list  
	class Node{  
		String data;  
		Node prev;  
		Node next;  

		public Node(String data) {  
			this.data = data;  
		}  
	}  
	public int size = 0;  
	
	//Initializing head and tail for the list  
	Node head = null;
	Node tail = null;  

	//Create firstNode() method for creating first node in the list
	public void firstNode(Node node){
		//The node is pointed by both head or tail 
		head = node;
		tail = node;
		//It is first node so prev will point to null  
		head.prev = null;  
		//It is also last node so tail's next will point to null  
		tail.next = null;	
	}
	
	//Create lastNode() method for adding node at last in the list
	public void lastNode(Node node){
		//The tail's next will point to that node
		tail.next = node;  
		//The tail is pointing to the second last node so the newly created node's prev will point to tail  
		node.prev = tail;  
		//The newly created node will become new tail because it is last node in the doubly linked list 
		tail = node;  
		//The newly created node will be the last node so tail's next will be null  
		tail.next = null;	
	}
	
	//Create addNodeInBeginning() method for adding node at first position
	public void addNodeInBeginning(Node node){
		//The head's prev will point to the newNode  
		head.prev = node;  
		//The newNode's next will point to the head  
		node.next = head;  
		//The newNode's prev will point to null because it will be the first node 
		node.prev = null;  
		//The newNode will become new head because now the newly created node is the first node of the list 
		head = node;  	
	}
	
	//Creating addNewNode() method to add a node into a list 
	public void addNewNode(String data) {  

		//Creating node  
		Node newNode = new Node(data);  

		//Checking whether our list is empty or not 
		if(head == null) {
			//Call firstNode() method to create first node in the list
			firstNode(newNode);
		}
		//Execute when the list is not empty
		else {  
			//Call lastNode() method to add a node at last in the list 
			lastNode(newNode);
		}
		size++;
	}  
	
	public void addNodeToSpeciifiedPosition(int position, String data) {
		//Creating node  
		Node newNode = new Node(data);  

		//Checking whether our doubly linked list is empty or not 
		if(head == null) {
			System.out.println("The specified location is not available");
		}
		//Execute when the list is not empty
		else {
			if(position == size+1){
				
				//Call lastNode() method to add the node at last in the list 
				lastNode(newNode);
				
			}else if(position == 1){
				
				addNodeInBeginning(newNode);
				
			}else{
				//current node will point to head  
				Node current = head;
				Node temp = null; 
				
				//Iterate list till current points to the specified position  
				for(int i = 1; i < position-1; i++){  
					current = current.next;  
				}  
  
				//The temp node points to the node that is next to current  
				temp = current.next;  
				temp.prev = current;  
  
				//newNode will be added between current and temp  
				current.next = newNode;   
				newNode.prev = current;  
				newNode.next = temp;  
				temp.prev = newNode;  
			}  
			size++;
		}
	}
	
	//Creating showData() method for displaying data of doubly linked list  
	public void showData() {
		//intializing a new node current that will point to head  
		Node current = head;  
		//Checking whether the doubly linked list is empty or not
		if(head == null) {
			//Printing a statement and pass the control flow into the main() method
			System.out.println("List is empty");  
			return;  
		}
		//Printing a statement
		System.out.println("Nodes of doubly linked list: ");  
		//Iterating the doubly linked list using while
		while(current != null) {  
			//Print tha data on that particular node and then increment the pointer for indicating next node  
			System.out.print(current.data + "\n");  
			current = current.next;  
		}  
	}  

	public static void main(String[] args) {  

		AddNodeAtSpecifiedLocation obj = new AddNodeAtSpecifiedLocation();  

		//Adding nodes into the doubly linked list 
		obj.addNewNode("New York");  
		obj.addNewNode("Los Angeles");  
		obj.addNewNode("Chicago");  
		obj.addNewNode("Houston");  
		obj.addNewNode("Phoenix");  
		
		//Adding nodes at the specified position 
		obj.addNodeToSpeciifiedPosition(6, "Philadelphia");
		obj.addNodeToSpeciifiedPosition(1, "San Antonio");
		obj.addNodeToSpeciifiedPosition(3, "San Diego");
		
		//Calling showData() method for displaying doubly linked list data  
		obj.showData();  
	}  
}

输出

从双向链表中删除节点

删除节点可能出现三种情况：

当节点是链表中的第一个节点时。
当节点是链表中的最后一个节点时。
当节点位于第一个和最后一个节点之间时。

在给定的程序中，我们为这三种不同情况创建了三个方法。程序中的每一行代码都通过注释进行了说明，以便于理解。

DeleteNodeFromList.java

public class DeleteNodeFromList {  

	//Create a node for DDL  
	class Node{  
		String data;  
		Node prev;  
		Node next;  

		public Node(String data) {  
			this.data = data;  
		}  
	}  

	int size = 0;
	
	//Initialize head and tail for DDL  
	Node head = null;
	Node tail = null;  

	
	
	//Create addNewNode() method to add a node into DDL 
	public void addNewNode(String data) {  

		//Creating node  
		Node newNode = new Node(data);  

		//Checking whether our DDL is empty or not 
		if(head == null) {
			//The newNode is pointed by both head or tail 
			head = newNode;
			tail = newNode;
			//It is first node so prev will point to null  
			head.prev = null;  
			//It is also last node so tail's next will point to null  
			tail.next = null;  
		}
		//Execute when the DDL is not empty
		else {  

			//The newly created node will be the last node, so now tail's next will point to that newly created node
			tail.next = newNode;  
			//The tail is pointing to the second last node so the newly created node's prev will point to tail  
			newNode.prev = tail;  
			//The newly created node will become new tail because it will be last node in the DDL 
			tail = newNode;  
			//The newly created node will be the last node so tail's next will be null  
			tail.next = null;  
		}
		//Increment the size of DDL
		size++;
	}
	
	//Create deleteFirstNode() method for deleting first node from DDL
	public void deleteFirstNode(){
		head = head.next;
	}
	
	//Create deleteLastNode() method for deleting last node from DDL
	public void deleteLastNode(){
		tail = tail.prev;
	}
	
	//Create deleteNodeAtSpecifiedLocation() method for deleting a node from DDL
	public void deleteNodeAtSpecifiedLocation(int position){

		//Check whether the DDL is empty or not 
		if(head == null || position>size) {
			System.out.println("\n" +position +"th position is not available\n");
		}
		//Execute when the DDL is not empty
		else {
			if(position == 1){
				
				//Call deleteFirstNode() method to delete first node from the DDL 
				deleteFirstNode();
				
				//Decrement the size of DDL
				size--;
				
			}else if(position == size){
				//Call deleteLastNode() method to delete last node from the DDL
				deleteLastNode();
				
				//Decrement the size of DDL
				size--;
				
			}else{
				//current node will point to head  
				Node current = head;
				
				//Iterate list till current points to the specified position  
				for(int i = 1; i < position; i++){  
					current = current.next;  
				} 
				
				//Delete node pointed by current
				current.next.prev = current.prev;
				current.prev.next = current.next;
			  
			}
			System.out.println(position +" node is deleted successfully from DDL");
		}
	}
	
	
	//Create showData() method for displaying data of DDL  
	public void showData() {
		//intialize a new node current that will point to head  
		Node current = head;  
		//Check whether the DDL is empty or not
		if(head == null) {
			//Print a statement and pass the control flow into the main() method
			System.out.println("List is empty");  
			return;  
		}
		//Print a statement
		System.out.println("Nodes of doubly linked list: ");  
		//Iterate the DDL using while
		while(current != null) {  
			//Print tha data on that particular node and then increment the pointer for indicating next node  
			System.out.print(current.data + "\n");  
			current = current.next;  
		}  
	}  

	public static void main(String[] args) {  

		DeleteNodeFromList obj = new DeleteNodeFromList();  

		//Add nodes into the DDL 
		obj.addNewNode("New York");  
		obj.addNewNode("Los Angeles");  
		obj.addNewNode("Chicago");  
		obj.addNewNode("Houston");  
		obj.addNewNode("Phoenix");  
		
		//Call showData() method for displaying DDL data  
		obj.showData();  
		
		//Delete nodes from the DDL
		obj.deleteNodeAtSpecifiedLocation(2);
		obj.deleteNodeAtSpecifiedLocation(1);
		obj.deleteNodeAtSpecifiedLocation(5);
		
		//Call showData() method for displaying DDL
		obj.showData();  
	}  
} 

输出

下一主题Java Cyclicbarrier 类

Doubly Linked List Program in Java

创建双向链表

将节点插入双向链表

在开头插入节点

在末尾插入节点

在指定位置插入节点

从双向链表中删除节点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Doubly Linked List Program in Java

创建双向链表

将节点插入双向链表

在开头插入节点

在末尾插入节点

在指定位置插入节点

从双向链表中删除节点

相关帖子

James Gosling：Java之父

Java vs. Python

Java 中的事件类型

Java 中的 NullPointerException

Java Basics

Java 中的预定义流

如何在 Eclipse 中导入 Jar 文件

如何在 Java 中清空链表

Java char keyword

Java 中反转带特殊字符的字符串

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器