Java从入门到放弃（九）集合框架之LinkedList源码(2)

上一篇Java从入门到放弃（八）集合框架之LinkedList源码(1)介绍了add和remove方法，这篇介绍LinkedList的set,get等方法。

1、get方法

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

方法很简单，就是一个越界检查，然后调用node(index)方法获取对应的节点，然后返回节点的item。node(index)方法和链表结构上一篇已经讲过了，这里不再讲解。

2、set方法

public E set(int index, E element) {
        checkElementIndex(index);    //越界检查
        Node<E> x = node(index);     //获取对应节点
        E oldVal = x.item;           
        x.item = element;            //节点item指向新的元素
        return oldVal;
    }

这里还是使用了node(index)方法，把对应节点的item数据更改为新的元素，返回旧的元素。

3、pop(),push(),offer(),peek(),poll()方法

pop: 删除第一个节点并返回

public E pop() {
        return removeFirst();
    }

看一下removeFirst方法

   public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;    
        final Node<E> next = f.next;   //获取first的next节点，即第二个节点
        f.item = null;
        f.next = null; // help GC
        first = next;                  //将first指向第二个节点
        if (next == null)              
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

就是把头节点删除，first指向第二个节点。

push：在链表头加入一个元素，不返回

public void push(E e) {
        addFirst(e);
    }
	public void addFirst(E e) {
        linkFirst(e);
    }
	private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);   //新的节点，next指向first的节点
        first = newNode;                                  //first指向新的节点
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;                              //f的perv节点指向新节点
        size++;
        modCount++;
    }

在开头加入一个节点，就是把first节点指向新的节点，然后把之前的first节点f的perv引用指向新节点。

offer:链表尾部增加元素，返回添加结果

public boolean offer(E e) {
        return add(e);  
    }

就是调用了add(e)方法,具体实现看上一篇博文。
peek:返回头部元素

public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

返回first节点的item元素。没有九返回null;
poll：删除第一个节点并返回

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

和pop作用一样，区别就是pop如果没有第一个元素会抛出异常。

LinkedList除了这几个还有removeLast()，pollLast()等方法，所以可以很容易的用LinkedList实现一个队列或者栈的结构。

4、clear,size,isEmpty

public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        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++;
    }

size方法和isEmpty就不贴代码了，size()就是返回size属性，isEmpty就是判断size是否等于0，

clear方法和ArrayList方法类似，就是把所有元素和引用都置为null，便于GC。

5、迭代器

和ArrayList不一样的是，iterator方法返回的是listIterator；这个方法是从AbstractSequentialList继承而来。

public Iterator<E> iterator() {
        return listIterator();
    }

关于listIterator和Iterator的区别具体看 Java从入门到放弃（七）集合框架之ArrayList的坑。

6、LinkedList和ArrayList的不同

LinkedList是基于双向链表实现的，各个节点直接的通过next和perv来连接，与数组不同，ArrayList的数组结构使得ArrayList可以通过索引快速访问元素，包括查询和修改，时间复杂度O(1),但是不便于添加和删除，因为每次添加或者删除要移动目标节点后的所有元素。而LinkedList基于链表结构，可以很快的进行添加和删除，只是把对应的next和perv更改就实现了添加删除，但是在查询和更改的时候，会比较慢，因为需要从first(或者last)遍历链表。

在查询和更改比较多的情况下使用ArrayList，在增加、删除比较多的情况下使用LinkedList.

秒客网