方圆

jcf-linkedList

2019-09-15

1. Important Variables

1
2
3
4
5
transient int size = 0;
// 头节点指针
transient Node<E> first;
// 尾节点指针
transient Node<E> last;
1
2
3
4
5
6
7
8
9
10
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 使用双向链表实现,内部类Node用来表示一个节点。LinkedList 同时实现了 List 接口和 Deque 接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。关于栈或队列,现在的首选是ArrayDeque,当作栈或队列使用时,它有着比 LinkedList 有着更好的性能。

2. Main Mthods

  • add()
    有两种添加单个元素的方法,add(E e)和· add(int index, E element)

    • add(E e)在(链表)末尾加入元素,通过以下方法实现。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      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++;
      }
    • add(int index, E element) 添加到指定的位置,包括索引检查、添加在末尾就调用linkLast,否则调用linkBefore实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
                    // succ =node(index)
      void linkBefore(E e, Node<E> succ) {
      // e 插入到succ之前
      final Node<E> pred = succ.prev;
      final Node<E> newNode = new Node<>(pred, e, succ);
      succ.prev = newNode;
      if (pred == null)
      first = newNode;
      else
      pred.next = newNode;
      size++;
      modCount++;
      }
  • remove()
    也有两种remove方法,remove(int index)remove(Object o)删除指定位置或者与指定元素(可以为null)相等的第一个元素。最终都通过unlink(Node<E> x)来实现。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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; // 可GC
    size--;
    return element;
    }
  • get()
    通过调用node(int index)实现,返回指定位置的元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Node<E> node(int index) {
    if (index < (size >> 1)) {// 在前半部分
    Node<E> x = first;
    for (int i = 0; i < index; i++)
    x = x.next;
    return x;
    } else {// 在后半部分
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
    x = x.prev;
    return x;
    }
    }
  • set()
    修改指定位置元素的值。

    1
    2
    3
    4
    5
    6
    7
    public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
    }

3. 其他

  1. transient关键字表示序列化时忽略LinkedList的双指针都忽略了,序列化时如何保存数据呢?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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 (LinkedList.Node<E> x = first; x != null; x = x.next)
    s.writeObject(x.item);
    }

    查看源码我们发现LinkedList是通过writeObjectreadObject实现序列化和反序列化,序列化时存储size和每个数据。反序列化时读取size然后使用linkLast边读边重建。因为如果直接序列化链表反序列化时节点地址会改变,指向下一个节点的指针会失效。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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());
    }
Tags: jcf
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章