資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告