Java基础：LinkedList

「爱情、让人受尽委屈。」 2022-12-07 11:49 176阅读 0赞

## 1.性质及底层实现 ##

##### LinkedList是一种双向链表 #####

![在这里插入图片描述][20200915144123924.png_pic_center]

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

LinkedList 基本的性质：

*  LinkedList是否允许空：是
 *  LinkedList是否允许重复数据：是
 *  LinkedList是否有序：是
 *  LinkedList是否线程安全：否

##### LinkedList 源码： #####

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    { 
    	//集合元素的个数
        transient int size = 0;
    
        /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
        //头结点引用
        transient Node<E> first;
    
        /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
        //尾结点引用
        transient Node<E> last;
    
        /** * 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);
        }

## 2.get(int index)方法解析 ##

public E get(int index) { 
    		//检查下标是否合法
            checkElementIndex(index);
            //返回指定下标的结点的值
            return node(index).item;
        }
    
    
    //根据指定位置获取结点
     Node<E> node(int index) { 
            // assert isElementIndex(index);
    		//如果下标在链表前半部分, 就从头开始查起
    		//size >> 1 = size/2
            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;
            }
        }

简单来说，比较传入的索引参数index与集合长度size/2，如果是index小，那么从第一个顺序循环，直到找到为止；如果index大，那么从最后一个倒序循环，直到找到为止。  
因此通过下标的查找和修改操作的时间复杂度是O(n/2)  
越靠近中间的元素，集合的数据量越大，get(int index)执行性能也会指数级降低

## 3.add(E e) 和 add(int index, E element) ##

public boolean add(E e) { 
    		//在链表尾部添加
            linkLast(e);
            return true;
        }
    
    
    //设置元素e为最后一个元素
     void linkLast(E e) { 
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

简单来说，

*  若集合为空，那么添加进来的node就是first，也是last，这个node的prev和next都为null
 *  若集合不为空，那么添加进来的node就是last，node的prev指向以前的最后一个元素，node的next为null。同时以前的最后一个元素的next指向插入的node

public void add(int index, E element) { 
     		//判定index位置的合法性,index >= 0 && index <= size才可以
            checkPositionIndex(index);
    		//如果插入的index等于size,则表示index是最后一个
            if (index == size)
            	//在链表尾部添加
                linkLast(element);
            else
            	//在链表中部插入
            	//传入的参数为当前的值element和index处的节点node(index)
                linkBefore(element, node(index));
        }
    
    
      //链接到指定结点之前
      void linkBefore(E e, Node<E> succ) { 
            // assert succ != null;
            //获取给定结点的上一个结点引用
            final Node<E> pred = succ.prev;
            //创建新结点, 新结点的上一个结点引用指向给定结点的上一个结点
            //新结点的下一个结点的引用指向给定的结点
            final Node<E> newNode = new Node<>(pred, e, succ);
            //将给定结点的上一个结点引用指向新结点
            succ.prev = newNode;
            //如果给定结点的上一个结点为空, 表明给定结点为头结点
            if (pred == null)
            	//将头结点引用指向新结点
                first = newNode;
            else
            	//否则, 将给定结点的上一个结点的下一个结点引用指向新结点
                pred.next = newNode;
                
            //集合元素个数加一 
            size++;
            //修改次数加一
            modCount++;
        }

简单来说，代码实现和add(E e)差别不大，都是通过新建一个Node实体，同时指定其prev和next来实现。不同点在于需要调用node(int index)通过传入的index来定位到要插入的位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]

## 4.remove(Object o) 和 remove(int index) ##

public boolean remove(Object o) { 
            if (o == null) { 
                //遍历整个链表删除
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (x.item == null) { 	
                        //找到了就删除
                        unlink(x);
                        return true;
                    }
                }
            } else { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (o.equals(x.item)) { 
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    
    
    public E remove(int index) { 
    		//检查下标是否合法,index >= 0 && index <= size才可以
            checkElementIndex(index);
            //unlink方法的参数是index处的节点
            return unlink(node(index));
        }
    
    
    //删除指定结点
    E unlink(Node<E> x) { 
            // assert x != null;
            //获取给定结点的元素
            final E element = x.item;
            //获取给定结点的下一个结点的引用
            final Node<E> next = x.next;
            //获取给定结点的上一个结点的引用
            final Node<E> prev = x.prev;
    
    		//如果给定结点的上一个结点为空, 说明给定结点为头结点
            if (prev == null) { 
            	//将头结点引用指向给定结点的下一个结点
                first = next;
            } else { 
            	//将上一个结点的后继结点引用指向给定结点的后继结点
                prev.next = next;
                //将给定结点的上一个结点置空
                x.prev = null;
            }
    
    		//如果给定结点的下一个结点为空, 说明给定结点为尾结点
            if (next == null) { 
            	//将尾结点引用指向给定结点的上一个结点
                last = prev;
            } else { 
            	//将下一个结点的前继结点引用指向给定结点的前继结点
                next.prev = prev;
                x.next = null;
            }
    
    		//将给定结点的元素置空
            x.item = null;
            //集合元素个数减一
            size--;
            //修改次数加一
            modCount++;
            return element;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 1]

## 5.set(int index, E element) ##

public E set(int index, E element) { 
    		//检查下标是否合法
            checkElementIndex(index);
            //获取指定下标的结点引用
            Node<E> x = node(index);
            //获取指定下标结点的值
            E oldVal = x.item;
            //将结点元素设置为新的值
            x.item = element;
            //返回之前的值
            return oldVal;
        }

## 6.LinkedList遍历 ##

*  普通for循环
 *  增强for循环
 *  Iterator迭代器

Iterator迭代器和增强for循坏的效率相差不大，都远超过普通for循坏

## 7.总结 ##

① LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加  
② 删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法  
③ 插入和删除操作的时间复杂度都是O(1)，查找和修改操作都需要遍历链表进行元素的定位，这两个操作都是调用的node(int index)方法定位元素。通过下标定位时先判断是在链表的上半部分还是下半部分，如果是在上半部分就从头开始找起，如果是下半部分就从尾开始找起，因此通过下标的查找和修改操作的时间复杂度是O(n/2)

#### 和ArrayList的对比： ####

1.  顺序插入速度ArrayList会比较快。  
    ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了  
    LinkedList每次顺序插入的时候需要new一个对象出来
2.  使用各自遍历效率最高的方式的情况下，ArrayList的遍历效率会LinkedList的遍历效率高一些
3.  LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址  
    ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

[20200915144123924.png_pic_center]: /images/20221123/7fbe8741b7714ae3a851f1a7aaea611f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/35bbd04394c24c10b0ef95989d11d1da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/e00be57c861b4c30b91b3cb3e3240363.png