数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学Java中单链表和双链表的区别
单链表和双链表都是链表的实现方式。单链表的每个元素包含一些数据和指向下一个元素的链接，从而保持结构。另一方面，双链表中的每个节点还包含指向前一个节点的链接。
以下是单链表和双链表之间的一些重要区别。
| 序号 | 关键点 | 单链表 | 双链表 |
|---|---|---|---|
| 1 | 复杂度 | 在单链表中，在已知位置插入和删除的复杂度为 O(n) | 在双链表中，在已知位置插入和删除的复杂度为 O(1) |
| 2 | 内部实现 | 在单链表中，实现方式是节点包含一些数据和指向链表中下一个节点的指针。 | 而双链表的实现更复杂，节点包含一些数据以及指向链表中下一个节点和前一个节点的指针。 |
| 3 | 元素顺序 | 单链表只能单向遍历元素。 | 双链表允许双向遍历元素。 |
| 4 | 用途 | 单链表通常用于实现栈。 | 另一方面，双链表可以用来实现栈、堆和二叉树。 |
| 5 | 索引性能 | 当需要节省内存并且不需要搜索时，单链表是首选，因为只存储单个索引的指针。 | 如果需要更好的搜索性能并且内存不是限制因素，则双链表更可取。 |
| 6 | 内存消耗 | 由于单链表只存储一个节点的指针，因此消耗的内存更少。 | 另一方面，双链表每个节点使用更多内存（两个指针）。 |
单链表与双链表示例
SinlgyLinkedList.java
class Node {
//create class Node
public int data;
public Node next; //create node parameter for pointer of next element
public void displayNodeData() {
System.out.println("{ " + data + " } ");
}
}
public class SinglyLinkedList {
private Node head;
public boolean isEmpty() {
return (head == null);
}
// used to insert a node at the start of linked list
public void insertFirst(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = head;
head = newNode;
}
// used to delete node from start of linked list
public Node deleteFirst() {
Node temp = head;
head = head.next;
return temp;
}
// Use to delete node after particular node
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;
}
// used to insert a node at the start of linked list
public void insertLast(int data) {
Node current = head;
while (current.next != null) {
current = current.next; // we'll loop until current.next is null
}
Node newNode = new Node();
newNode.data = data;
current.next = newNode;
}
// For printing Linked List
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();
}
}输出
Nodes of doubly linked list: 1 2 3 4 5
更新于：2019年9月18日
3000+ 次浏览
广告