集合-03

三.LinkedList

1.LinkedList 数据结构？

如图所示，LinkedList 底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。

• LinkedList 底层数据结构为双向链表,实现了 List 和 Deque 两个接口。
• LinkedList 允许 null 值。
• 由于双向链表，顺序访问效率高，而随机访问效率较低。

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  transient int size = 0;
  transient Node<E> first;
  transient Node<E> last;
  public LinkedList() {
  }
}

2.add()和 offer()区别?

offer()直接调用了 add()方法

public boolean offer(E e) {
  return add(e);
}

public boolean add(E e) {
  linkLast(e);
  return true;
}

add 方法:在不违背队列的容量限制的情况，往队列中添加一个元素，如果添加成功则返回 true。
如果因为容量限制添加失败了，则抛出 IllegalStateException 异常

offer 方法:在不违背容量限制的情况，往队列中添加一个元素，如果添加元素成功，返回 true，
如果因为空间限制，无法添加元素则，返回 false；

• 在有容量限制的队列中，这个 offer 方法优于 add 方法。
• 因为抛异常处理更加耗时，offer 直接返回 false 的方式更好

3.offerLast 与 addLast()

offerLast()将元素链接到队列尾并返回 true。

所以能看出 offerLast()和 add()效果又是一样的。

public void addLast(E e) {
  linkLast(e);
}
public boolean offerLast(E e) {
  addLast(e);
  return true;
}

4.addLast()与 add()区别

• addLast()仅仅将元素链接到队列尾部。
• 然而 add()不仅将元素链接到队列尾部，还返回 true。
• 底层都是调用了 linkLast(e)方法

public void addLast(E e) {
  linkLast(e);
}
public boolean add(E e) {
  linkLast(e);
  return true;
}
//addFirst()仅将元素链接到队列首。
public void addFirst(E e) {
  linkFirst(e);
}

5.pollFirst 和 removeFirst

removeFirst:删除并返回队列首元素，若队列为空则抛出 Exception ! 这是 1.2 的版本，由于抛出异常处理起来较为麻烦。所以在 1.6 版本中推出了 poll 家族

pollFirst:删除并返回队列首元素，若队列为空则返回 null。 处理起来友善很多。

public E pollFirst() {
  final Node<E> f = first;
  return (f == null) ? null : unlinkFirst(f);
}

public E removeFirst() {
  final Node<E> f = first;
  if (f == null)
    throw new NoSuchElementException();
  return unlinkFirst(f);
}

6.poll 和 pop 的区别

poll 是队列数据结构实现类的方法，从队首获取元素，同时获取的这个元素将从原队列删除；

pop 是栈结构的实现类的方法，表示返回栈顶的元素，同时该元素从栈中删除，当栈中没有元素时，调用该方法会发生异常

7.LinkedList 变种

• LinkedList 继承了 AbstractSequentialList 类。
• LinkedList 实现了 Queue 接口，可作为队列使用。
• LinkedList 继承了 AbstractQueue 抽象类，具有队列的功能。
• LinkedList 实现了 List 接口，可进行列表的相关操作。
• LinkedList 实现了 Deque 接口，可作为双向队列使用。
• LinkedList 实现了 Cloneable 接口，可实现克隆。
• LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

8.LinkedList 使用总结

• 需要链接元素到队列尾时优先用offer()
• 查看元素优先使用peek()
• 删除元素优先使用poll()

特别情况：

• 想要在指定索引位置链接元素可以使用 add(int index, E element)
• 获取指定索引的元素可以使用 get(int index)
• 修改指定索引的元素可以使用 set(int index, E newElement)