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

浅浅的花香味﹌ 2022-05-27 08:37 185阅读 0赞

上一篇[Java从入门到放弃（八）集合框架之LinkedList源码(1)][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的坑][Java_ArrayList]。

### **6、LinkedList和ArrayList的不同** ###

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

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

[Java_LinkedList_1]: https://blog.csdn.net/qq_34101608/article/details/79941473
[Java_ArrayList]: https://blog.csdn.net/qq_34101608/article/details/79836185