ArrayList改查效率高是因为数组可以通过索引直接定位,LinkedList则需要从头遍历
另外这两个都是线程不安全的,在单线程的时候考虑使用
为了便于理解这里我们先模拟一个简单的双向链表:
package collection.list.linkedlist; /** * @author 紫英 * @version 1.0 * @discription 模拟一个双向链表 */ public class LinkedList01 { public static void main(String[] args) { //先创建三个节点 Node node01 = new Node("111"); Node node02 = new Node("222"); Node node03 = new Node("333"); //将三个节点连接起来形成双向链表 // node01 -> node02 -> ndoe03 node01.next = node02; node02.next = node03; // node01 <- node02 <- ndoe03 node02.pre = node01; node03.pre = node02; //头节点指向第一个 Node first = node01; //尾节点指向最后一个 Node last = node03; //正向遍历双向链表 System.out.println("===正向遍历双向链表==="); while (true) { if (first == null) { break; } System.out.println(first); first = first.next; } //逆向遍历双向链表 System.out.println("===逆向遍历双向链表==="); while (true) { if (last == null) { break; } System.out.println(last); last = last.pre; } //在node01和node02之间添加一个新的node // 1.先创建一个新节点 Node node = new Node("666"); // 2.将其加入到双向链表中 node01.next = node; node.next = node02; node.pre = node01; node02.pre = node; //重置first后再进行一次正向遍历 first = node01; //添加数据后正向遍历双向链表 System.out.println("===添加数据后正向遍历双向链表==="); while (true) { if (first == null) { break; } System.out.println(first); first = first.next; } //重置last后再进行一次逆向遍历 last = node03; //添加数据后逆向遍历双向链表 System.out.println("===添加数据后逆向遍历双向链表==="); while (true) { if (last == null) { break; } System.out.println(last); last = last.pre; } } } class Node { public Object item;//真正存放的数据 public Node next;//指向下一个节点 public Node pre;//指向前一个节点 //构造器 public Node(Object item) { this.item = item; } @Override public String toString() { return "Node name = " + item; } }
结果如下:
public class LinkedListCRUD { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.add(1); linkedList.add(2); } }
1.构造器语句
此时 first=null,last=null
2.add()方法
3.linkLast(e) 将新节点加入到双向链表最后
(1)先将last赋值给一个Node型的数据l,也就是说此时的l是指向null的(因为last指向null)
(2)创建一个新的节点
(3)将last指向新节点,此时的新节点前后都为null
(4)判断 if (l == null) 根据(1)此时的l为null,所以将first也指向新节点
4.加入第二个节点
(1)此时的l还是指向last也就是第一个节点
(2)创建一个新结点,并将新节点的pre指向l,也就是说此时新节点的pre指向了第一个节点
(3)将last指向新节点
(4)判断 if (l == null) 根据(1)此时的l是指向第一个节点的不为null,所以执行l.next = newNode,将第一个节点的next指向新节点
(5)此时的first还是指向第一个节点而last则指向新节点
public class LinkedListCRUD { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.remove();//默认删除第一个 } }
1.进去之后执行了removeFirst()方法
2.removeFirst() 先将f指向双向链表的first,并判断一下是否删除的是空链表
3.unlinkFirst(f)
(1)先将first中的item赋给element(最后作为返回值返回)
(2)创建一个next指向f的下一个节点
(3)将f中的内容置空
(4)将f.next的指向置空(可以帮助GC垃圾回收机制判定为垃圾)
(5)将first指向next,也就是指向了第二个节点
(6)判断 if (next == null),这里next指向的是第二个节点并不为null,所以执行 next.prev = null,将 next.prev置空
(7)此时之前的第一个节点变成孤零零的一个,会被GC判定为垃圾回收