◆
LinkedList简介
◆
LinkedList实际上是通过双向链表去实现的。它继承于AbstractList,实现了List、 RandomAccess、Cloneable、Serializable这些接口。
◆
LinkedList的属性
◆
//List的大小 transient int size = 0; /** * 链表头部 */ transient Node<E> first; /** * 链表尾部 */ transient Node<E> last; /** * 特别注意这个是继承自AbstractList的属性,用来记录List被修改的次数 */ protected transient int modCount = 0;
相比较于ArrayList使用数组作为缓冲区,LinkedList使用的是一个内部的静态类Node来保存的,每个Node节点不光记录本身的数据,还保留了前一个节点和后一个节点的引用。所以本身LinkedList只保留了链表的头部和尾部的节点。
下方是Node的代码:
private static class Node<E> { //当前节点 E item; //后一个节点 Node<E> next; //前一个节点 Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
◆
LinkedList构造方法
◆
/** * 默认构造方法 */ public LinkedList() { } /** * 添加一个集合 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); } /** * 添加一个集合 */ public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }
/** * 从指定索引开始添加一个集合 */ public boolean addAll(int index, Collection<? extends E> c) { //判断下标是否越界 checkPositionIndex(index);
Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false;
Node<E> pred, succ; if (index == size) { //从链表尾部添加 succ = null; pred = last; } else { //从链表中间添加 succ = node(index); pred = succ.prev; }
for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //创建Node节点,指定Node的前一个节点 Node<E> newNode = new Node<>(pred, e, null); if (pred == null) //pred如果为空则代表整个链表为空, first = newNode; else pred.next = newNode; pred = newNode; }
if (succ == null) { //将节点放到最后 last = pred; } else { //将节点插入 pred.next = succ; succ.prev = pred; } //更新链表大小 size += numNew; //更新修改次数 modCount++; return true; }
◆
LinkedList的基本方法
◆
addAll方法添加一个集合还是比较简单粗暴的,接下来我们来看一下普通的add方法:
LinkedList不仅有普通的add方法,鉴于双向链表的特殊性,它还包含以下方法:
/** * 往最后添加一个元素 */ public boolean offer(E e) { return add(e); }
// Deque operations /** * 往第一个位置添加元素 */ public boolean offerFirst(E e) { addFirst(e); return true; }
/** * 往最后一个位置添加元素 */ public boolean offerLast(E e) { addLast(e); return true; } /** * 往List头部添加元素 */ public void push(E e) { addFirst(e); }
修改方法:
/** * 将指定索引的元素替换 */ public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }
删除方法:
/** * 删除第一个节点 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
/** * 删除最后一个节点 */ public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 删除元素 */ public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 删除节点 */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } /** * 删除第一个元素 */ public E remove() { return removeFirst(); } /** * 删除顺序遍历到的第一个存在的元素 */ public boolean removeFirstOccurrence(Object o) { return remove(o); }
/** * 删除逆序遍历到的最后一个存在的元素 */ public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
/** * 删除第一个节点 */ 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; }
/** * 删除最后一个节点 */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
/** * 删除x节点 */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev;
if (prev == null) { first = next; } else { prev.next = next; x.prev = null; }
if (next == null) { last = prev; } else { next.prev = prev; x.next = null; }
x.item = null; size--; modCount++; return element; }
查询方法:
/** * 获取第一个节点 */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
/** * 获取最后一个节点 */ public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } /** * 获取指定索引的元素 */ public E get(int index) { //判断是否越界 checkElementIndex(index); return node(index).item; }
/** * 获取第一个元素 */ public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }
/** * 获取第一个元素 */ public E element() { return getFirst(); }
/** * 弹出第一个元素(删除并获取) */ public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
/** * 获取第一个元素 */ public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } /** * 获取最后一个元素 */ public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } /** * 弹出第一个元素(删除并获取) */ public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
/** * 弹出最后一个元素(删除并获取) */ public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }
/** * * 弹出第一个元素(删除并获取) */ public E pop() { return removeFirst(); }
看了LinkedList的增删改查方法相信你已经明白了为什么一直有人告诉你LinkedList添加和删除效率高而随机查询修改效率低了。
序列化
/** * 将List写入s,注意先写容量,然后在写数据 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject();
// Write out size s.writeInt(size);
// Write out all elements in the proper order. for (Node<E> x = first; x != null; x = x.next) s.writeObject(x.item); }
/** * 从s读取,先读容量,再读数据 */ @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject();
// Read in size int size = s.readInt();
// Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); }
鉴于篇幅有限,本篇文章仅列出上方部分代码