微信网站应用开发/seo培训课程-南充网站建设

引言

LinkedList是Java集合中重要的一个实现,其底层才用双向链表结构。和ArrayList一样,LinkedList也支持空值和重复值。由于LinkedList底层基于链表实现,存储过程中,无需像ArrayList那样进行扩容.但有得必有失，LinkedList存储元素的节点需要额外的空间前驱和后继的引用.另外,LinkedList在头部和尾部插入效率比较高,但是在制定位置进行插入时,效率一般.原因是,在指定位置插入需要定位到该位置处的节点,此操作的时间复杂度为O(N)。最后,LinkedList是非线程安全的集合类,并发环境下,多个线程同时操作LinkeList,会引发不可预知的错误.

结构体系

从结构体系我们可以大致其总结特性：

实现了List接口，提供了对数据的增删查该功能
实现了Deque接口,可用于双端队列
实现了Cloneable接口,可被浅拷贝
实现了Serializable接口,可被序列化

属性

 transient int size = 0; //表示元素的个数transient Node<E> first;//1.8中 结构是双向链表,所以这是头结点transient Node<E> last; //尾节点
复制代码

构造函数

无参构造函数
```
 public LinkedList() {}
复制代码
```
啥也不干。

带集合参数的构造函数

  public LinkedList(Collection<? extends E> c) {this();addAll(c);}public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}
//可以将addAll方法理解成一个插入方法 index即为准备插入节点下标
public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index); //检查下标 区间为 0到sizeObject[] a = c.toArray();  //调用集合的toArray()方法将其转化为数组int numNew = a.length; //获取数组的长度if (numNew == 0) //长度为0 直接返回 表示addAll失败return false;Node<E> pred, succ; //prev表示前置节点 succ表示后置节点if (index == size) { //如果是在尾部插入succ = null; 后置节点为nullpred = last; 前置节点为最后一个} else {succ = node(index); //后置节点为index对应的节点 pred = succ.prev; //前置节点为 index对应节点的前一个}for (Object o : a) { //增强for循环 代码更加简介@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null); //实例节点的时候赋值前置节点以及元素if (pred == null) //如果前置节点为空，则该节点为头结点first = newNode; elsepred.next = newNode; //否则的话设置新节点为前置节点的下一个节点pred = newNode; //将当前的节点作为新的前置节点}//遍历完成后 需要将最后一个节点与后置节点连接if (succ == null) { //如果后置节点为null 则表示最后一个节点即为尾部节点last = pred;} else { //否则,将最后一个节点与尾部连接pred.next = succ;succ.prev = pred;}size += numNew; //更新元素的大小modCount++; //修改更改的次数return true; //返回true表示更新成功
}
private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {return index >= 0 && index <= size;
}
复制代码

增加元素

add(E e)

public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final Node<E> l = last; //得到last节点final Node<E> newNode = new Node<>(l, e, null); //新建连接左边连接last节点last = newNode; //将新的节点赋值给lastif (l == null) //如果 最初的last节点为空 则 当前节点为头结点first = newNode;elsel.next = newNode; //否则 将新节点与最初的last节点相连size++; //增加元素个数modCount++; //增加修改次数
}
复制代码

该方法比较比较简单,只是创建了一个新节点插入在了链表的尾部而已.

add(int index, E element),可以把该方法当做单个插入的方法

public void add(int index, E element) {checkPositionIndex(index); //检查下标是否合法if (index == size) //如果是在尾部,插入在尾部即可linkLast(element);else //否则,插在node(index)节点之前linkBefore(element, node(index));}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) //连接前面 如果前置节点为null 则将当前节点设置为头节点first = newNode;else //否则与前置节点相连接pred.next = newNode;size++;modCount++;
}
复制代码

获取元素

get(int index)

public E get(int index) {checkElementIndex(index); //检查下标是否合法return node(index).item; //只杰根据node方法查找到节点并返回其元素即可}Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) { //位运算 表示 index<size/2 即偏向头结点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;}}
复制代码

可以看到，双向链表在这里起到的作用,在查找的时候,先根据index判断节点更靠近头部还是尾部,提升查找的效率。

删除元素

remove(int index)

public E remove(int index) {checkElementIndex(index);return unlink(node(index));}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;}
复制代码

检查下标合法后,直接调用unlink方法将该节点移除.在unlink方法中可以看到,将被移除的节点的前后节点以及元素都赋值为null，方便GC回收.

修改元素

set(int index, E element)

public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}
复制代码

也很简单,不再赘述,现实用node(int index)方法定位到对应节点,然后修改其值即可。

LinkedList总结

底层使用链表进行数据存储,不需要扩容
增加和删除元素效率比较高,执行相应的链表操作即可
查找和修改的效率比较低,虽然遍历之前根据下标判断了遍历起点,但是节点比较多的时候,效率会大幅缩减

引言