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

时间:2021-09-08 19:24:17

    上一篇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.