1. LinkedList 简介
1) LinkedList 底层实现了 双向链表和双端队列 特点
2) 可以添加任意元素(元素可以重复)，包括null
3) 线程不安全，没有实现同步
2. LinkedList 底层操作机制
1) LinkedList 底层维护了一个双向链表.
2) LinkedList 中维护了两个属性first和last分别指向首节点和尾节点
3) 每个节点(Node对象) ，里面又维护了 prev、 next. item 三个属性，其中 prev 指向前一个，通过 next 指向后一个节点。 最终实现双向链表
4) 所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高。
5) 模拟一个简单的双向链表，如：
- 双向链表的简单使用
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，也就是说，要根据业务需求来进行选择。
