- public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
- transient int size = 0;
- // 第一个元素的引用
- transient Node<E> first;
- // 最后一个元素的引用
- transient Node<E> last;
- // 无参构造函数
- public LinkedList() {
- }
- // 包含一个 Collection 的构造函数
- public LinkedList(Collection<? extends E> c) {
- this();
- addAll(c);
- }
- // 在链表头部创建链接
- private void linkFirst(E e) {
- final Node<E> f = first;
- final Node<E> newNode = new Node<>(null, e, f);
- first = newNode;
- if (f == null)
- last = newNode;
- else
- f.prev = newNode;
- size++;
- modCount++;
- }
- // 在链表尾部创建链接
- 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++;
- }
- /**
- * Inserts element e before non-null Node succ.
- */
- void linkBefore(E e, Node<E> succ) {
- // assert succ != null;
- final Node<E> pred = succ.prev;
- final Node<E> newNode = new Node<>(pred, e, succ);
- succ.prev = newNode;
- if (pred == null)
- first = newNode;
- else
- pred.next = newNode;
- size++;
- modCount++;
- }
- // 删除链表中第一个链接
- private E unlinkFirst(Node<E> f) {
- // assert f == first && f != null;
- final E element = f.item;
- final Node<E> next = f.next;
- f.item = null;
- f.next = null; // help GC
- first = next;
- if (next == null)
- last = null;
- else
- next.prev = null;
- size--;
- modCount++;
- return element;
- }
- // 删除链表中最后一个链接
- private E unlinkLast(Node<E> l) {
- // assert l == last && l != null;
- final E element = l.item;
- final Node<E> prev = l.prev;
- l.item = null;
- l.prev = null; // help GC
- last = prev;
- if (prev == null)
- first = null;
- else
- prev.next = null;
- size--;
- modCount++;
- return element;
- }
- // 删除链表给定的元素链接
- 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;
- }
- // 获取头部元素
- public E getFirst() {
- final Node<E> f = first;
- if (f == null)
- throw new NoSuchElementException();
- return f.item;
- }
- // 获取尾部元素
- public E getLast() {
- final Node<E> l = last;
- if (l == null)
- throw new NoSuchElementException();
- return l.item;
- }
- // 移除头部元素
- public E removeFirst() {
- final Node<E> f = first;
- if (f == null)
- throw new NoSuchElementException();
- return unlinkFirst(f);
- }
- // 移除尾部元素
- public E removeLast() {
- final Node<E> l = last;
- if (l == null)
- throw new NoSuchElementException();
- return unlinkLast(l);
- }
- // 添加一个元素在链表头部
- public void addFirst(E e) {
- linkFirst(e);
- }
- // 添加一个元素到链表尾部
- public void addLast(E e) {
- linkLast(e);
- }
- // 判断是否包含某个元素
- public boolean contains(Object o) {
- return indexOf(o) != -1;
- }
- // 获取链表大小
- public int size() {
- return size;
- }
- // 添加元素
- public boolean add(E e) {
- // 把该元素放到链表最后面
- linkLast(e);
- return true;
- }
- // 移除链表中一个给定的元素对象
- public boolean remove(Object o) {
- if (o == null) {
- for (Node<E> x = first; x != null; x = x.next) {
- 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;
- }
- // 添加一个包含 Collection 的元素
- public boolean addAll(Collection<? extends E> c) {
- return addAll(size, c);
- }
- // 在给定的索引下面添加一个包含 Collection 的元素
- public boolean addAll(int index, Collection<? extends E> c) {
- checkPositionIndex(index);
- Object[] a = c.toArray();
- int numNew = a.length;
- if (numNew == 0)
- return false;
- Node<E> pred, succ;
- if (index == size) {
- succ = null;
- pred = last;
- } else {
- succ = node(index);
- pred = succ.prev;
- }
- for (Object o : a) {
- @SuppressWarnings("unchecked")
- E e = (E) o;
- Node<E> newNode = new Node<>(pred, e, null);
- if (pred == null)
- first = newNode;
- else
- pred.next = newNode;
- pred = newNode;
- }
- if (succ == null) {
- last = pred;
- } else {
- pred.next = succ;
- succ.prev = pred;
- }
- size += numNew;
- modCount++;
- return true;
- }
- // 清除链表
- public void clear() {
- for (Node<E> x = first; x != null;) {
- Node<E> next = x.next;
- x.item = null;
- x.next = null;
- x.prev = null;
- x = next;
- }
- first = last = null;
- size = 0;
- modCount++;
- }
- // Positional Access Operations
- // 根据索引获取元素
- public E get(int index) {
- checkElementIndex(index);
- return node(index).item;
- }
- // 根据索引设置索引所指向的对象的值
- public E set(int index, E element) {
- checkElementIndex(index);
- Node<E> x = node(index);
- E oldVal = x.item;
- x.item = element;
- return oldVal;
- }
- // 根据索引添加元素
- public void add(int index, E element) {
- checkPositionIndex(index);
- if (index == size)
- linkLast(element);
- else
- linkBefore(element, node(index));
- }
- // 根据索引移除元素
- public E remove(int index) {
- checkElementIndex(index);
- return unlink(node(index));
- }
- // 判断所给索引是否合法
- private boolean isElementIndex(int index) {
- return index>= 0 && index <size;
- }
- // 判断所给索引是否为第一个 / 最后一个
- private boolean isPositionIndex(int index) {
- return index>= 0 && index <= size;
- }
- private void checkElementIndex(int index) {
- if (!isElementIndex(index))
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
- private void checkPositionIndex(int index) {
- if (!isPositionIndex(index))
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
- Node<E> node(int 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;
- }
- }
- public E poll() {
- final Node<E> f = first;
- return (f == null) ? null : unlinkFirst(f);
- }
- //Queue 里面 offer() 方法
- public boolean offer(E e) {
- return add(e);
- }
- //Deque 里面 offerFirst() 方法
- public boolean offerFirst(E e) {
- addFirst(e);
- return true;
- }
- //Deque 里面 offerLast() 方法
- public boolean offerLast(E e) {
- addLast(e);
- return true;
- }
- public ListIterator<E> listIterator(int index) {
- checkPositionIndex(index);
- return new ListItr(index);
- }
- 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;
- }
- }
- }
来源: https://www.cnblogs.com/hongten/p/hongten_arraylist_linkedlist_vector.html