Java集合源码—LinkedList

朴灿烈づ我的快乐病毒、 2021-11-10 14:36 483阅读 0赞

## LinkedList源码分析 ##

### 1.LinkedList概述 ###

*  LinkedList底层是一个双链表(非循环), 是一个直线型的链表结构
 *  因为实现方式是链表, 所以在插入或删除时的效率较高, 但是因为其内存空间并不一定连续, 遍历时需要从头到尾访问一遍, 所以查找的效率并不是很高

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        
    }

*  继承AbstractSequentialList 抽象类, 在遍历LinkedList的时候, 官方更推荐使用迭代器. (虽然LinkedList也提供了get(int index)方法, 但是每次调用该方法, 都需要从链表的头部或尾部进行遍历, 复杂度是O(n) ),
 *  实现了List接口, 提供List接口中所有方法的实现
 *  实现了Cloneable接口, 支持克隆(浅克隆). 通过Object.clone()方法的到的Object对象转化为了LinkedList, 并把内部的实例域都置空, 然后把背靠背的LinkedList结点中的每个值都拷贝到clone中
 *  实现了Deque接口, 可以用作双端队列
 *  实现了Serializable接口, 支持序列化.

### 2.类中的属性 ###

//链表的长度
    	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;
            }
        }

Node类作为一个私有的静态内部类, 是每个节点的数据结构

### 3.类的构造器 ###

#### 1>无参构造器 ####

public LinkedList() {
        
        }

#### 2>带参构造器 ####

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

相比于ArrayList, LinkedList的构造方法简洁了很多

### 4.常用方法 ###

#### 1>add() , linkLast(), addLast() ####

public boolean add(E e) {
        
            //默认将节点添加在链表末尾(尾插)
            linkLast(e);
            return true;
        }
    
    	//分析一下linkLast(e)方法
    
    	void linkLast(E e) {
        
            //获取当前的尾节点
            final Node<E> l = last;
            //new出一个赋值的新节点
            final Node<E> newNode = new Node<>(l, e, null);
            //新节点变成尾节点
            last = newNode;
            //当链表还是空时, 新加入的这个节点就是头节点了 
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            //长度增加
            size++;
            modCount++;
        }
    	//同样的, addLast()方法也是调用了linkLast()方法
    	public void addLast(E e) {
        
            linkLast(e);
        }

#### 2>addFirst() ,linkFirst() ####

public void addFirst(E e) {
        
            //调用头插方法
            linkFirst(e);
        }
    
    	//linkFirst()与linkLast 相对应, 使用头插法插入新元素
    	private void linkFirst(E e) {
        
            //获取第一个头结点
            final Node<E> f = first;
            //new出新节点, 并让其next指向之前的头
            final Node<E> newNode = new Node<>(null, e, f);
            //新节点成为头
            first = newNode;
            //如果之前链表为空, 那么last节点也就是新new出的这个节点
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }

#### 3> addAll() ####

public boolean addAll(Collection<? extends E> c) {
        
            return addAll(size, c);
        }
        
    	//index代表
        public boolean addAll(int index, Collection<? extends E> c) {
        
            //检查index位置是否合法
            checkPositionIndex(index);
     		
            //将传入的集合参数转为数组
            Object[] a = c.toArray();
            int numNew = a.length;
            //若集合为空, 返回失败
            if (numNew == 0)
                return false;
    
            Node<E> pred, succ;
            //判断插入位置是否是在尾部
            if (index == size) {
        
                //如果是从尾部开始插入, pred节点就是链表的尾节点, succ代表插入位置后面的节点
                succ = null;
                pred = last;
            } else {
        
                succ = node(index);
                pred = succ.prev;
            }
    
            for (Object o : a) {
        
                //将Object对象转化成泛型类型
                @SuppressWarnings("unchecked") E e = (E) o;
                //new出新的节点, prev指向前一个节点
                Node<E> newNode = new Node<>(pred, e, null);
                //当链表为空的时候, 
                if (pred == null)
                    first = newNode;
                else
                    pred.next = newNode;
                //更新pred节点, 每插入一个, 向后移动一位
                pred = newNode;
            }
    
            //如果在尾部开始插入
            if (succ == null) {
        
                last = pred;
            } else {
        
                //否则将两边连接上
                pred.next = succ;
                succ.prev = pred;
            }
    		//更新链表长度
            size += numNew;
            modCount++;
            return true;
        }

#### 4>remove(), unlink() ####

//删除链表中指定元素
    	public boolean remove(Object o) {
        
            //如果为要删除 node中值为null的节点
            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;
        }
    	
    	//删除指定node
    	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;
    
            /**
            * 其实就是把要删除节点的prev.next指向next
            * 把next.pre指向prev
            */
            
            //如果是删除第一个节点
            if (prev == null) {
        
                first = next;
            } else {
        
                prev.next = next;
                x.prev = null;
            }
    		//如果是最后一个节点
            if (next == null) {
        
                last = prev;
            } else {
        
                next.prev = prev;
                //将要删除的节点中的引用置空, 方便gc
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }

#### 5>removeLast() , unlinkLast() ####

public E removeLast() {
        
            final Node<E> l = last;
            //若为空, 则抛出异常
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
    
    	private E unlinkLast(Node<E> l) {
        
            // assert l == last && l != null;
            final E element = l.item;
            final Node<E> prev = l.prev;
            //帮助GC
            l.item = null;
            l.prev = null; // help GC
            //更新为尾节点
            last = prev;
            //若链表中就一个节点, 删除完就没有节点了,
            if (prev == null)
                first = null;
            else
                prev.next = null;
            size--;
            modCount++;
            return element;
        }

#### 6>removeFirst() , unlinkFirst() ####

//移除链表中的第一个元素
    	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;
            //方便虚拟机进行GC
            f.item = null;
            f.next = null; // help GC
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }

#### 7>indexOf() ####

public int indexOf(Object o) {
        
            int index = 0;
            //寻找第一个出现的指定元素的位置
            if (o == null) {
        
                for (Node<E> x = first; x != null; x = x.next) {
        
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
        
                for (Node<E> x = first; x != null; x = x.next) {
        
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }

#### 8>clear() ####

//清空操作
    	public void clear() {
        
        //将所有节点中的引用置空, 方便虚拟机进行GC
        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++;
    }

以上基本都是LinkedList中较为核心的方法, 其他的方法大多都是利用以上的方法实现的, 这里就不拿出来细看了.