Java基礎之：List——LinkedList
LinkedList簡單介紹
LinkedList實作了雙向鏈表(資料結構)和雙端佇列特點，
實作了List介面，可以添加任意元素(即可以重復和null)，執行緒不安全，
LinkedList底層實作分析
-
LinkedList底層維護了一個雙向鏈表
-
LinkedList中維護了兩個屬性first和last，分別指向首節點和尾節點
-
每個節點(資料結構中將節點都稱作Node物件)，里面又維護了prev、next、item三個屬性，其中prev指向前一個Node，next指向后一個Node，最終實作雙向鏈表，
-
所以LinkedList的元素添加與洗掉不是通過陣列完成的，效率較高，
模擬最簡單的雙向鏈表：
package class_LinkedList;
?
?
public class ClassTest01_DoubleLinkedList {
public static void main(String[] args) {
Node first = null;//首先定義一個first節點，作為標記位置存在
//當添加一個節點時，讓first節點指向此節點
Node node1 = new Node(first, null, "小范");
first = node1;
//添加第二個節點，在構造時，讓第二個節點的prev屬性指向前一個節點node1
Node node2 = new Node(node1, null, "小黃");
node1.next = node2; //讓node1的next指向node2，實作雙向連接
//添加第三個節點
Node node3 = new Node(node2, null, "小雨");
node2.next = node3;
//結尾 ，使用last節點，讓last節點指向node3，因為node3的next為null代表鏈表結束
Node last = node3;
//鏈表遍歷，通常都使用一個臨時temp節點來用于遍歷鏈表，不要使用first！
Node temp = first;
//鏈表從前向后遍歷
System.out.println("==========從前向后============");
while(true) {
System.out.println(temp);
if(temp.next == null) { //last節點的next屬性為null
break;
}
temp = temp.next; //將temp向后移
}
//鏈表從后向前遍歷
System.out.println("==========從后向前============");
temp = last;
while(true) {
System.out.println(temp);
if(temp.prev == null) { //first節點的prev屬性為null
break;
}
temp = temp.prev; //將temp向前移
}
//添加節點，讓需要添加位置的前后節點分別指向要添加的節點即可，
//創建需要添加的節點，讓其prev屬性指向要添加位置的前一個節點，next屬性指向要添加位置的后一個節點
Node add = new Node(node1,node2,"add"); //在第一個和第二個節點中間插入一個節點
//將node1的next指向add，node2的prev指向add，完成連接，此時node1與node2之間的連接自然就斷開了
node1.next = add;
node2.prev = add;
//再次遍歷檢查是否添加成功
System.out.println("==========添加后===========");
temp = first;
while(true) {
System.out.println(temp);
if(temp.next == null) { //last節點的next屬性為null
break;
}
temp = temp.next; //將temp向后移
}
}
}
?
class Node{
//說明 這里為了方便演示案例，沒有進行封裝，實際開發中需要封裝
Node prev; //指向前一個節點
Node next; //指向后一個節點
String name; //每個節點的自有屬性
public Node(Node prev, Node next, String name) {
this.prev = prev;
this.next = next;
this.name = name;
}
@Override
public String toString() {
return "Node [name=" + name + "]";
}
}
程式輸出：
==========從前向后============
Node [name=小范]
Node [name=小黃]
Node [name=小雨]
==========從后向前============
Node [name=小雨]
Node [name=小黃]
Node [name=小范]
==========添加后===========
Node [name=小范]
Node [name=add]
Node [name=小黃]
Node [name=小雨]
LinkedList常用方法
package class_LinkedList;
?
import java.util.LinkedList;
?
public class ClassTest02_LinkedListMethods {
?
@SuppressWarnings({ "rawtypes", "unchecked" })
public static void main(String[] args) {
?
LinkedList linkedList = new LinkedList();
// 添加
for (int i = 0; i < 2; i++) {
linkedList.add("AAA" + i);
}
?
String kk = "yyy";
linkedList.add(kk);
linkedList.add(2, kk);
?
// 遍歷
for (Object object : linkedList) {
System.out.println(object);
}
?
// 洗掉
// linkedList.remove(0);
// linkedList.remove(kk);
System.out.println("=================");
//替換
linkedList.set(0, "川農");
for (Object object : linkedList) {
System.out.println(object);
}
System.out.println("=================");
//查找，也可以使用下標進行訪問
Object object = linkedList.get(0);
System.out.println("object=" + object);
//LinkedList特有方法，獲取首尾節點
System.out.println(linkedList.getFirst());
System.out.println(linkedList.getLast());
}
}
添加節點原始碼分析
默認添加：
帶下標位置的添加：
Node內部類原始碼
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
?
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node內部類維護了next與prev屬性，
LinkedList與ArrayList對比
如何選擇ArrayList和LinkedList：
-
如果我們改查的操作多，選擇ArrayList
-
如果我們增刪的操作多，選擇LinkedList
-
一般來說，在程式中，80%-90%都是查詢，因此大部分情況下會選擇ArrayList
-
在一個專案中，根據業務靈活選擇，也可能這樣，一個模塊使用的是ArrayList,另外一個模塊是LinkedList.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/240747.html
標籤：Java