网站资讯创作,可以做内容的网站,做视频给网站到流量,小微企业2022年税收优惠政策LinkedList里面涉及到的一些操作#xff0c;非常细致#xff0c;以避免出现的空指针#xff0c;理解后对于其优点与确定会有一个更加整体的认识吧。
继承关系图(对比ArrayList) 元素的存储结构 在LinkedList中#xff0c;每一个元素都是Node存储#xff0c;Node拥有一个存…LinkedList里面涉及到的一些操作非常细致以避免出现的空指针理解后对于其优点与确定会有一个更加整体的认识吧。
继承关系图(对比ArrayList) 元素的存储结构 在LinkedList中每一个元素都是Node存储Node拥有一个存储值的item与一个前驱prev和一个后继next如下
// 典型的链表结构
private static class NodeE {E item;// 存储元素NodeE next;// 指向上一个元素NodeE prev;// 指向下一个元素Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}构造函数与成员变量 变量主要有3个
transient int size 0;//当前列表的元素个数
/*** Pointer to first node.* Invariant: (first null last null) ||* (first.prev null first.item ! null)*/
transient NodeE first;// 第一个元素
/*** Pointer to last node.* Invariant: (first null last null) ||* (last.next null last.item ! null)*/
transient NodeE last;// 最后一个元素在LinkedList中的构造函数有两个一个是无参的另一个是带Collection参数的。
public LinkedList() {}//无参构造函数
public LinkedList(Collection? extends E c) {this();addAll(c);//将c中的元素都添加到此列表中
} 其添加的过程中此时size 0如下
public boolean addAll(Collection? extends E c) {return addAll(size, c);//此时 size 0
} 如果indexsize则添加c中的元素到列表的尾部否则添加的第index个元素的前面
public boolean addAll(int index, Collection? extends E c) {// 检查位置是否合法 位置是[0,size]注意是闭区间 否则报异常checkPositionIndex(index);Object[] a c.toArray();// 得到一个元素数组int numNew a.length;// c中元素的数量if (numNew 0)return false;// 没有元素添加失败// 主要功能是找到第size个元素的前驱和后继。得到此元素需要分情况讨论。// 这段代码是各种情况的总和可能有一点点容易懵逼。NodeE pred, succ;// 前驱与后继if (index size) {// 如果位置与当前的size相同succ null;// 无后继pred last;// 前驱为last即第size个元素(最后一个元素)} else {// 若与size不同即index位于[0, size)之间succ node(index);// 后继为第index个元素pred succ.prev;// 前驱为后继的前驱}// 后文有详细的图片说明// 开始逐个插入for (Object o : a) {SuppressWarnings(unchecked) E e (E) o;// 新建一个以pred为前驱、null为后继、值为e的节点NodeE newNode new Node(pred, e, null);if (pred null)// 前驱为空则此节点被当做列表的第一个节点first newNode;else// 规避掉了NullPointerException感觉又达到了目的又实现了逻辑pred.next newNode;// 不为空则将前驱的后继改成当前节点pred newNode;// 将前驱改成当前节点以便后续添加c中其它的元素}// 至此c中元素已添加到链表上但链表中从size开始的那些元素还没有链接到列表上// 此时就需要利用到之前找出来的succ值它是作为这个c的整体后继if (succ null) {// 如果后继为空说明无整体后继last pred;// c的最后一个元素应当作为列表的尾元素} else {// 有整体后继pred.next succ;// pred即c中的最后一个元素其后继指向succ即整体后继succ.prev pred;// succ的前驱指向c中的最后一个元素}// 添加完毕修改参数size numNew;modCount;return true;
} 返回序号为index的元素节点。看这段代码中的if语句真的是佩服这样写代码都可以这样减少查找次数。
NodeE node(int index) {// assert isElementIndex(index);// 这个地方很有意思。视其与中值得差距觉得从前遍历还是从后遍历。if (index (size 1)) {NodeE x first;// 循环index次 迭代到所需要的元素for (int i 0; i index; i)x x.next;return x;} else {NodeE x last;// 循环size-1-index次for (int i size - 1; i index; i--)x x.prev;return x;}
} 测试代码以及验证输出如下
public class Main {public static void main(String[] args) {ListString list new LinkedList(Arrays.asList(1, 2, 3));System.out.println(list.toString());list.addAll(2, Arrays.asList(4, 5));System.out.println(list.toString());list.addAll(0, Arrays.asList(6, 7));System.out.println(list.toString());}
}
---
[1, 2, 3]
[1, 2, 4, 5, 3]
[6, 7, 1, 2, 4, 5, 3] 增加元素 对于向列表中添加元素先看一组基本的添加操作具体如下
将e链接成列表的第一个元素 源代码以及相应的分析如下
private void linkFirst(E e) {final NodeE f first;// 前驱为空值为e后继为ffinal NodeE newNode new Node(null, e, f);first newNode;// first指向newNode// 此时的f有可能为nullif (f null)// 若f为空则表明列表中还没有元素last newNode;// last也应该指向newNodeelsef.prev newNode;// 否则前first的前驱指向newNodesize;modCount;
} 其过程大致如下两图所示 初始状态 后续状态 添加元素作为第一个元素时所需要做的工作有下列所述 首先获取第一个节点然后将该节点的前驱指向新添加的元素所在的节点 接着将新添加的节点的后继指向前第一个节点 最后将first指向新添加的元素的节点。添加完毕。 将e链接为最后一个元素 源代码以及相应的解释如下
void linkLast(E e) {final NodeE l last;// 找到最后一个节点// 前驱为前last值为e后继为nullfinal NodeE newNode new Node(l, e, null);last newNode;// last一定会指向此节点if (l null)// 最后一个节点为空说明列表中无元素first newNode;// first同样指向此节点elsel.next newNode;// 否则前last的后继指向当前节点size;modCount;
} 其操作过程与前述linkFirst()的过程类似因此其替换后的示意图如下 将e链接到节点succ前 源代码以及相应的解析如下
void linkBefore(E e, NodeE succ) {// assert succ ! null;final NodeE pred succ.prev; // 找到succ的前驱// 前驱为pred值为e后继为succfinal NodeE newNode new Node(pred, e, succ);// 将succ的前驱指向当前节点succ.prev newNode;if (pred null)// pred为空说明此时succ为首节点first newNode;// 指向当前节点elsepred.next newNode;// 否则将succ之前的前驱的后继指向当前节点size;modCount;
} 这个操作有点类似将上述的两个操作整合到一起。其操作简图如下 有了上述的分析我们再来看一些添加的操作这些操作基本上是做了一些逻辑判断然后再调用上述三个方法去实现添加功能这里略过就好。 public boolean add(E e) {linkLast(e);return true;}// 只有这个是有一点逻辑的public void add(int index, E element) {checkPositionIndex(index);if (index size)// 为最后一个节点当然是添加到最后一个~linkLast(element);elselinkBefore(element, node(index));}public void addFirst(E e) {linkFirst(e);}public void addLast(E e) {linkLast(e);} 删除元素 删除就是添加过程的逆过程。同样在分析我们使用的接口前先分析几个我们看不到的方法如下
删除首节点
private E unlinkFirst(NodeE f) {// assert f first f ! null;别忽略这里的断言final E element f.item;// 取出首节点中的元素final NodeE next f.next;// 取出首节点中的后继f.item null;f.next null; // help GCfirst next;// first指向前first的后继也就是列表中的2号位if (next null)// 如果此时2号位为空那么列表中此时已无节点last null;// last指向nullelsenext.prev null;// 首节点无前驱size--;modCount;return element;// 返回首节点保存的元素值
} 删除尾节点 此处的操作与删除首节点的操作类似。
private E unlinkLast(NodeE l) {
// assert l last l ! null;别忽略这里的断言
final E element l.item;// 取出尾节点中的元素
final NodeE prev l.prev;// 取出尾节点中的后继
l.item null;
l.prev null; // help GC
last prev;// last指向前last的前驱也就是列表中的倒数2号位
if (prev null)// 如果此时倒数2号位为空那么列表中已无节点first null;// first指向null
elseprev.next null;// 尾节点无后继
size--;
modCount;
return element;// 返回尾节点保存的元素值
} 删除某个非空节点 这个也类似添加元素时的第三个基本操作与结合了上述两个操作有点类似。
// x即为要删除的节点
E unlink(NodeE x) {
// assert x ! null;
final E element x.item;// 保存x的元素值
final NodeE next x.next;// 保存x的后继
final NodeE prev x.prev;// 保存x的前驱if (prev null) {// 前驱为null说明x为首节点first next;// first指向x的后继
} else {prev.next next;// x的前驱的后继指向x的后继即略过了xx.prev null;// x.prev已无用处置空引用
}if (next null) {// 后继为null说明x为尾节点last prev;// last指向x的前驱
} else {next.prev prev;// x的后继的前驱指向x的前驱即略过了xx.next null;// x.next已无用处置空引用
}x.item null;// 引用置空
size--;
modCount;
return element;// 返回所删除的节点的元素值
} 有了上面的几个函数作为支撑我们再来看下面的几个我们能用来删除节点的方法他们也基本上是在一些逻辑判断的基础之上再调用上述的基本操作
public E removeFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return unlinkFirst(f);
}
public E removeLast() {final NodeE l last;if (l null)throw new NoSuchElementException();return unlinkLast(l);
}
// 遍历列表中所有的节点找到相同的元素然后删除它
public boolean remove(Object o) {if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);return true;}}} else {for (NodeE 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));
}修改元素 通过遍历循环index次获取到相应的节点后再通过节点来修改元素值。
public E set(int index, E element) {checkElementIndex(index);NodeE x node(index);// 获取到需要修改元素的节点E oldVal x.item;// 保存之前的值x.item element;// 修改return oldVal;// 返回修改前的值} 查询元素
通过位置循环index次获取到节点然后返回该节点中元素的值public E get(int index) {checkElementIndex(index);return node(index).item;// 获取节点并返回节点中的元素值
} 还有两个获取首尾节点的元素的方法public E getFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return f.item;
}
public E getLast() {final NodeE l last;if (l null)throw new NoSuchElementException();return l.item;
} 获取元素位置
从0开始往后遍历public int indexOf(Object o) {int index 0;if (o null) {// null时分开处理for (NodeE x first; x ! null; x x.next) {if (x.item null)// 说明找到return index;// 返回下标index;}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item))// 说明找到return index;// 返回下标index;}}return -1;// 未找到返回-1
} 从size - 1开始遍历。基本操作与上述操作类似只是起始位置不同。public int lastIndexOf(Object o) {int index size;if (o null) {for (NodeE x last; x ! null; x x.prev) {index--;if (x.item null)return index;}} else {for (NodeE x last; x ! null; x x.prev) {index--;if (o.equals(x.item))return index;}}return -1;
} 额外的话 在上面的诸多函数中有许多是需要进行位置判断的。在源码中位置判断有两个函数一个是下标一个是位置。看到这两个函数确实是有一些感触这确实是需要比较强的总结能力以及仔细的观察能力。
// 下标保证数组访问不越界。
private boolean isElementIndex(int index) {return index 0 index size;
}
// 位置
private boolean isPositionIndex(int index) {return index 0 index size;
} 后记 LinkedList还实现了Queue这个接口在实现这些接口时仍然是做一些逻辑处理然后调用上面所描述的基本操作如link()、unlink()之类的因此不再分析。还有其中的关于序列化、Iterator这两块与ArrayList的实现也是不尽相同的故在此可参考ArrayList中的解析。
