-
day20--Java集合03
8.LinkedList
1）linkedList底层实现了双向链表和双端队列的特点
2）可以添加任意元素（元素可以重复），包括null
3）线程不安全，没有实现同步
-
LinkedList的底层操作机制
- LinkedList底层维护了一个双向链表
- LinkedList中维护了两个属性first和last，分别指向首节点和尾节点
- 每个节点（Node对象）里面又维护了prev、next、item三个属性，其中通过prev指向前一个节点，通过next指向后一个节点，最终实现双向链表。
- 所以LinkedList的元素的添加和删除不是通过数组完成的，相对来说效率较高
8.1双向链表
例子：实现简单的双向链表
|
|
package li.collections.list.linkedlist; |
|
|
|
|
|
|
|
|
public class LinkedListTest { |
|
|
|
|
|
public static void main(String[] args) { |
|
|
Node jack = new Node("jack"); |
|
|
Node tom = new Node("tom"); |
|
|
Node marry = new Node("marry"); |
|
|
|
|
|
//连接节点，形成双向链表 |
|
|
//jack-->tom-->marry |
|
|
jack.next = tom; |
|
|
tom.pre = jack; |
|
|
tom.next = marry; |
|
|
marry.pre = tom; |
|
|
|
|
|
Node first = jack;//让头节点指向Jack |
|
|
Node last = marry;//尾节点指向marry |
|
|
|
|
|
//从头到尾遍历 |
|
|
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; |
|
|
} |
|
|
|
|
|
|
|
|
} |
|
|
} |
|
|
|
|
|
//定义一个Node对象，表示节点 |
|
|
class Node { |
|
|
public Object item;//存放数据 |
|
|
public Node next;//指针指向下一个节点 |
|
|
public Node pre;//指针指向上一个节点 |
|
|
|
|
|
public Node(Object name) { |
|
|
this.item = name; |
|
|
} |
|
|
|
|
|
|
|
|
public String toString() { |
|
|
return "Node item=" + item; |
|
|
} |
|
|
} |
例子2：双向链表节点的增加和删除
|
|
package li.collections.list.linkedlist; |
|
|
|
|
|
|
|
|
public class LinkedListTest { |
|
|
|
|
|
public static void main(String[] args) { |
|
|
Node jack = new Node("jack"); |
|
|
Node tom = new Node("tom"); |
|
|
Node marry = new Node("marry"); |
|
|
|
|
|
//连接节点，形成双向链表 |
|
|
//jack-->tom-->marry |
|
|
jack.next = tom; |
|
|
tom.pre = jack; |
|
|
tom.next = marry; |
|
|
marry.pre = tom; |
|
|
|
|
|
Node last = marry;//尾节点指向marry |
|
|
|
|
|
|
|
|
//链表添加数据 |
|
|
//要求在tom和marry之间插入一个对象json |
|
|
Node json = new Node("json"); |
|
|
|
|
|
//指针先连后删 |
|
|
json.pre = tom; |
|
|
json.next = marry; |
|
|
marry.pre = json; |
|
|
tom.next = json; |
|
|
|
|
|
Node first = jack;//让头节点再次指向Jack |
|
|
|
|
|
//从头到尾遍历 |
|
|
while (true) { |
|
|
if (first == null) { |
|
|
break; |
|
|
} |
|
|
System.out.println(first); |
|
|
first = first.next; |
|
|
} |
|
|
|
|
|
} |
|
|
} |
|
|
|
|
|
//定义一个Node对象，表示节点 |
|
|
class Node { |
|
|
public Object item;//存放数据 |
|
|
public Node next;//指针指向下一个节点 |
|
|
public Node pre;//指针指向上一个节点 |
|
|
|
|
|
public Node(Object name) { |
|
|
this.item = name; |
|
|
} |
|
|
|
|
|
|
|
|
public String toString() { |
|
|
return "Node item=" + item; |
|
|
} |
|
|
} |
8.2LinkedList底层结构
常用方法：
例子1：LinkedList双向链表增加数据
|
|
package li.collections.list.linkedlist; |
|
|
|
|
|
import java.util.LinkedList; |
|
|
|
|
|
public class LinkedListCRUD { |
|
|
|
|
|
public static void main(String[] args) { |
|
|
LinkedList linkedList = new LinkedList(); |
|
|
|
|
|
linkedList.add(1); |
|
|
linkedList.add(2); |
|
|
|
|
|
System.out.println("linkedList="+linkedList); |
|
|
|
|
|
|
|
|
} |
|
|
} |
-
在执行
LinkedList linkedList = new LinkedList();时，LinkedList底层创建了一个空的列表
-
执行
linkedList.add(1);时，首先进行自动装箱（略），然后调用底层的add（）方法，add（）又调用linkLast（）方法。
linkLst（）方法将新的节点加到双向链表的最后：
首先创建一个node类型的常量 l ，首先将last的地址赋给l，因为刚开始没有数据，last指向null，因此l同样也指向null。
再创建一个新的节点newNode，将add（1）传入的参数赋给newNode，newNode的pre指向l，即指向null，newNode的next也指向null。
然后将last指向newNode 
第一次的l指向了null，因此执行first也指向新结点newNode语句
最后是链表长度加1，修改次数modCount加1
所以，第一个节点的时候情况如图：
linkedList.add(2);执行第二次添加操作时，重复上述操作，最后来到linkLast（）方法。
-
此时last指向的是第一个节点，执行
final Node<E> l = last;，则 l 也指向第一个节点。 -
再新建一个节点，将 l 设置为新结点的pre，即将新结点的前置节点设置为了第一个节点，将新结点的next设置为空。
final Node<E> newNode = new Node<>(l, e, null); -
将last指向新结点
-
这里 l不再指向null，因此执行
l.next=newNode;语句，因为l这时指向第一个节点，所以执行语句之后第一个节点的next将会指向newNode
例子2：双向链表删除数据
|
|
package li.collections.list.linkedlist; |
|
|
|
|
|
import java.util.LinkedList; |
|
|
|
|
|
public class LinkedListCRUD { |
|
|
|
|
|
public static void main(String[] args) { |
|
|
LinkedList linkedList = new LinkedList(); |
|
|
|
|
|
linkedList.add(1); |
|
|
linkedList.add(2); |
|
|
linkedList.add(3); |
|
|
|
|
|
linkedList.remove();//这里默认删除第一个节点 |
|
|
System.out.println("linkedList="+linkedList);//linkedList=[2, 3] |
|
|
|
|
|
|
|
|
} |
|
|
} |
分析unlinkFirst（）方法：将f指向的双向链表中的第一个节点删除
-
首先在removeFirst（）方法中将 f 指向第一个节点：
final Node<E> f = first; -
然后取出第一个节点的值item：
final E element = f.item; -
然后将第一个节点next存储的地址赋给常量next，即将next指向第二个节点：
final Node<E> next = f.next; -
然后将第一个节点的值置空，以及将第一个节点指向的地址置空，这样第一节点指向第二节点的next就断开了：
f.item = null;
f.next = null; // help GC -
然后将next的地址赋给first，此时的next已经指向了第二个节点，所以first也指向第二个节点：
first = next; -
然后判断next是否为空，即判断删除的节点时候为最后一个节点，如果是，则将last置空；若否则将next指向节点的pre置空，也就是将第二个节点指向第一节点的指针断开。
|
|
if (next == null) |
|
|
last = null; |
|
|
else |
|
|
next.prev = null; |
-
而后链表长度-1，链表操作次数+1
-
最后返回删除数据的内容
例子3：其他常用方法
|
|
package li.collections.list.linkedlist; |
|
|
|
|
|
import java.util.Iterator; |
|
|
import java.util.LinkedList; |
|
|
|
|
|
public class LinkedListCRUD { |
|
|
|
|
|
public static void main(String[] args) { |
|
|
LinkedList linkedList = new LinkedList(); |
|
|
|
|
|
linkedList.add(1); |
|
|
linkedList.add(2); |
|
|
linkedList.add(3); |
|
|
|
|
|
//修改某个节点对象 |
|
|
linkedList.set(1,999);//public E set(int index, E element) |
|
|
System.out.println("linkedList="+linkedList);//linkedList=[1, 999, 3] |
|
|
|
|
|
//得到某个节点对象 |
|
|
System.out.println(linkedList.get(1));//得到第二个节点对象 999 |
|
|
|
|
|
//遍历:因为LinkedList实现了List接口，所以LinkedList也可以使用增强for循环和迭代器 |
|
|
// 1.增强for循环 |
|
|
for (Object o:linkedList) { |
|
|
System.out.println(o); |
|
|
|
|
|
} |
|
|
|
|
|
//2.迭代器 |
|
|
Iterator iterator = linkedList.iterator(); |
|
|
while (iterator.hasNext()) { |
|
|
Object next = iterator.next(); |
|
|
System.out.println(next); |
|
|
} |
|
|
|
|
|
//3.普通for循环 |
|
|
for (int i = 0; i < linkedList.size(); i++) { |
|
|
System.out.println(linkedList.get(i)); |
|
|
} |
|
|
|
|
|
|
|
|
} |
|
|
} |
8.3ArrayList和LinkedList的比较
| 底层结构 | 增删的效率 | 改查的效率 | |
|---|---|---|---|
| ArrayList | 可变数组 | 较低：数组扩容 | 较高 |
| LinkedList | 双向链表 | 较高：通过链表追加 | 较低 |
如任选择ArrayList和LinkedList：
- 如果我们改查比较多，选择ArrayList
- 如果增删比较多，选择LinkedList
- 一般来说，在程序中百分之80到90都是查询，因此大部分情况下会选择ArrayList
- 在一个项目中，根据业务灵活查询，也可以两个集合一起用。一个模块使用ArrayList，另一个模块使用LinkedList
