郑州网站优化公司哪家好,网站迁移教程,网站怎么做的支付宝接口,巩义市住房和城乡规划建设局网站链表数据结构 当前节点会保存上一个、下一个节点。 参见 LinkedList的Node类 实现#xff1a; 1. 内部链表的方式。 1.1 添加元素。追加的方式#xff0c;创建一个新的节点[Node]#xff0c;用最后一个节点关联新的节点。 1.2 删除元素… 链表数据结构 当前节点会保存上一个、下一个节点。 参见 LinkedList的Node类 实现 1. 内部链表的方式。 1.1 添加元素。追加的方式创建一个新的节点[Node]用最后一个节点关联新的节点。 1.2 删除元素 1.2.1 通过对象删除。遍历链表删除第一个匹配的对象 修改链表关联结构 2. 内部是同步[modCount] 2.1 LinkedList数据结构变化的时候都会将modCount。 2.2 采用Iterator遍历的元素 next()会去检查集合是否被修改[checkForComodification]如果集合变更会抛出异常 类似于数据库层面的 乐观锁 机制。 可以通过 Iterator的api去删除元素 3. 数组结构内部存储数据是有序的并且数据可以为null 源码实现 package xin.rtime.collections.list;import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;// 链表的源码实现
public class LinkedListE {transient int size 0; // 当前链表的sizetransient NodeE first; // 首节点transient NodeE last; // 尾节点private int modCount 0; // 结构修改次数// 添加节点public boolean add(E e) {linkLast(e);return true;}// 删除节点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)) { // equalsunlink(x);return true;}}}return false;}// 获取节点public E get(int index) {checkElementIndex(index); // 检查元素Index是否存在 不存在会抛出数组越界return node(index).item;}// 获取链表sizepublic int size() {return size;}public IteratorE iterator() {return listIterator();}public ListIteratorE listIterator() {return listIterator(0);}NodeE node(int index) {// assert isElementIndex(index);if (index (size 1)) { // 当前index 小于 当前一半容量的 sizeNodeE x first; // 当前节点 等于 首节点for (int i 0; i index; i) // 遍历 index -1 次x x.next; // x 等于当前节点的下一个节点return x;} else { // 大于NodeE x last;for (int i size - 1; i index; i--) // 从尾部开始遍历x x.prev; // x 等于当前节点的上一个节点return x;}}private void checkElementIndex(int index) {if (!isElementIndex(index)) // 节点index是否在链表的容量范围内throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int index) {return index 0 index size;}private String outOfBoundsMsg(int index) {return Index: index, Size: size;}// 获得首个节点值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;}// 获得所有节点值public Object[] toArray() {Object[] result new Object[size];int i 0;for (NodeE x first; x ! null; x x.next)result[i] x.item;return result;}public ListIteratorE listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}// 判断当前节点index是否存在private boolean isPositionIndex(int index) {return index 0 index size;}private class ListItr implements ListIteratorE {private NodeE lastReturned null; // 返回的节点private NodeE next; // 下个节点private int nextIndex; // 下个节点 下标private int expectedModCount modCount; // 预期的修改次数 等于遍历时的修改次数
ListItr(int index) {// assert isPositionIndex(index);next (index size) ? null : node(index);nextIndex index;}public boolean hasNext() {return nextIndex size;}public E next() {checkForComodification(); // 校验当前链表是否被改动if (!hasNext())throw new NoSuchElementException();lastReturned next;next next.next;nextIndex;return lastReturned.item;}public boolean hasPrevious() {return nextIndex 0;}public E previous() {checkForComodification(); // 校验当前链表是否被改动if (!hasPrevious())throw new NoSuchElementException();lastReturned next (next null) ? last : next.prev;nextIndex--;return lastReturned.item;}public int nextIndex() {return nextIndex;}public int previousIndex() {return nextIndex - 1;}public void remove() {checkForComodification(); // 校验当前链表是否被改动if (lastReturned null)throw new IllegalStateException();NodeE lastNext lastReturned.next;unlink(lastReturned); // 剔除节点if (next lastReturned)next lastNext;elsenextIndex--;lastReturned null;expectedModCount;}// 当前节点设置值public void set(E e) {if (lastReturned null)throw new IllegalStateException();checkForComodification();lastReturned.item e; }public void add(E e) {checkForComodification();lastReturned null;if (next null) // 下一个节点为nulllinkLast(e); // 在尾部插入elselinkBefore(e, next); // 在指定节点之前插入nextIndex;expectedModCount;}final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();}}private E unlink(NodeE x) {final E element x.item; // 当前元素final NodeE next x.next; // 下一个节点 final NodeE prev x.prev; // 上一个节点if (prev null) { // 上一个节点为空first next; // 首节点 当前节点下一个节点} else { // 不为空prev.next next; // 上一个节点的下一个节点 等于 当前节点的 下一个节点x.prev null; // 当前节点的上一个节点置为null gc回收}if (next null) { // 下一个节点为空last prev; // 最后节点 当前节点的上一个节点} else { // 不为空 next.prev prev; // 上一个节点的上一个节点 等于 当前节点的上一个节点x.next null; // 当前节点的下一个节点置为null gc回收}x.item null; // 当前元素置为null gc回收size--; // 长度 1modCount; // 修改次数1return element;}// 在链表的尾部插入节点void linkLast(E e) {final NodeE l last; // 最后一个元素final NodeE newNode new Node(l, e, null); // 上一个元素当前元素nulllast newNode; // 最后一个节点等新建的节点if (l null) // 如果最后一个节点为空first newNode; // 出现一个情况 当链表为空的时候 , first 和 last 都为 newNodeelsel.next newNode; //最后节点的下一个节点等于当前节点size; // 链表长度1modCount; // 修改次数1}// 在指定节点添加上一个节点void linkBefore(E e, NodeE succ) {// assert succ ! null;final NodeE pred succ.prev;final NodeE newNode new Node(pred, e, succ);succ.prev newNode;if (pred null)first newNode;elsepred.next newNode;size;modCount;}// 链表节点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;}}
} 转载于:https://www.cnblogs.com/LuisYang/p/10034601.html
