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->xdrtom.next = jack;jack.next = xdr;// xdr->jack->tomxdr.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 就是 mikeNode mike = new Node("mike");//下面就把 mike 加入到双向链表了mike.next = xdr;mike.pre = jack;xdr.pre = mike;jack.next = mike;//让 first 再次指向 tomfirst = 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 = null3. 执行 添加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;elsel.next = newNode;size++;modCount++;}

2、演示删除节点的源码：linkedList.remove(); 这里默认删除的是第一个节点

1. 执行 removeFirstpublic 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 GCfirst = next;if (next == null)last = null;elsenext.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));}