Java 中单链表和双链表的区别

java 8object oriented programmingprogramming更新于 2025/11/25 19:24:17

单链表和双链表都是链表的实现，其中单链表的每个元素都包含一些数据和指向下一个元素的链接，这样可以保持结构。另一方面，双链表中的每个节点还包含指向前一个节点的链接。

以下是单链表和双链表之间的重要区别。

Sr.No.	键	单链表	双向链表
1	复杂度	在单链表中，在已知位置插入和删除的复杂度为 O(n)	在双向链表中，在已知位置插入和删除的复杂度为 O(1)
2	内部实现	单链表的实现是这样的，其中节点包含一些数据和一个指向列表中下一个节点的指针	而双向链表有一些更复杂的实现，其中节点包含一些数据和一个指向列表中下一个节点以及上一个节点的指针
3	元素顺序	单链表只允许以一种方式遍历元素。	双向链表允许元素双向遍历。
4	用法	单链表通常用于实现堆栈	另一方面，双向链表可用于实现堆栈以及堆和二叉树。
5	索引性能	当我们需要节省内存并且不需要搜索时，单链表是首选，因为存储了单个索引的指针。	如果我们在搜索时需要更好的性能并且内存不是限制，则双向链表是首选。
6	内存消耗	由于单链表只存储一个节点的指针，因此消耗的内存较少。	另一方面，双向链表每个节点(两个指针)使用更多内存。

单链表与双向链表的示例

SinlgyLinkedList.java

class Node {
   //创建类 Node
   public int data;
   public Node next; //创建指向下一个元素的指针的节点参数
   public void displayNodeData() {
      System.out.println("{ " + data + " } ");
   }
}
public class SinglyLinkedList {
   private Node head;
   public boolean isEmpty() {
      return (head == null);
   }
   // 用于在链接列表的开头插入一个节点
   public void insertFirst(int data) {
      Node newNode = new Node();
      newNode.data = data;
      newNode.next = head;
      head = newNode;
   }
   // 用于从链接列表的开头删除节点
   public Node deleteFirst() {
      Node temp = head;
      head = head.next;
      return temp;
   }
   // 用于删除特定节点后的节点
   public void deleteAfter(Node after) {
      Node temp = head;
      while (temp.next != null && temp.data != after.data) {
         temp = temp.next;
      }
      if (temp.next != null)
      temp.next = temp.next.next;
   }
   // 用于在链接列表的开头插入一个节点
   public void insertLast(int data) {
      Node current = head;
      while (current.next != null) {
         current = current.next; // 我们将循环直到 current.next 为 null
      }
      Node newNode = new Node();
      newNode.data = data;
      current.next = newNode;
   }
   // 用于打印链接列表
   public void printLinkedList() {
      System.out.println("Printing LinkedList (head --> last) ");
      Node current = head;
      while (current != null) {
         current.displayNodeData();
         current = current.next;
      }
      System.out.println();
   }
}

示例

LinkedListMain.java

public class LinkedListMain {
   public static void main(String args[]){
      SinglyLinkedList myLinkedlist = new SinglyLinkedList();
      myLinkedlist.insertFirst(5);
      myLinkedlist.insertFirst(6);
      myLinkedlist.insertFirst(7);
      myLinkedlist.insertFirst(1);
      myLinkedlist.insertLast(2);
      Node node=new Node();
      node.data=1;
      myLinkedlist.deleteAfter(node);
      myLinkedlist.printLinkedList();
   }
}

输出

Printing LinkedList (head --> last)
{ 1 }
{ 6 }
{ 5 }
{ 2 }

示例

DoublyLinkedListMain.java

public class DoublyLinkedList {
   class Node{
      int data;
      Node previous;
      Node next;
      public Node(int data) {
         this.data = data;
      }
   }
   Node head, tail = null;
   public void addNode(int data) {
      //Create a new node
      Node newNode = new Node(data);
      if(head == null) {
         head = tail = newNode;
         head.previous = null;
         tail.next = null;
      } else {
         tail.next = newNode;
         newNode.previous = tail;
         tail = newNode;
         tail.next = null;
      }
   }
   public void display() {
      Node current = head;
      if(head == null) {
         System.out.println("List is empty");
         return;
      }
      System.out.println("Nodes of doubly linked list: ");
      while(current != null) {
         System.out.print(current.data + " ");
         current = current.next;
      }
   }
   public static void main(String[] args) {
      DoublyLinkedList dList = new DoublyLinkedList();
      dList.addNode(1);
      dList.addNode(2);
      dList.addNode(3);
      dList.addNode(4);
      dList.addNode(5);
      dList.display();
   }
}