java集合-LinkedList

LinkedList简介

LinkedList数据结构是双端链表，所以它支持高效的插入和删除操作，继承于AbstractSequentialList,实现了Serializable,List,Deque,Cloneable等接口

LinkedList继承AbstrctSequentialList，实现了List接口，他是一个链表队列，提供了相关的添加，删除，插入，遍历等操作

LinkedList实现了Deque接口，拥有部分队列的性质，例如可以在两端插入和删除元素

LinkedList实现了Cloneable接口，表示覆盖了clone（）方法，能被克隆。

LinkedList实现了Serializable接口,表示该类能够被序列化来传输。

LinkedList类中的静态内部类Node便是用来充当链表中的节点功能

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;
      }
  }

LinkedList源码分析

构造方法

 //无参构造方法
 public LinkedList() {}

/**
 * 根据指定集合创建链表
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

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++;
}

在指定位置插入的add方法

public void add(int index, E element) {
    checkPositionIndex(index);//检查下标范围
    if (index == size)//判断下标值
        linkLast(element);//插入尾部（上面讲过了）
    else
        linkBefore(element, node(index));//插入指定位置
}

Node<E> node(int index) {
       // assert isElementIndex(index);
		//判断下标是否小于链表大小/2
       //这里对半查询
       //size>>1==size/2
       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;
       }
   }


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++;
}

addAll方法

1
2
3

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//尾部批量插入
}

指定位置的addAll方法

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;
  }

remove方法

//删除指定元素
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;
    }

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的后继节点
            x.prev = null;
        }
			//判断后继节点是否为空
        if (next == null) {
            last = prev;//把尾指针指向前驱节点
        } else {
            next.prev = prev;//后继节点的前驱节点指向x的前驱节点
            x.next = null;
        }

        x.item = null;
        size--;长度减一
        modCount++;
        return element;返回x数据
    }

1	#### get方法

//上面都讲过了。。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}




### ArrayList和LinkedList的区别，使用场景

#### 区别
> 1.ArrayList和LinkedList的区别就来自于他们的底层数据结构，ArrayList是基于数组实现的，因此它随机遍历会很快，LinkedList是基于双端链表，因此它插入删除会很快。

> 2.相对于ArrayList，LinkedList的随机访问集合元素时性能较差，因为需要在双向列表中找到要index的位置，再返回；但在插入，删除操作是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

> 3.存储同样数据的LinkedList相对于ArrayList会占用更多内存，因为LinkedList还要存储前驱节点和后驱节点的位置。

#### 使用场景

> 1.在需要大量的随机访问，使用ArrayList优于LinkedList

> 2.在需要大量的插入和删除操作时，使用LinkedList优于ArrayList