Collection:Java集合框架-LinkedList

LinkedList(基于JDK1.8)

LinkedList

• 是list接口 最常用的实现类 之一
• LinkedList 底层是 双向链表
• LinkedlList 可以应用在 “先进先出” “先进后出”的场景 在队列源码中被频繁使用

依赖关系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• 实现了 list 双向队列 可克隆 以及序列化接口
• 每个节点 叫做 Node Node有prev 代表前一个节点位置 next 代表后一个节点位置
• first 代表头结点 last代表尾节点
• 当链表为空是 两个节点是一个节点
• 链表 是 数据结构中 最简单的 动态数据结构
• 链表 引入了 指针（或者 引用）的概念

类注释说明

• 双向链表实现list 和deque 并且可以操作 null
• LinkedList 是线程不安全的 如果多个线程池并发地访问一个链表 至少其中一个线程在 结构上修改链表 它必须外部同步（链表修改可以是任意操作：添加，删除一个或多个元素 但是 设置元素的值 不是结构修改）通常通过对链表进行封装来完成的
• 推荐使用 Collections.synchronizedList 访问非同步链表 例子：List list = Collections.synchronizedList(new LinkedList(…));
• since：1.2

属性

transient int size = 0; // 默认大小

transient Node<E> first; // 指向第一个节点的指针

transient Node<E> last; // 只想最后一个节点的指针

关于 transient 关键字的作用

总所周知 实现了 Serializable 可以实现类的 序列化与反序列化 而此类中有的属性不想要在序列化与反序列化的时候 序列化与反序列化 添加此关键字 序列化的时候与反序列 不会被添加到指定的位置

构造器

public LinkedList() {
}

// 参数 为一个集合
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

方法

// 按照指定集合的迭代器返回的顺序
// 将集合中的 所有元素 最佳到 末尾
// 如果在操作的时候 修改了指定的集合
public boolean addAll(Collection<? extends E> c) {
	return addAll(size, c);
}

添加方法

// 将 指定的元素 追加到链表的末尾  等同于 addLast
	public boolean add(E e) {
    linkLast(e);
    return true;
	}

// 将 指定的元素 追加到链表的末尾
    public void addLast(E e) {
        linkLast(e);
    }

// 将 指定的元素 追加到链表的头部
    public void addFirst(E e) {
        linkFirst(e);
    }

LinkedList 的 静态内部类

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;
    }
}

删除方法

   // 删除 指定节点
   public E remove(int index) {
       checkElementIndex(index);
       return unlink(node(index));
   }

// 检索 并删除 第一个节点 等同于 removeFirst
// since ： 1.5
public E remove() {
       return removeFirst();
   }

// 删除 第一个节点
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);
   }

在指定的位置 操作节点

   // 链表第一个节点 即 头部
private void linkFirst(E e) {
       // 此节点 为 第一个节点
       final Node<E> f = first;
       final Node<E> newNode = new Node<>(null, e, f);
       first = newNode;
       if (f == null)
           last = newNode;
       else
           f.prev = newNode;
       size++;
       modCount++;
   }

// 链表最后一个节点 即 尾部
   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++;
   }

   /**
    * Inserts element e before non-null Node succ.
    */
// 在链表 不为空的 节点前 插入 即 插入succ 前一个节点
   void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
       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++;
   }

   /**
    * Unlinks non-null first node f.
    */
// 删除 第一个非空节点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;
   }

   /**
    * Unlinks non-null last node l.
    */
// 删除 最后一个非空节点l
   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;
   }

   /**
    * Unlinks non-null node x.
    */
// 删除 非空节点 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;
   }

有关 操作节点的说明

1. 操作头部 或者 尾部
2. 操作 非头部尾部

• 操作头部 或者 尾部 （头部为例）
  • 新增 新节点 prev 指向 null 而 它的 next 指向 原来链表的 头结点
  • 删除 旧节点 next 不在指向 下一个节点 原链表的 第二个节点 变为第一个节点 其prev指向 null
  • 尾部 和 上述 反之
• 操作 非头部
  • 新增 新节点 在指定位置 将prev 指向到 指定的 断开的节点的 前一个节点 将next 指向到 指定的 断开节点的 下一个节点
  • 删除 目标节点干掉 目标节点的前一个节点的next 指向到 目标节点的下一个节点 而 目标节点的prev 指向到 目标节点的上一个节点

1.5以后 实现Deque的一些方法

和前面的用处一样 只是实现的底层方式不同

// 检索 第一个 节点 但是不删除
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
// 检索 并且删除 第一个节点
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// 将 指定元素 添加到 最后一个节点
public boolean offer(E e) {
    return add(e);
}

1.6以后 实现Deque的一些方法

// 入栈 也就是说 往第一个节点添加元素
public void push(E e) {
    addFirst(e);
}
// 出栈 也就是说 移除 最后一个节点
public E pop() {
    return removeFirst();
}

小结 ：LinkedList 底层数据结构为 双向链表 内存够用的情况下 理论上是无限长的 LinkedList是线程不安全的 如果共享资源为 它 需要将它 外部同步 或者使用Collectionsd的synchronizedList(new LinkedList(…))方法

赏

谢谢你请我吃糖果