浅谈LinkedList

LinkedList结构图

image.png

LinkedList主要方法

• public E get(int index)
• public E set(int index, E element)
• public void add(int index, E element)
• public E remove(int index)

LinkedList解读主要方法

来看一下public E get(int index)源码：

//第一步
public boolean add(E e) {
        linkLast(e);
        return true;
    }
//第二步
void linkLast(E e) {
        //保存last节点
        final Node<E> l = last;
        //创建一个新的节点，它的前一个节点为l，后一个节点为null
        final Node<E> newNode = new Node<>(l, e, null);
        //把新的节点标记为last节点
        last = newNode;
        //如果之前的last节点为空，那么新的节点既是头结点也是尾节点
        if (l == null)
            first = newNode;
        else
          //把新的节点加入到原尾节点的后面
            l.next = newNode;
        //修改size大小
        size++;
        //修改count值
        modCount++;
    }

看一下public E set(int index, E element)的源码

public E set(int index, E element) {
        //校验index位置
        checkElementIndex(index);
        //找到index
        Node<E> x = node(index);
        //获取原节点值，修改为新值，返回原节点的值
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
  //校验index，index需在0到size之间
 private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//找到index节点
Node<E> node(int index) {
        // assert isElementIndex(index);
        //小技巧，判断index是在中间位置的左边还是右边，然后选择正序遍历还是逆序遍历找到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 void add(int index, E element) 源码

 public void add(int index, E element) {
      //这个还是和set一样的判断，index位置是否合理
        checkPositionIndex(index);
      //在末尾添加
        if (index == size)
            linkLast(element);
        else
            //非末尾添加
            linkBefore(element, node(index));
    }
//在末尾添加，这个前面我已经讲过了
 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++;
    }
//在index节点前插入element元素
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //保存index位置之前的节点为pred
        final Node<E> pred = succ.prev;
        //创建一个节点，它的前一个节点为pred它的后一个节点为index对应的节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        //index节点的前一个节点为element对于的新节点了
        succ.prev = newNode;
      //index的前一个节点pred如果是空的证明就没有首节点，将前一个节点设置为首节点
        if (pred == null)
            first = newNode;
        else
//前一个节点不为空的话，把它的下一个节点设置为新节点
            pred.next = newNode;
//修改size和modCount值
        size++;
        modCount++;
    }

来看一下public E remove(int index)源码

  public E remove(int index) {
       //这个还是和set一样的判断，index位置是否合理
        checkElementIndex(index);
        //删除index对应的节点
        return unlink(node(index));
    }
//删除index节点
E unlink(Node<E> x) {
        // assert x != null;
        //获取index元素，找到index的前一个节点prev和后一节点next
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //如果待删除节点的前一个节点为空的话，将next节点设置为first节点，也就说明就两个节点，删除的就是首节点
        if (prev == null) {
            first = next;
        } else {
        //将前一个节点的next指向待删除节点的下一个节点(next)
            prev.next = next;
          //将待删除节点的前一个节点设置为空
            x.prev = null;
        }
        //如果待删除节点的后一个节点为空，将pred节点设置为last节点，也就说明只有两个节点，删除节点就是尾节点
        if (next == null) {
            last = prev;
        } else {
            //将后一个节点的prev指向待删除节点的前一个节点(prev)
            next.prev = prev;
            //将待删除节点的下一个节点设置为空
            x.next = null;
        }
        //待删除节点内容设置为空，修改size和modCount，返回待删除元素
        x.item = null;
        size--;
        modCount++;
        return element;
    }

LinkedList遍历介绍

常用的三种遍历方式：

       //one  foreach  遍历
        for (Object o : list) {
            System.out.println(o);
        }
        // two 随机访问
        for (int i = 0; i <list.size(); i++) {
            System.out.println(list.get(i));
        }
        //three 迭代器的遍历
        Iterator iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

LinkedList其他特性介绍

• LinkedList底层使用链表来实现的(并且是双向链表)，所以LinkedList在新增和删除的时候效率比较高，但是在随机访问的时候效率会比较低。
• LinkedList是无界的，还有LinkedList在多线程操作的时候当modCount!=expectedModCount会抛出ConcurrentModificationException异常。