老规矩我们先看下LinkedList的继承关系图:
![]() ①.从图中我可以看出LinkedList实现了Deque接口，可以将LinkedList当做队列使用;实现了cloneable表示能被克隆，实现了Serializable接口表示支持序列化.
②.LinkedList基于双向链表，实现了所有List操作并允许所有元素包括null值，它可以被当作双端队列.
③.LinkedList顺序访问非常高效，而随机访问效率很低.
④.LinkedList线程不安全，可以用Collections.synchronizedList使其线程安全.
源码分析LinkedList字段 /** * 序列号 */ private static final long serialVersionUID = 876323262645176354L; /** * LinkedList长度，不可序列化 */ transient int size = 0; /** * 首结点 */ transient Node first; /** * 尾结点 */ transient Node last;复制代码结点类:
/** * 结点类 */ private static class Node { // 当前结点所包含的值 E item; // 后继结点 Node next; // 前驱结点 Node prev; //结点构造方法 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } 复制代码>构造方法 /** * 无参构造 */ public LinkedList() { } /** * 参数Collection的构造方法 */ public LinkedList(Collection c) { // 调用无参构造函数 this(); // 添加集合中所有的元素 addAll(c); } 复制代码CRUDCreateLinkedList新增(public)有如下几个方法:
public boolean add(E e);
public boolean offer(E e);
public void addLast(E e);
public boolean offerLast(E e);
/** * 末尾插入元素 */ public boolean add(E e) { linkLast(e); return true; } public boolean offer(E e) { // 尾插元素 return add(e); } /** * 尾插元素 */ public void addLast(E e) { linkLast(e); } /** * 尾插元素 */ public boolean offerLast(E e) { addLast(e); return true; } /** * 尾插元素 */ void linkLast(E e) { //获取当前尾结点 final Node l = last; //定义新结点，其前驱结点为尾结点，值为e，后继结点为null final Node newNode = new Node<>(l, e, null); //将刚定义的新节点设为尾结点 last = newNode; //若原尾结点为null，即原链表为null，则链表首结点也为newNode if (l == null) first = newNode; //若不是原尾结点的后继设为newNode else l.next = newNode; 长度+1 size++; 改变次数+1 modCount++; }复制代码public void add(int index, E element);
public boolean addAll(Collection<? extends E> c);
public boolean addAll(int index, Collection<? extends E> c);
/** * 指定位置插入元素 */ public void add(int index, E element) { // 判断索引是否越界 checkPositionIndex(index); // 若指定位置在尾部，则尾插元素;若不在调通用方法指定位置插入 if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 尾插集合所有元素 */ public boolean addAll(Collection c) { return addAll(size, c); } /** * 指定位置插入集合所有元素 */ public boolean addAll(int index, Collection c) { //判断索引是否越界 checkPositionIndex(index); //将集合转为数组 Object[] a = c.toArray(); //获取数组长度 int numNew = a.length; //若数组长度为0，即没有要插入的元素返回false if (numNew == 0) return false; //succ为原index位置上结点，pred为succ前驱结点 Node pred, succ; //若是尾部，succ为null，pred为尾结点 if (index == size) { succ = null; pred = last; //若不是succ为index位置结点，pred为其前驱结点 } else { succ = node(index); pred = succ.prev; } //for循环遍历集合 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //定义一个新结点，其前驱结点为pred，结点值为e，后继结点为null Node newNode = new Node<>(pred, e, null); //若前驱结点为null，则将newNode设为首结点 if (pred == null) first = newNode; else //若存在前驱结点，将其后继赋为newNode pred.next = newNode; 类似于迭代器的next，将newNode指向下一个需插入结点位置的前驱 pred = newNode; } //若是尾插，则最后添加元素为尾结点 if (succ == null) { last = pred; } else { //若不是，最后添加的结点后继指向原index位置上的succ pred.next = succ; //succ的前驱指向最后添加的结点 succ.prev = pred; } //长度+numNew size += numNew; modCount++; return true; } private void checkPositionIndex(int index) { //若index不在[0，size]区间内则抛越界异常 if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } /** * 获取指定位置结点 */ Node node(int index) { // 若指定索引小于LinkedList长度一半，则从首结点开始遍历;若不是从尾结点开始遍历 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } /** * 中间插入 */ void linkBefore(E e, Node succ) { // 获取原索引上元素前驱结点pred final Node pred = succ.prev; // 定义新结点，其前驱结点为pred，结点值为e，后继为succ final Node newNode = new Node<>(pred, e, succ); // 将succ的前驱结点设为newNode succ.prev = newNode; // pred为空，即succ为原首结点，那么将新定义的newNode设为新首结点 if (pred == null) first = newNode; else //否则pred后继结点设为newNode pred.next = newNode; //长度+1 size++; //修改次数+1 modCount++; }复制代码public boolean offerFirst(E e);
public void addFirst(E e);
public void push(E e);
/** * 头插指定元素 */ public void addFirst(E e) { linkFirst(e); } public void push(E e) { addFirst(e); } /** * 头插指定元素 */ public boolean offerFirst(E e) { addFirst(e); return true; } /** * 头插 */ private void linkFirst(E e) { //获取当前首结点 final Node f = first; //定义新结点，前驱为null，结点值为e，后驱为f final Node newNode = new Node<>(null, e, f); //将newNode设为首结点 first = newNode; //若首结点为null，尾结点设为newNode，若不是原首结点前驱设为newNode if (f == null) last = newNode; else f.prev = newNode; 长度+1 size++; modCount++; }复制代码RetrieveLinkedList查询(public)有如下几个方法:
public boolean contains(Object o);
public int size();
public E element();
public E get(int index);
public E getFirst();
public E getLast();
public int indexOf(Object o);
public int lastIndexOf(Object o);
public int size();
public E peek();
public E peekFirst();
public E peekLast();
/** * 查询是否包含此元素 */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * 循环从头遍历找出指定元素索引，-1表示不存在该元素 */ public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } /** * 查询LinkedList长度 */ public int size() { return size; } /** * 获取首结点值，若链表为空会抛异常 */ public E element() { return getFirst(); } /** * 获取首结点值，若链表为空会抛异常 */ public E getFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * 获取首结点值，若无首结点返回null */ public E peek() { final Node f = first; return (f == null) ? null : f.item; } /** * 获取首结点值，若无首结点返回null */ public E peekFirst() { final Node f = first; return (f == null) ? null : f.item; } /** * 获取指定索引元素 */ public E get(int index) { //校验是否越界 checkElementIndex(index); return node(index).item; } /** * 获取尾结点，，若链表为空会抛异常 */ public E getLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return l.item; } /** * 获取尾结点值，若链表为空返回null */ public E peekLast() { final Node l = last; return (l == null) ? null : l.item; } /** * 循环从尾遍历找出指定元素索引，-1表示不存在该元素 */ public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }复制代码Updatepublic E set(int index, E element);
/** * 修改指定位置结点值，返回被替换结点值 */ public E set(int index, E element) { //校验index是否越界 checkElementIndex(index); //获取当前index位置上结点 Node x = node(index); //获取此结点值 E oldVal = x.item; //修改结点值 x.item = element; //返回被替换结点值 return oldVal; } 复制代码Deletepublic E remove();
public E remove(int index);
public boolean remove(Object o);
public E removeFirst();
public boolean removeFirstOccurrence(Object o);
public E removeLast();
public boolean removeLastOccurrence(Object o);
public void clear();
public E poll();
public E pollFirst();
public E pop();
/** * 获取并删除首结点值，若链表为空则抛出异常 */ public E remove() { return removeFirst(); } public E pop() { return removeFirst(); } public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * 获取并删除首结点，若链表为空返回null */ public E poll() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } public E pollFirst() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } private E unlinkFirst(Node f) { //获取首结点值 final E element = f.item; //获取首结点后继 final Node next = f.next; //删除首结点 f.item = null; f.next = null; // help GC //原后继结点设为首结点 first = next; //若后继结点为null，尾结点设为null;若不是后继结点的前驱结点设为null if (next == null) last = null; else next.prev = null; //长度-1 size--; modCount++; return element; } /** * 删除指定位置结点 */ public E remove(int index) { //校验index是否越界 checkElementIndex(index); return unlink(node(index)); } /** * 删除指定结点 */ E unlink(Node x) { // 获取指定结点值 final E element = x.item; // 获取指定结点后继 final Node next = x.next; // 获取指点结点前驱 final Node prev = x.prev; // 若前驱为null，则后继结点设为首结点 if (prev == null) { first = next; } else { //若不是，指定结点后继结点设为指定结点前驱结点后继，指定结点的前驱设为null prev.next = next; x.prev = null; } //若后继结点为空，则前驱结点设为尾结点 if (next == null) { last = prev; } else { //若不是，指定结点前驱结点设为指定结点后继结点前驱，指定结点的后继设为null next.prev = prev; x.next = null; } //指定结点值设为null x.item = null; //长度-1 size--; modCount++; //返回被删除的结点值 return element; } /** * for循环从头遍历，删除第一次出现的指定元素 */ public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 删除从头开始第一出现的指定结点 */ public boolean removeFirstOccurrence(Object o) { return remove(o); } /** * 删除尾结点，若链表为空抛异常 */ public E removeLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 删除尾结点，若链表为空返回null */ public E pollLast() { final Node l = last; return (l == null) ? null : unlinkLast(l); } /** * 删除尾结点 */ private E unlinkLast(Node l) { // 获取尾结点值 final E element = l.item; // 获取尾结点前驱 final Node prev = l.prev; // 删除尾结点 l.item = null; l.prev = null; // help GC // 将原尾结点前驱设为尾结点 last = prev; // 若原尾结点的前驱结点为空，则首结点设为null if (prev == null) first = null; else //若不为null，原原尾结点的前驱结点的后继结点设为null prev.next = null; //长度-1 size--; modCount++; return element; } /** * 删除最后出现的结点 */ public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 清空LinkedList */ public void clear() { //循环遍历LinkedList，删除所有结点 for (Node x = first; x != null; ) { Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } //首尾结点置空 first = last = null; //长度设为0 size = 0; modCount++; }复制代码转换数组 public Object[] toArray() { // 声明一个LinkedList长度的数组 Object[] result = new Object[size]; int i = 0; //for遍历一一添加 for (Node x = first; x != null; x = x.next) result[i++] = x.item; return result; } 复制代码手撕简单实现public class LinkedList { private int size; private Node first; private Node last; public LinkedList() { } public void add(Object obj) { final Node lastNode = last; Node newNode = new Node(lastNode, obj, null); if (lastNode == null) { first = newNode; } else { lastNode.next = newNode; } last = newNode; size++; } public void add(int index, Object obj) { final Node node = getNode(index); final Node preNode = node.pre; if (index == size) { add(obj); return; } Node newNode = new Node(preNode, obj, node); node.pre = newNode; if (preNode == null) { first = newNode; } else { preNode.next = newNode; } size++; } public Object get(int index) { return getNode(index).item; } private Node getNode(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("越界"); } if (index < size << 1) { Node node = first; for (int i = 0; i < index; i++) { node = node.next; } return node; } else { Node node = last; for (int i = size - 1; i > index; i--) { node = node.pre; } return node; } } public void set(int index, Object obj) { Node node = getNode(index); node.item = obj; } public void remove(int index) { final Node node = getNode(index); final Node preNode = node.pre; final Node nextNode = node.next; if (preNode == null) { first = nextNode; } else { preNode.next = nextNode; node.pre = null; } if(nextNode == null){ last = preNode; } else { nextNode.pre = preNode; node.next = null; } node.item = null; size--; } private static class Node { private Object item; private Node pre; private Node next; public Node(Node pre, Object item, Node next) { this.item = item; this.pre = pre; this.next = next; } }} 复制代码结语
①.ArrayList相当于动态数组，LinkedList相当于双向链表可以被当作堆栈、队列、双端队列
②.ArrayList支持随机访问，而LinkedList需要一步步移动找到索引位置
③.ArrayList新增可能需要扩容预留内存，LinkedList不需要
④.ArrayList插入删除操作(非尾部)需要数组拷贝，LinkedList只需要修改结点的前驱后继
【转载】仅作分享，侵删
作者：午夜12点
链接：https://juejin.im/post/5abb3ad46fb9a028cd452389
|
|
收藏
淘帖
踩
