百度做网站免费,中山网上房地产,外贸网站seo推广,工贸企业logo设计JDK版本为1.8.0_271#xff0c;以插入和删除元素为例#xff0c;LinkedList部分源码如下#xff1a;
//属性#xff0c;底层结构为双向链表
transient NodeE first; //记录第一个结点的位置
transient NodeE last; //记录最后一个结点的尾元素
transient …JDK版本为1.8.0_271以插入和删除元素为例LinkedList部分源码如下
//属性底层结构为双向链表
transient NodeE first; //记录第一个结点的位置
transient NodeE last; //记录最后一个结点的尾元素
transient int size 0; //记录链表的元素个数//内部Node类定义如下
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;}
}//构造器
public LinkedList() {
}//方法add()相关方法
public boolean add(E e) {linkLast(e); //默认把新元素链接到链表尾部return true;
}// 尾部插入一个新节点
void linkLast(E e) {final NodeE l last; //用 l 记录原来的最后一个结点//创建新结点final NodeE newNode new Node(l, e, null);//现在的新结点是最后一个结点了last newNode;//如果lnull说明原来的链表是空的if (l null)//那么新结点同时也是第一个结点first newNode;else//否则把新结点链接到原来的最后一个结点的next中l.next newNode;//元素个数增加size;//修改次数增加modCount;
}//方法获取get()相关方法
public E get(int index) {// 校验index是否越界合法范围:[0,size)checkElementIndex(index);return node(index).item;
} //方法插入add()相关方法
public void add(int index, E element) {checkPositionIndex(index); // 校验index是否越界合法范围:[0,size)if (index size)//如果indexsize链接到当前链表的尾部linkLast(element);elselinkBefore(element, node(index));
}// 查找index位置节点
NodeE node(int index) {// assert isElementIndex(index);/*index (size 1)采用二分思想先将index与长度size的一半比较如果indexsize/2就只从位置0往后遍历到位置index处如果indexsize/2就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历。*///如果indexsize/2就从前往后找目标结点if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {//否则从后往前找目标结点NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
}//把新结点插入到[index]位置的结点succ前面succ是[index]位置对应的结点
void linkBefore(E e, NodeE succ) {// assert succ ! null;final NodeE pred succ.prev; //[index]位置的前一个结点//新结点的prev是原来[index]位置的前一个结点//新结点的next是原来[index]位置的结点final NodeE newNode new Node(pred, e, succ);//[index]位置对应的结点的prev指向新结点succ.prev newNode;//如果原来[index]位置对应的结点是第一个结点那么现在新结点是第一个结点if (pred null)first newNode;elsepred.next newNode;//原来[index]位置的前一个结点的next指向新结点size;modCount;
}//方法remove()相关方法
public boolean remove(Object o) {//分o是否为空两种情况if (o null) {//找到o对应的结点xfor (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);//删除x结点return true;}}} else {//找到o对应的结点xfor (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);//删除x结点return true;}}}return false;
}
// 将节点x从链表中取下
E unlink(NodeE x) {//x是要被删除的结点// assert x ! null;final E element x.item;//被删除结点的数据final NodeE next x.next;//被删除结点的下一个结点final NodeE prev x.prev;//被删除结点的上一个结点//如果被删除结点的前面没有结点说明被删除结点是第一个结点if (prev null) {//那么被删除结点的下一个结点变为第一个结点first next;} else {//被删除结点不是第一个结点//被删除结点的上一个结点的next指向被删除结点的下一个结点prev.next next;//断开被删除结点与上一个结点的链接x.prev null;//使得GC回收}//如果被删除结点的后面没有结点说明被删除结点是最后一个结点if (next null) {//那么被删除结点的上一个结点变为最后一个结点last prev;} else {//被删除结点不是最后一个结点//被删除结点的下一个结点的prev执行被删除结点的上一个结点next.prev prev;//断开被删除结点与下一个结点的连接x.next null;//使得GC回收}//把被删除结点的数据也置空使得GC回收x.item null;//元素个数减少size--;//修改次数增加modCount;//返回被删除结点的数据return element;
}// 删除index位置的节点
public E remove(int index) { //index是要删除元素的索引位置// 校验index范围checkElementIndex(index);// 将节点x从链表中取下return unlink(node(index));
}// 插入新节点链表头结点
public void addFirst(E e) {linkFirst(e);
}
// 链接节点到链表头
private void linkFirst(E e) {final NodeE f first; // 获取链表头节点final NodeE newNode new Node(null, e, f); // 新建节点first newNode; // 更新头结点if (f null) // 原链表为空时last newNode; // 将链表last指向新的头结点else // 双端链表将原头结点的prev指向新的头结点f.prev newNode;size; // 链表节点数1modCount; // 链表修改次数1
}// 获取链表的头结点的元素
public E getFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return f.item;
}
// addLast尾插法插入节点getLast获取链表尾结点插入删除结点的过程如图所示
只有1个元素的LinkedList 包含4个元素的LinkedList add(E e)方法 add(int index,E e)方法 remove(Object obj)方法 remove(int index)方法
