这是JDK1.8的分析,可能分析的不够好,各位大佬多指点一下 结合这张图看比较容易理思路 1.怎么实现的? 双向链表 Node first 第一结点 Node last 最后一个结点
transient int size = 0; //实际元素个数 transient Node<E> first; //指向第一个结点的指针 transient Node<E> last; //指向最后一个结点的指针 //默认new 了一个空的构造方法 public LinkedList() { }2.怎么add()添加的? 默认添加到链表的尾部
public boolean add(E e) { linkLast(e); //方法默认将指定的元素追加到此列表的末尾 return true; } void linkLast(E e) { //默认指向最后一个结点元素 final Node<E> l = last; //new了一个新结点 final Node<E> newNode = new Node<>(l, e, null); //新结点指向到最后的结点 last = newNode; if (l == null) //如果最后一个结点是空链表null first = newNode; //新结点就指向到第一个结点 else //不是空链表 l.next = newNode; //新元素添加到此链表最后一个结点 size++; //元素个数 modCount++; //添加次数 }3.指定位置怎么添加?
// 指定索引 元素 public void add(int index, E element) { checkPositionIndex(index); //检查索引位置的合理性方法 if (index == size) //如果当前索引等于元素长度 linkLast(element); //那么连接到链表的最后 else //不等于元素长度 元素 指定索引 linkBefore(element, node(index));//element元素否则在链表前面插入, node(index)找到指定位置的节点 } ---------------------------------------------------------------------------- //检查索引位置的合理性方法 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); //不合理报索引越界异常 } ---------------------------------------------------------------------------- 指定索引 Node<E> node(int index) { //判断:假设siez是10原来长度除以2是5个长度链表,现在链表索引是2,那就在5前面 if (index < (size >> 1)) { Node<E> x = first; //前面一个结点 for (int i = 0; i < index; i++)//前面往后遍历找到索引节点位置返回 x = x.next; return x; } else { // 否则如果插入索引是6大于 Node<E> x = last; //最后一个结点 for (int i = size - 1; i > index; i--) x = x.prev; return x; //后面往前面遍历找到节点索引返回 } } ---------------------------------------------------------------------------- 元素 例如遍历找出的结点2 void linkBefore(E e, Node<E> succ) { // 2结点前面插入是1结点 final Node<E> pred = succ.prev; //插入进来(前一个元素1,插入元素,后一个元素2) final Node<E> newNode = new Node<>(pred, e, succ); //这里意思是,新元素插入进来,就要关联前后指针,那么这句是新的指针要指向后面的节点指针 succ.prev = newNode; //如果插入最前面结点是null if (pred == null) first = newNode; //新结点在链表第一个节点最前面 else //这里关联新的指针指向前面结点 pred.next = newNode; size++; //元素个数 modCount++;//增加次数 }4.如果删除方法怎么做? 假设1 2 3 个结点,删除了2断开二边的指针. 这里删除要删除前一个和后一个指针,连接关系怎么维护?
transient int size = 0; //实际元素个数 transient Node<E> first; //指向第一个结点的指针 transient Node<E> last; //指向最后一个结点的指针 public boolean remove(Object o) { //元素如果是空 if (o == null) { //first前面结点遍历 for (Node<E> x = first; x != null; x = x.next) { //如果值是null,因为要删除结点拿item对象. 属性 E item; 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; } ---------------------------------------------------------------------------- 结点对象 E unlink(Node<E> x) { // assert x != null; final E element = x.item; //中间结点ndoe对象 final Node<E> next = x.next; //后一个结点指针 final Node<E> prev = x.prev; //前一个结点指针 //如果前一个结点指针是指向是null,链表中第一个结点 if (prev == null) { first = next; // next指向下一个结点的第一个结点 //如果前一个结点指针不是null,不是第一个 } else { prev.next = next; //后一个结点对象指前一个结点对象 x.prev = null; // 给结点对象指针前面指向null } if (next == null) { //如果链表后一个next指针null last = prev; //指向last } else { //不是null next.prev = prev; // 前一个prev指针,指向前一个结点node对象next后面 x.next = null;//结点对象后面指针给null } x.item = null; //node元素结点是空了,删掉了 size--; //长度 modCount++; //次数 return element; }