一、属性

在LinkedList中,共有三个成员变量,size,first和last

transient int size = 0; //LinkedList的大小 transient Node<E> first; //链表中第一个节点 transient Node<E> last; //链表中最后一个节点

Node类是ListedList的一个内部类,其结构如下:

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

item表示当前节点的值,next引用指向下一个节点,prev引用指向前一个节点,这就是双向链表的特征

二、构造方法

//构造一个无参 public LinkedList() { 
} 
 
public LinkedList(Collection<? extends E> c) { this(); 
    addAll(c); 
}

容器第一篇总结篇说过,所有实现Collection接口的容器类,都一定有两个构造方法,一个无参,一个有参(参数为所有实现Collection的对象)

LinkedList(Collection< ? extends E> c) :构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列

首先调用this()生成一个空的LinkedList对象,然后调用addAll,把参数的Collection添加到LinkedList中,addAll(Collection< ? extends E> c)代码如下:

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

addAll方法有两个(一参和二参):
addAll(Collection< ? extends E> c) : 把Collection添加到LinkedList的尾端
addAll(int index, Collection< ? extends E> c):把Collection添加到LinkedList的index位置

在构造方法中调用一参的addAll,从而调用二参的addAll,此时index为成员变量size,即把Collection添加到LinkedList的尾端

    public boolean addAll(int index, Collection<? extends E> c) { //检查index位置是否超出边界 
        checkPositionIndex(index); 
 //把Collection转为数组    
        Object[] a = c.toArray(); int numNew = a.length; //如果Collection为空,返回false,表示添加失败 if (numNew == 0) return false; 
 //pred指向前一个节点,succ指向下一个节点 
        Node<E> pred, succ; //如果在链尾添加,下一个节点为空,pred指向当前链表最后一个节点 if (index == size) { 
            succ = null; 
            pred = last; 
        } else { /** 
            如果不在链尾添加,调用node(index),内部通过遍历离链表取得index位置的节点,并把succ指向index位置的节点,pred指向index位置节点的前一个节点 
            **/ 
            succ = node(index); 
            pred = succ.prev; 
        } 
 //执行插入,注意pred for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; 
            Node<E> newNode = new Node<>(pred, e, null); //如果把o插入到链头 if (pred == null) 
                first = newNode; else //让index位置的前一个节点的next指向包含o的新节点 
                pred.next = newNode; //把newNode节点作为pred 
            pred = newNode; 
        } 
 //更新pred和succ if (succ == null) { 
            last = pred; 
        } else { 
            pred.next = succ; 
            succ.prev = pred; 
        } 
 //增加LinkedList的大小 
        size += numNew; //LinkedList用modCount变量来记录链表改变的次数 
        modCount++; return true; 
    }

node(index)方法非常重要,LinkedList很多方法都是通过node(index)才取得index位置的节点,从而进一步操作:
例如set(int index, E e),就是要通过node(index)取得index位置的node,从而设置node.item = e;

    //遍历链表从而取得index位置节点 
    Node<E> node(int index) { //如果index 小于 size/2 则从头开始查找 if (index < (size >> 1)) { 
            Node<E> x = first; for (int i = 0; i < index; i++) 
                x = x.next; return x; 
        } else { //如果index 大于 size/2 则从尾部开始查找 
            Node<E> x = last; for (int i = size - 1; i > index; i--) 
                x = x.prev; return x; 
        } 
    }

这里是数据结构链表的内容,有数据结构基础的人完全可以看懂

三、增加方法的核心

add(E e) :将指定元素添加到此列表的结尾
add(int index, E element):在此列表中指定的位置插入指定的元素
当index == size时,两个方法等效,都是添加到链表的尾部

接下来看看add(int index, E element)的源码:

    public void add(int index, E element) { 
        checkPositionIndex(index); 
 //当在链尾添加时,调用linkLast(element),add(E e) 方法内部也是调用linkLast(element) if (index == size) 
            linkLast(element); else //如果不是在链尾添加,则把element添加到index位置节点前 
            linkBefore(element, node(index)); 
    }

    //succ是index位置的节点 void linkBefore(E e, Node<E> succ) { // assert succ != null; //pred指向要添加的位置的前一个节点 final Node<E> pred = succ.prev; //创建一个新节点 final Node<E> newNode = new Node<>(pred, e, succ); //把新节点插入到index位置前 
        succ.prev = newNode; 
 //如果是在链表头部添加 if (pred == null) 
            first = newNode; else //把新节点插入到index位置前一个节点的后面,这样就把新节点插入到了index位置 
            pred.next = newNode; //容量加1 
        size++; //修改次数加1 
        modCount++; 
    }

除了linkBefore,linkFirst和linkLast也是其它增加方法的核心
例如addFirst内部是调用linkFirst,push()也是调用linkFirst,addLast()内部调用的是linkLast

这三个方法都比较简单,就不再叙述

四、删除方法的核心

remove(Object o):从此列表中移除首次出现的指定元素(如果存在)

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

这段代码很简单,就是遍历链表,把删除掉第一次出现参数值得节点,如果找不到,返回false

remove调用了unlink(x)方法:

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

这里的删除逻辑跟数据结构中的链表的操作一样,非常简单

五、总结

总得来看,LinkedList的实现是很简单的,只要数据结构过关,完全可以自己实现一个

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

数组(二):ArrayList的实现和Arrays类的使用详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。