## 动力学知识库

• Node节点
• remove方法
• get方法

### (一)Node节点

1 private static class Node<E> { 2 E item; 3 Node<E> next; 4 Node<E> prev; 5 6 Node(Node<E> prev, E element, Node<E> next) { 7 this.item = element; 8 this.next = next; 9 this.prev = prev;10 }11 }

1 void linkLast(E e) { 2 //将链表的last节点给l 3 final Node<E> l = last; 4 final Node<E> newNode = new Node<>(l, e, null); 5 last = newNode; 6 //如果是第一个节点 7 if (l == null) 8 first = newNode; 9 //直接加入到尾节点的后面去10 else11 l.next = newNode;12 size++;13 modCount++;14 }

1 public void add(int index, E element) { 2 //检查插入位置是否合法 3 checkPositionIndex(index); 4 5 //如果插入到最后，直接调用linkLast方法 6 if (index == size) 7 linkLast(element); 8 //否则调用linkBefore 9 else10 linkBefore(element, node(index));11 }

1 Node<E> node(int index) { 2 // assert isElementIndex(index); 3 4 if (index < (size >> 1)) { 5 Node<E> x = first; 6 for (int i = 0; i < index; i++) 7 x = x.next; 8 return x; 9 } else {10 Node<E> x = last;11 for (int i = size - 1; i > index; i--)12 x = x.prev;13 return x;14 }15 }

1 void linkBefore(E e, Node<E> succ) { 2 // assert succ != null; 3 final Node<E> pred = succ.prev; 4 final Node<E> newNode = new Node<>(pred, e, succ); 5 succ.prev = newNode; 6 if (pred == null) 7 first = newNode; 8 else 9 pred.next = newNode;10 size++;11 modCount++;12 }

### (四)get方法

1 public E get(int index) {2 //检查是否超过链表长度或者负数3 checkElementIndex(index);4 //node节点我前面分析过了，O(n)复杂度5 return node(index).item;6 }