4 LinkedList
发布时间:2020-12-15 05:25:37 所属栏目:Java 来源:网络整理
导读:1 LinkedList public class LinkedListE extends AbstractSequentialListE?implements ListE,DequeE,Cloneable,java.io.Serializable 实现原理,通过双向链表实现的。适合插入、删除操作。 ? 2 节点 LinkedList使用双向链表实现,而双向链表通过节点来实现,
1 LinkedListpublic class LinkedList<E> extends AbstractSequentialList<E>?implements List<E>,Deque<E>,Cloneable,java.io.Serializable 实现原理,通过双向链表实现的。适合插入、删除操作。 ? 2 节点LinkedList使用双向链表实现,而双向链表通过节点来实现,我们来看看节点的定义。 ? private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev,E element,Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } ? ? ? 3 元素操作LinkedList默认大小为0,没有扩容机制,每增加一个元素,容量加1。 (1) add? ? public boolean add(E e) { linkLast(e); return true; } ? void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l,e,null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ? (2) remove public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; } ? ? (3) get ? public E get(int index) { checkElementIndex(index); return node(index).item; } ? Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } ? 4、其他方法getFirst() ? getLast() addFirst() ? addLast() removeFirst() ? removeLast() (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |