单链表和双链表都是链表的实现，其中单链表的每个元素都包含一些数据以及到下一个元素的链接，从而可以保持结构。另一方面，双向链接列表中的每个节点也包含指向前一个节点的链接。
以下是单链接列表和双链接列表之间的重要区别。序号键单链表双链表1复杂在单链表中，在已知位置插入和删除的复杂度为O(n)如果是双链表，则在已知位置插入和删除的复杂度为O(1)
2内部实施在单链列表的实现中，例如节点包含一些数据以及指向列表中下一个节点的指针虽然双向链表具有一些更复杂的实现，其中节点包含一些数据以及指向列表中的下一个节点和上一个节点的指针
3元素顺序单链表仅允许以一种方式遍历元素。双链表允许元素双向遍历。
4用法单链表通常用于堆栈的实现另一方面，双向链表可用于实现堆栈以及堆和二叉树。
5指数表现当我们需要节省内存并且由于存储单个索引的指针而不需要搜索时，首选单链表。如果在搜索时我们需要更好的性能，并且内存不是一个限制，则在这种情况下，双向链表是更可取的。
6内存消耗由于单链表仅存储一个节点的指针，因此消耗较少的内存。另一方面，双链表每个节点使用更多内存(两个指针)。
单链表与双链表的示例
SinlgyLinkedList.javaclass Node {
//创建类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);
}
//用于在链表的开头插入节点
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; // we'll loop until current.next is 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.javapublic 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.javapublic 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) {
//创建一个新节点
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