做网站域名多少钱/2023新闻大事10条

       为了更深一步的学习掌握Java中的集合类，最近决定把Java中比较常用的集合类源码学习一下。

       今天就把我对LinkedList源码的理解跟大家分享下，JDK版本是1.7（不同版本的源码可能略有差异，但是思想几乎不变）。

       LinkedList底层是由双向链表来实现，我主要从add、get、remove以及它的构造函数还有一些关键参数（Node结点类）理解它。

       LinkedList是一个继承于AbstractSequentialList的双向链表。inkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。LinkedList是非同步的。

1、Node结点类

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

2、LinkedList关键参数

       transientint size = 0;              //链表的大小

       transient Node<E> first;          //链表的头结点

       ransient Node<E> last;             //链表的尾结点

3、LinkedList构造函数

（1）空构造函数

public LinkedList() {}

（2）带参构造函数

public LinkedList(Collection<? extends E> c) {this();addAll(c);}public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}public boolean addAll(int index, Collection<? extends E> c) {//首先检验index的值是否在有效范围之内checkPositionIndex(index);Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;//确定待插入的节点的位置及其前驱和后继结点引用Node<E> pred, succ;//表示头结点或者尾结点插入if (index == size) {succ = null;pred = last;} else {//表示中间结点插入succ = node(index);pred = succ.prev;}//（无论插入多少节点，后继结点的引用不会变，只需要不断改变前驱节点引用即可）for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;//表示新结点的上一结点是prevNode<E> newNode = new Node<>(pred, e, null);if (pred == null)first = newNode;else//表示上一结点的下一结点现在指向了newNode（很重要）//(链表插入新的节点（只考虑与前驱结点的操作）,首先要保证新插入的节点指向前驱结点,另外也要保证前驱结点的引用指向新结点，这个是双向操作)pred.next = newNode;pred = newNode;}//处理后继结点if (succ == null) {last = pred;} else {//前后节点的互相引用，双向操作pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}//某一索引对应的结点Node<E> node(int index) {// assert isElementIndex(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;}}

其中对addAll（）的应用及其使用场景要清楚，即怎么在双向链表中添加结点元素。（分两种情况：空链表和非空链表（分三种情况：头结点、尾结点、中间结点））。

4、add方法

//在链表后边添加node结点。public boolean add(E e) {linkLast(e);return true;}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;elsel.next = newNode;size++;modCount++;}

5、get方法

public E get(int index) {checkElementIndex(index);//返回对应node结点的数据内容return node(index).item;}

6、remove方法

（1）E remove(intindex)

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;}//将删除节点的内容数据置空，便于GC回收x.item = null;size--;modCount++;return element;}

（2）boolean remove(Object o)

public boolean remove(Object o) {//首先分成两种情况找到相对应的node节点（第一个节点内容是o的节点）if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}