LinkedList源码研究

小咪咪 2023-10-08 13:04 8阅读 0赞

#### 文章目录 ####

*  LinkedList
 *   *   *  无参构造
         *  有参构造
         *  push()方法
         *  add()方法
         *  get()方法
         *  set()方法

接着上一篇，研究完ArrarList之后，理所应当看看LinkedList  
什么是LinkedList呢，  
它是通过 `双向链表`实现的列表，具有双向链表的优缺点  
**相比较ArrarList，增删效率要高，随机访问效率要低**

## LinkedList ##

首先看一下里面定义的参数

transient int size = 0;//节点数量
    transient Node<E> first;//头节点
    transient Node<E> last;//尾节点

经典的双向链表数据结构  
它包含一个非常重要的私有内部静态类:Node，用来操作节点并设置节点的前后节点

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

然后看一下它的构造方法，也就是我们创建它的源码

/**
         * Constructs an empty list.
         */
        public LinkedList() {
        
        }
    
        /**
         * Constructs a list containing the elements of the specified
         * collection, in the order they are returned by the collection's
         * iterator.
         *
         * @param  c the collection whose elements are to be placed into this list
         * @throws NullPointerException if the specified collection is null
         */
        public LinkedList(Collection<? extends E> c) {
        
            this();
            addAll(c);
        }

#### 无参构造 ####

public LinkedList() {
        
        }

没啥说的，空构造而已

#### 有参构造 ####

public LinkedList(Collection<? extends E> c) {
        
            this();
            addAll(c);
        }

继续往里点

public boolean addAll(Collection<? extends E> c) {
        
            return addAll(size, c);
        }

让我们点进addAll()方法，写的十分优美

public boolean addAll(int index, Collection<? extends E> c) {
        
            //检查长度是否越界
            checkPositionIndex(index);
            Object[] a = c.toArray();//形态转换，方便后期操作
            int numNew = a.length;//获取参数个数
            if (numNew == 0)//如果数量为0
                return false;//返回false
            Node<E> pred, succ;//注意，此时前后节点的设计，对后期批量插入十分关键，是美的前提
            if (index == size) {
        
                succ = null;//当在链表最后插入时，last变为前节点，后继节点为空
                pred = last;
            } else {
        
                succ = node(index);//在当前节点的前面插入整个数组
                pred = succ.prev;
            }
    		//每个节点有三个特征，pred, element, succ.注意三个元素的变化
            for (Object o : a) {
        
                @SuppressWarnings("unchecked") E e = (E) o;
                Node<E> newNode = new Node<>(pred, e, null);//新建节点，并指向pred
                if (pred == null)
                    first = newNode;
                else
                //对pred节点，让其指向newNode.至此，newNode与前节点的双边指向关系建立.此时后节点还没出现
                pred.next = newNode;
                //令newNodeo为即将插入节点的前节点，在一个循环中，newNode将建立与后节点的双边指向关系
                pred = newNode;
            }
    		//如此循环结束后，只剩最后一个节点的双边指向关系没有建立
            if (succ == null) {
        
                last = pred;
            } else {
        //建立最后一个节点的指向
                pred.next = succ;
                succ.prev = pred;
            }
    
            size += numNew;//节点数增加
            modCount++;//链表修改次数增加
            return true;
        }

这个方法做了什么呢，首先检查长度是否越界，然后将参数转化为数组，通过**尾插法**添加进链表  
至此，一个双向链表被创建了出来

然后再让我们研究下LinkedList的添加与删除  
先看添加吧，因为LinkedList本质是双向链表，是可以当做队列或栈使用的。  
其添加不光有add()方法，也有push()方法

#### push()方法 ####

看到这个方法名想起来什么？  
没错，就是**栈**  
LinkedList是有push()和pop()方法的，所以它能当栈来使用

public void push(E e) {
        
        addFirst(e);
    }

可以看到，push()方法，其实就是通过头插法，将数据插到链表头部的位置，点进去

public void addFirst(E e) {
        
            linkFirst(e);
        }

再点进去

private void linkFirst(E e) {
        
            final Node<E> f = first;//创建节点f，将头节点赋给它
            final Node<E> newNode = new Node<>(null, e, f);//创建新节点newNode，放在f的前面
            first = newNode;//将头节点设为新节点newNode
            if (f == null)//如果f为空，即插入前链表为空链表
                last = newNode;//将尾节点设为新节点newNode
            else
                f.prev = newNode;//将f的上一个节点设为新节点newNode
            size++;//节点数量+1
            modCount++;//操作次数+1
        }

至此，插入成功。  
显而易见，push()方法是**头插法**插入元素（将新节点放在原来头节点的前面）

#### add()方法 ####

public boolean add(E e) {
        
            linkLast(e);
            return true;
        }

看名字就能看到，这个肯定是尾插法插入元素，让我们点进去

void linkLast(E e) {
        
            final Node<E> l = last;//创建节点l=尾节点
            final Node<E> newNode = new Node<>(l, e, null);//创建新节点，并将节点放在尾节点的后面
            last = newNode;//设置尾节点为新节点
            if (l == null)//如果l为空，即原链表为空链表
                first = newNode;//设置头节点为新节点
            else
                l.next = newNode;//将l节点指向新节点
            size++;//节点数量+1
            modCount++;//操作次数+1
        }

至此，插入数据成功，果然是**尾插法**。  
那么，push和add有什么不同呢？  
add 是加在list尾部，是将LinkedList当作链表来使用。  
push 施加在list头部， 等同于addFirst，是将LinkedList当作栈来使用。  
验证：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][18a017f47573404e9bd84ee0dd35d292.png]

顺便一提，LinkedList的取出操作只有`pop`和`get`。并且如果一个LinkedList中既有`add`的添加，又有`push`的添加，那么`pop`操作会先取栈元素，再取队列元素。

好了，再让我们看一下get()与set()方法

#### get()方法 ####

本质上还是遍历链表中的数据，通过下标取数据

public E get(int index) {
        
        checkElementIndex(index);//检查是否越界
        return node(index).item;
    }

让我们点进去node方法，看看里面

Node<E> node(int index) {
        
            // assert isElementIndex(index);
    		//下标和长度的一半比较，用以确定从头还是尾遍历
            if (index < (size >> 1)) {
        //size >> 1 移位运算，意味size的一半
                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;
            }
        }

就是做了一个从头还是从尾遍历的判断，然后取值，嗐

#### set()方法 ####

public E set(int index, E element) {
        
            checkElementIndex(index);//检查下标是否越界
            Node<E> x = node(index);//根据下标取值
            E oldVal = x.item;//旧数据
            x.item = element;//更新数据
            return oldVal;//返回旧数据
        }

没啥难得，看注释就好  
有兴趣的同学可以看看remove方法的源码，remove有三个哦

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/169cba1f2ecd404f887d24072be2f2c9.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70
[18a017f47573404e9bd84ee0dd35d292.png]: https://img-blog.csdnimg.cn/18a017f47573404e9bd84ee0dd35d292.png