链表03--第五天
从来不虚场合 人气:01.双向链表
1.1双向链表--remove(int index)
@Override public E remove(int index) { rangeCheck(index); Node<E> node = node(index); Node<E> prev = node.prev; Node<E> next = node.next; if (prev == null) { // index == 0 first = next; } else { prev.next = next; } if (next == null) { // index == size - 1 last = prev; } else { next.prev = prev; } size--; return node.element; }
1.2双向链表VS单向链表
1.3双向链表VS动态数组
1.4LinkedList源码分析
2.单向循环链表
2.1单向循环链表--只有一个节点
2.2单向循环链表--add(int index,E element)
@Override public void add(int index, E element) { rangeCheckForAdd(index); if (index == 0) { Node<E> newFirst = new Node<>(element, first); // 拿到最后一个节点 Node<E> last = (size == 0) ? newFirst : node(size - 1); last.next = newFirst; first = newFirst; } else { Node<E> prev = node(index - 1); prev.next = new Node<>(element, prev.next); } size++; }
2.3单向循环链表--remove(int index)
@Override public E remove(int index) { rangeCheck(index); Node<E> node = first; if (index == 0) { if (size == 1) { first = null; } else { Node<E> last = node(size - 1); first = first.next; last.next = first; } } else { Node<E> prev = node(index - 1); node = prev.next; prev.next = node.next; } size--; return node.element; }
3.双向循环链表
3.1双向循环链表--只有一个节点
3.2双向循环链表--add(int index,E element)
@Override public void add(int index, E element) { rangeCheckForAdd(index); // size == 0 // index == 0 if (index == size) { // 往最后面添加元素 Node<E> oldLast = last; last = new Node<>(oldLast, element, first); if (oldLast == null) { // 这是链表添加的第一个元素 first = last; first.next = first; first.prev = first; } else { oldLast.next = last; first.prev = last; } } else { Node<E> next = node(index); Node<E> prev = next.prev; Node<E> node = new Node<>(prev, element, next); next.prev = node; prev.next = node; if (next == first) { // index == 0 first = node; } } size++; }
3.3双向循环链表--remove(int index)
@Override public E remove(int index) { rangeCheck(index); return remove(node(index)); } private E remove(Node<E> node) { if (size == 1) { first = null; last = null; } else { Node<E> prev = node.prev; Node<E> next = node.next; prev.next = next; next.prev = prev; if (node == first) { // index == 0 first = next; } if (node == last) { // index == size - 1 last = prev; } } size--; return node.element; }
4.静态链表
5.ArrayList能否进一步优化
加载全部内容