Java集合系列之近乎万能的LinkedList

1,917

Java集合系列之近乎万能的LinkedList

Hello,大家好,元旦已经过去了,小伙伴们该安心回来工作赚钱了,OK,废话少说,上几篇文章给大家讲了HashMap,ArrayList的底层实现,这一篇给大家讲一讲LinkedList,这个集合底层维护也不难,但却实现了很多层语义,像队列(FIFO),栈(FILO),List语义(根据索引搞事),其实学习本篇博文,不只是学会LinkedList,而是告诉大家几个接口层面的语义,大家以后选集合使用时就知道怎么回事了。OK,老规矩,文章结构:

  1. 队列Queue、双端队列Deque.
  2. LinkedList底层维护。
  3. LinkedList核心API讲解。

1. 队列Queue、双端队列Deque.

上一篇讲Collection和Map宏观把控时已经讲到了Queue这个接口要定义的语义,其实就是一个FIFO,两个核心的API为Offer和poll,一个是在队列尾加元素,一个是从队列头取元素。今天给大家说一个双端队列Deque,这个接口实现于Queue,它主要实现了什么语义呢,其实就是一个双端队列,不管是新增还是删除都可以从尾巴向头操作,也可以从头向尾巴操作,不像Queue一样,只能在尾巴上添加,头上取.它在Quene的基础上,新增了XXFirst,XXLast方法,像getFirst,getLast,peekFirst,peekLast,pollFirst,pollLast等等。。说白了,就是可以直接操作头尾,不像单向Queue一样头只能取,尾巴只能添加。其次,需要重点强调的是,Deque还维护了Stack的语义(FILO),对应的API为push,pop..OK,来给大家列一下核心的API:

上面說了Deque要实现的语义,其实了解数据结构的都知道,这种结构其实还是很好实现了,数组和链表都是可以实现这种语义的,对应JDK实现好的集合那就是ArrayDeque和LinkedList,很多人可能有点蒙蔽,为什么不叫LinkedDeque,呵呵,其实是因为这个LinkedList也实现了List接口,所以才叫LinkedList的啦,说实话有点不楞不累的,还不如叫LinkedDequeList...

2. LinkedList底层维护

好了,正式给大家介绍了LinkedList:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

是不是有点神奇,即实现了List,又实现了Deque,这就是文章题目叫做近乎万能的LinkedList,他即实现了List的有序语义(根据index访问),又实现了Deque的队列语义,还有Stack的语义..哈哈..OK,直接说下结构吧:

    transient Node<E> first; //链表的头指针
    transient Node<E> last; //尾指针
    //存储对象的结构 Node, 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;
        }
    }

其实还是很清晰的,就是一个双向链表,每个Node节点存储了上个节点和下个节点.这种结构的特点就是根据索引访问很慢,而增删改会比较快,至于为什么,我就不啰嗦了,这是数据结构的知识了。其实大家想一想,这种双向链表来实现双向队列和使用数组来实现双向队列是一种鱼和熊掌不可兼得的事情,链表注定了索引访问慢,而数组注定了增删元素慢。

3. LinkedList核心API讲解。

好了,来通过几个核心的API来看下LinkedList这个双向链表是如何实现这么多语义的:

3.1 实现List语义

前面给大家讲ArrayList时,大家可能比较清楚,它在实现List语义时,因为底层使用数组维护的,所以直接调用数组的 array[index]就行了,那么LinkedList由于底层是用链表维护了,我们来看一下API:

    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            //链表尾部添加element
            linkLast(element);
        else
            在某个元素前面添加element
            linkBefore(element, node(index));
    }
    
    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;
        }
    }

可以看到,无论是调用新增,还是查询,要实现根据索引搞事,一个最核心的方法是node(index),这个方法意思就是返回索引为index的Node节点.方法内部,大致可以看到,是根据for循环的次数为index来取到Node.所以大家知道为什么链表维护的数据结构要根据索引查找很慢了吗?因为一直要遍历。。不像数组,直接array[index]...根据索引拿到Node后,其他的就是链表的基本操作了,新增和删除的时候其实都只会影响某个Node的前后节点,挪一挪指针就OK了。

3.1 实现Deque语义

先说下LinkedList中几个核心的API:

这几个API啥作用了,其实就是操作内部这个双向链表的头尾和在中间插一个元素用的。它外层实现的Deque的接口和Quene的接口内部都是使用这几个API来实现的外层语义.举个例子: Quene的API:

    public boolean offer(E e) {
        return add(e);
    }
        public boolean add(E e) {
        //链表尾部新增一个元素
        linkLast(e);
        return true;
    }

再看一个Deque的API:

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
        public void addFirst(E e) {
        linkFirst(e);
    }

看,是不是很简单。至于内部这几个linkFirst,unlinkFirst之类的API,大家不用看源码都应该知道干了什么事。无非就是把Node节点中的指针挪一挪,实现了新增删除节点的目的。

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

很Easy...如果头结点为Null,它就是头结点和尾结点,如果头结点不为NUll,它的下一节点为头结点(new Node<>(null, e, f);来实现的),之前的头结点的上一节点为它(f.prev = newNode;)熟悉链表这种结构的小伙伴应该比较清楚指针怎么挪动,我就不耀武扬威了。^_^..

结语

好了,其实把LinkedList内部结构说一说,大家自己翻一下源码都很清楚了,这个集合不是很难,但是很典型的一个集合。实现了很多层次的语义,又可以当List用,又可能当Deque用,又可以当Stack用。。但大家要知道要点,如果你要使用的数据经常有增删操作,这个LinkedList比较合适。如果是经常的有根据index查询的场景,这个是显然不合适的。上面已经讲到了。OK.LinkedList就给大家说明白了。Over,Have a good day !