1. LinkedList 简介
- LinkedList 底层实现了双向链表和双端队列特点
- 可以添加任意元素(元素可以重复)，包括
null - 线程不安全，没有实现同步
2. LinkedList 底层操作机制
- LinkedList 底层维护了一个双向链表.
- LinkedList 中维护了两个属性
first和last分别指向首节点和尾节点 - 每个节点(Node对象) ，里面又维护了
prev、 next. item 三个属性，其中prev 指向前一个，通过next 指向后一个节点。 最终实现双向链表 - 所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高。
- 模拟一个简单的双向链表，如：
-
- 双向链表的简单使用
public class LinkedList01 {
public static void main(String[] args) {
// 模拟一个简单的双向链表
Node tom = new Node("tom");
Node jack = new Node("jack");
Node xdr = new Node("xdr");
//连接三个点，形成双向链表
// tom->jack->xdr
tom.next = jack;
jack.next = xdr;
// xdr->jack->tom
xdr.pre = jack;
jack.pre = tom;
Node first = tom;//让 first 引用指向 jack,就是双向链表的头节点
Node last = xdr; //让 last 引用指向 xdr,就是双向链表的尾节点
// 从头到尾进行遍历
System.out.println("===从头到尾进行遍历===");
while (true) {
if (first == null) {
break;
}
//输出 first 信息
System.out.println(first);
first = first.next;
}
//从尾到头的遍历
System.out.println("====从尾到头进行遍历====");
while (true) {
if (last == null) {
break;
}
//输出 last 信息
System.out.println(last);
last = last.pre;
}
}
}
// 定义一个 Node 类，Node 对象，表示双向链表的一个节点
class Node {
public Object item; // 真正存放的数据
public Node next; // 指向后一个节点
public Node pre; // 指向前一个节点
public Node(Object name) {
this.item = name;
}
public String toString() {
return "Node name=" + item;
}
}
- 在链表中插入元素，如：在 jack 和 xdr 中间插入一个对象 mike
//先创建一个 Node 结点，name 就是 mike
Node mike = new Node("mike");
//下面就把 mike 加入到双向链表了
mike.next = xdr;
mike.pre = jack;
xdr.pre = mike;
jack.next = mike;
//让 first 再次指向 tom
first = tom;//让 first 引用指向 tom,就是双向链表的头结
System.out.println("===从头到尾进行遍历===");
while (true) {
if (first == null) {
break;
}
//输出 first 信息
System.out.println(first);
first = first.next;
}
// 从尾到头进行遍历
last = xdr; //让 last 重新指向最后一个节点
//从尾到头的遍历
System.out.println("====从尾到头进行遍历====");
while (true) {
if (last == null) {
break;
}
//输出 last 信息
System.out.println(last);
last = last.pre;
}
3. LinkedList 源码分析
1、案例：打断点进行源码分析
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
1. LinkedList linkedList = new LinkedList();
public LinkedList() {}
2. 这时 linkeList 的属性 first = null last = null
3. 执行 添加
public boolean add(E e) {
linkLast(e);
return true;
}
4.将新的结点，加入到双向链表的最后
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2、演示删除节点的源码：linkedList.remove(); 这里默认删除的是第一个节点
1. 执行 removeFirst
public E remove() {
return removeFirst();
}
2. 执行
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
4. LinkedList 增删改查案例
- 删除一个节点
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
System.out.println(linkedList);
linkedList.remove();
System.out.println(linkedList);
- 修改某个节点对象，index 索引是按照
0 开始编号的
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println(linkedList);
linkedList.remove();
System.out.println(linkedList);
linkedList.set(1, 2233);
System.out.println(linkedList);
- 得到某个结点对象，
get(1) 是得到双向链表的第二个对象
Object o = linkedList.get(1);
System.out.println(o);
- LinkedList 是 实现了List接口，遍历方式可以用 迭代器、增强for、普通for 进行遍历
System.out.println("===迭代器遍历===");
Iterator iterator = linkedList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println("next=" + next);
}
System.out.println("===增强for循环遍历===");
for (Object o : linkedList) {
System.out.println("o=" + o);
}
System.out.println("===普通for循环遍历===");
for (int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedList.get(i));
}
5. ArrayList和LinkedList比较
- 如何选择 ArrayList 和 LinkedList ：
- 如果改查的操作多，选择
ArrayList - 如果增删的操作多，选择
LinkedList - 一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择
ArrayList - 在一个项目中，根据业务灵活选择，一个模块使用的是
ArrayList，另外一个模块是LinkedList，也就是说，要根据业务需求来进行选择。
