LinkedList實(shí)現(xiàn)了雙向鏈表(數(shù)據(jù)結(jié)構(gòu))和雙端隊(duì)列特點(diǎn)。
實(shí)現(xiàn)了List接口,可以添加任意元素(即可以重復(fù)和null),線程不安全。
LinkedList底層維護(hù)了一個(gè)雙向鏈表
LinkedList中維護(hù)了兩個(gè)屬性first和last,分別指向首節(jié)點(diǎn)和尾節(jié)點(diǎn)
每個(gè)節(jié)點(diǎn)(數(shù)據(jù)結(jié)構(gòu)中將節(jié)點(diǎn)都稱作Node對(duì)象),里面又維護(hù)了prev、next、item三個(gè)屬性。其中prev指向前一個(gè)Node,next指向后一個(gè)Node,最終實(shí)現(xiàn)雙向鏈表。
所以LinkedList的元素添加與刪除不是通過數(shù)組完成的,效率較高。
模擬最簡單的雙向鏈表:
package class_LinkedList;public class ClassTest01_DoubleLinkedList { public static void main(String[] args) { Node first = null;//首先定義一個(gè)first節(jié)點(diǎn),作為標(biāo)記位置存在 //當(dāng)添加一個(gè)節(jié)點(diǎn)時(shí),讓first節(jié)點(diǎn)指向此節(jié)點(diǎn) Node node1 = new Node(first, null, "小范"); first = node1; //添加第二個(gè)節(jié)點(diǎn),在構(gòu)造時(shí),讓第二個(gè)節(jié)點(diǎn)的prev屬性指向前一個(gè)節(jié)點(diǎn)node1 Node node2 = new Node(node1, null, "小黃"); node1.next = node2; //讓node1的next指向node2,實(shí)現(xiàn)雙向連接 //添加第三個(gè)節(jié)點(diǎn) Node node3 = new Node(node2, null, "小雨"); node2.next = node3; //結(jié)尾 ,使用last節(jié)點(diǎn),讓last節(jié)點(diǎn)指向node3,因?yàn)閚ode3的next為null代表鏈表結(jié)束 Node last = node3; //鏈表遍歷,通常都使用一個(gè)臨時(shí)temp節(jié)點(diǎn)來用于遍歷鏈表,不要使用first! Node temp = first; //鏈表從前向后遍歷 System.out.println("==========從前向后============"); while(true) { System.out.println(temp); if(temp.next == null) { //last節(jié)點(diǎn)的next屬性為null break; } temp = temp.next; //將temp向后移 } //鏈表從后向前遍歷 System.out.println("==========從后向前============"); temp = last; while(true) { System.out.println(temp); if(temp.prev == null) { //first節(jié)點(diǎn)的prev屬性為null break; } temp = temp.prev; //將temp向前移 } //添加節(jié)點(diǎn),讓需要添加位置的前后節(jié)點(diǎn)分別指向要添加的節(jié)點(diǎn)即可。 //創(chuàng)建需要添加的節(jié)點(diǎn),讓其prev屬性指向要添加位置的前一個(gè)節(jié)點(diǎn),next屬性指向要添加位置的后一個(gè)節(jié)點(diǎn) Node add = new Node(node1,node2,"add"); //在第一個(gè)和第二個(gè)節(jié)點(diǎn)中間插入一個(gè)節(jié)點(diǎn) //將node1的next指向add,node2的prev指向add,完成連接,此時(shí)node1與node2之間的連接自然就斷開了 node1.next = add; node2.prev = add; //再次遍歷檢查是否添加成功 System.out.println("==========添加后==========="); temp = first; while(true) { System.out.println(temp); if(temp.next == null) { //last節(jié)點(diǎn)的next屬性為null break; } temp = temp.next; //將temp向后移 } }}class Node{ //說明 這里為了方便演示案例,沒有進(jìn)行封裝,實(shí)際開發(fā)中需要封裝 Node prev; //指向前一個(gè)節(jié)點(diǎn) Node next; //指向后一個(gè)節(jié)點(diǎn) String name; //每個(gè)節(jié)點(diǎn)的自有屬性 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=小雨]
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, "川農(nóng)"); for (Object object : linkedList) { System.out.println(object); } System.out.println("================="); //查找,也可以使用下標(biāo)進(jìn)行訪問 Object object = linkedList.get(0); System.out.println("object=" + object); //LinkedList特有方法,獲取首尾節(jié)點(diǎn) System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); }}
默認(rèn)添加:
帶下標(biāo)位置的添加:
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內(nèi)部類維護(hù)了next與prev屬性。
如何選擇ArrayList和LinkedList:
如果我們改查的操作多,選擇ArrayList
如果我們?cè)鰟h的操作多,選擇LinkedList
一般來說,在程序中,80%-90%都是查詢,因此大部分情況下會(huì)選擇ArrayList
在一個(gè)項(xiàng)目中,根據(jù)業(yè)務(wù)靈活選擇,也可能這樣,一個(gè)模塊使用的是ArrayList,另外一個(gè)模塊是LinkedList.
聯(lián)系客服