• 周一. 6月 24th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

跟踪LinkedList源码,通过分析双向链表实现原理,自定义一个双向链表

admin

11月 28, 2021

1.LinkedList实现的基本原理

LinkedList是一个双向链表,它主要有两个表示头尾节点的成员变量first  、last,因其有头尾两个节点,所以从头或从尾操作数据都非常容易快捷。LinkedList通过内部类Node来保存元素 ,一个Node对象表示链表的一个节点,有多少个元素就需要多少个Node节点。如果要添加元素,则新建一个Node节点,保存这个元素,同时指定其前驱节点和后继节点的引用。若要删除一个元素,则将取消此元素对应的Node节点在链表中的前驱后继关系。

2.ListedList实现的关键 -——静态内部类Node

Node类有3个成员变量:

 1)表示当前节点保存的元素item ,

 2)表示后继节点的引用next

 3)表示前驱节点的引用 prev

    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个成员能够很清楚的表示自己的逻辑结构。首先它能确定自己的位置,属性prev 、next分别指定了前驱、后继节点分别是谁,指明了当前节点在链表结构中的位置;另外成员变量item明确了当前节点要保存的元素。

3.ListedList的成员变量

其成员变量主要是表示链表头 尾节点的两个成员变量:头节点first 、  尾节点last。

因为有头尾两个节点,可以很方便地从头部或从尾部这两个方向进行逻辑操作。

只用一个头节点可实现单向链表,它的效率不高,因为只能从单向从头到尾遍历,不能根据实际情况选择更优的遍历方向。

    // 链表的所含元素个数
    transient int size = 0;

    // 链表的头节点
    transient Node<E> first;
    // 链表的尾节点
    transient Node<E> last;
    /*
     * 此属性在本类中没有,此属性是从父类AbstractSequentialList中继承而来
     * 链表结构被修改的次数,防止在迭代遍历过程中,修改链表结构
     */
    protected    int modCount = 0;

4 .其构造方法

构造方法有两个,一个默认构造方法,将初始化一个空链表;另一个带单参数的构造方法,将初始化后,此链表将包含集合参数c的所有元素

    public LinkedList() { } //头尾节点都是null的空链表

    //初始化后,包含集合c所有元素的链表
    public LinkedList(Collection<? extends E> c) { 
        this();
        addAll(c);//添加集合c所有元素
    }

5.其常用的API

1). public boolean add(E e)   在尾部添加一个元素

此方法去调用了一个对链表尾部连接新元素的方法linkLast(E)

    public boolean add(E e) {
        linkLast(e);//在尾部链接一个新元素
        return true;
    }

 此时去看看linkLast(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++;//添加一个元素,链表结构被修改一次,modCount自加一
    }

2)public void add(int index, E element)  在指定下标处添加元素

    此方法有两个分支,若插入的下标位置等于链表元素个数,则可直接在链表尾部添加要插入的元素;而其它一般情况则调用linkBefore(E,Node)方法,在指定某节点之前插入指定元素。

而linkBefore(E,Node)的方法参数又调用了Node<E>  node(int)方法。

    public void add(int index, E element) {
        checkPositionIndex(index); //检查下标是否合法

        if (index == size)  //插入的位置index=size即可直接在链表尾部添加元素
            linkLast(element);
        else
            //在指定的节点之前插入元素
            linkBefore(element, node(index));
    }

先来看看node(int)方法是如何根据下标查找到下标对应的Node节点

  ——- node(int)方法中有两个分支,根据index是否小于size的一半作为进入不同分支的条件。此分支条件是用来确定待查找的节点与头/尾节点的距离远近,若待查找的节点和头节点较近,就从头节点开始查找;若待查找的节点与尾节点较近,则从尾节点开始遍历查找。这主要是从遍历效率角度考虑的。

    Node<E> node(int index) {
        //index作为循环遍历停止的条件
        if (index < (size >> 1)) { // 如果index小于size的一半,则从头部开始向后查找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next; //将当前节点的后继节点赋值给当前节点
            return x;
        } else {     // 如果index大于size的一半,则从尾部开始向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) 
                x = x.prev;//将当前节点的前驱节点赋值给当前节点
            return x;
        }
    }

最后来看linkBefore(E,Node)如何在指定的节点前添加指定的元素

  ——-其中也对插入位置的进行了判断,如果是在头部插入节点,则需要将头节点的引用更新为待插入节点。

    void linkBefore(E e, Node<E> succ) {
         //插入点节点succ的前驱节点pred
        final Node<E> pred = succ.prev;
        /*
         * 待插入的节点,
         * 此节点将取代插入点节点succ,插入点succ将后移一位
         * 此节点的前驱是插入点节点的前驱节点pred,其后继节点就是插入点节点succ
         */
        final Node<E> newNode = new Node<>(pred, e, succ);
        //插入点节点的前驱是待插入节点
        succ.prev = newNode;
        
        if (pred == null)
            /*
             * 插入点节点的前驱节点pred为为空,表明此时在头部直接插入节点
             * 那么链表更新后,当前的待插入节点就是头节点
             */
            first = newNode;
        else
            /*
             * 插入点节点的前驱节点pred的后继节点是待插入节点
             */
            pred.next = newNode;
        size++;
        modCount++;
    }

3) public E remove(int index)   移除指定位置的元素

 先利用node(int)方法,根据下标查找到对应的Node节点,再调用unlink(Node)方法,取消指定节点在链表中的链接关系。

    public E remove(int index) {
        checkElementIndex(index);//检查下标是否合法
        /*
         * 利用node(int)方法,根据下标查找到对应的Node节点
         * 再调用unlink(Node)方法,取消指定节点在链表中的链接关系
         */
        return unlink(node(index)); 
    }

 node(int)方法已经在之前已经分析过了,这里主要来看unlink(Node)方法的实现 

   ——unlink(Node)方法比较复杂,但是将思路理清楚,也就不难理解了。

           (1)因为待移除节点x将被删除,x的前驱prev和x的后继next都将不再依赖x这个中间连接者,所以要将前驱节点prev与后继节点next直接链接起来。LinkedList是双向链表,每个节点都要双向(前后)维护链接关系,即同时维护前驱与后继。那么prev、next两者都要更新链接关系,链表更新后prev的后继节点是next,即prev.next=next, 而next的前前驱节点又是prev,即next.prev=prev 。

           (2)另外还要考虑待移除节点x是头节点或尾节点这种特殊情况(first=next或last=prev)。

           (3)因为待移除节点x不会再被使用了,最后还要将待移除节点x的各个属性赋为null,便于GC回收内存资源(x.item=null ;x.prev=null;x.next=null)。

    E unlink(Node<E> x) {
        //保存待移除节点储存的元素,最后要返回这个被移除的元素
        final E element = x.item;
        //待移除节点的后继节点
        final Node<E> next = x.next;
        //待移除节点的前驱节点
        final Node<E> prev = x.prev;

        /**
         * 维护待移除节点的前节点驱prev的链接关系
         */
        if (prev == null) {
            /*
             * 待移除节点的前驱prev为空,表明待移除节点是头节点
             * 当待移除节点是头节点时,移除元素更新后,待移除节点的后继节点next就是链表更新后的头节点
             * 此时待移除节点的前驱节点本来就为空,不用再去赋为空值
             */
            first = next;
        } else {
            /* 在其他一般情况下(非头节点),更新后
             * 待移除节点的前驱节点prev的后继节点 就是待移除节点的后继节点next
             * 将待移除节点x的属性prev赋为空,便于最后的垃圾回收
             */
            prev.next = next;
            x.prev = null;
        }

        
        /*
         * 维护待移除节点的后继节点的链接关系
         */
        if (next == null) {
            /*
             * 待移除节点的后继next为空,表明待移除节点是尾节点
             * 当待移除节点是尾节点,移除元素更新后,待移除节点的前驱节点prev就是链表更新后的尾节点
             * 此时待移除节点的后继节点本来就为空,不用再去赋为空值
             */
            last = prev;
        } else {
            /* 在其他一般情况下(非尾节点),移除更新后
             * 待移除节点的后继节点next的前驱节点 就是的待移除节点的前驱节点prev
             * 将待移除节点x的属性next赋为空,便于最后的垃圾回收
             */
            next.prev = prev;
            x.next = null;
        }

        x.item = null; //将待移除节点储存的元素引用赋空
        size--;
        modCount++;//链表结构被修改,modCount自加
        return element;//返回被移除元素
    }

4) public E remove(Object o)  根据元素的引用移除元素

根据元素是否为空进入不同的分支。从头元素开始向后遍历,若链表中的一个元素与o相等,则调用unlink(Node)方法移除当前节点,退出循环并返回true;若遍历了所有元素,没有任何一个元素与o相等,则返回false,移除指定元素失败。

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

5)public E set(int index, E element)  替换指定下标对应的元素

   (1)找到下标index对应的节点

   (2)保存index下标位置的原元素值

   (3) 将节点的item属性更新为element

    public E set(int index, E element) {
        checkElementIndex(index);//检查下标
        Node<E> x = node(index); //查找下标index对应的节点
        E oldVal = x.item; //保存原值
        x.item = element;//将下标index对应节点所保存的元素值更新
        return oldVal;
    }

6)public  E get(int index)  获取指定下标对应的元素   

       找到下标index对应的节点,返回此节点的item属性。

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

  

7)  public int indexOf(Object o)  根据元素值确定其第一次出现的位置下标

从头节点开始向后遍历,若找到这个元素则退出循环并返回当前遍历的下标,若不存在此元素返回-1.

    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)  public int lastIndexOf(Object o)  根据元素值确定其最后一次出现的位置下标

      与“public int indexOf(Object o)”的实现原理基本一致,只有遍历的方向不同而已,此方法是从尾节点向前遍历

    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

9)public void clear()  清空所有元素

    public void clear() {
      /*
       * 将所有结点的所有属性赋空
       */
        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;//不含任何元素,size设为0
        modCount++;
    }

 10)  public boolean addAll(int index, Collection<? extends E> c)  在指定下标处插入所有集合元素

    此方法也对一些特殊情况做了判断分支处理,如在链表的尾部添加元素,或是在链表的头部添加元素等。

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);//检查下标
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0) //集合c没有任何元素,不用添加任何一个元素,直接返回false。
            return false;
        //pred表示插入点原节点的前驱节点, succ表示插入点的原节点,
        Node<E> pred, succ; 
        if (index == size) {
            /*
             * index=size表明在链表的尾部批量添加元素
             * 前驱pred为尾节点
             * 插入点的原节点succ不存在,则为null
             */
            succ = null;
            pred = last;
        } else {
            /*
             * 非尾部添加元素
             */
            succ = node(index);
            pred = succ.prev;
        }
         /*
          * 将集合中的所有元素加入到链表中
          */
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //当前要添加的节点(初始化了新节点的链接关系)
            Node<E> newNode = new Node<>(pred, e, null);
            //更新前驱元素的链接关系
            if (pred == null)
                //在头部添加节点时
                first = newNode;
            else
                //非头部添加节点
                pred.next = newNode;
            //当前新添加节点作为下次遍历时新添加节点的前驱
            pred = newNode;
        }
        
        /**
         * 维护添加最后一个元素时的链接关系
         */
        if (succ == null) {
             /*
              * 在尾部添加时,最后添加的那个元素即为尾节点
              */
            last = pred;
        } else {
            /*
             * 非尾部添加时
             */
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

 6.总结源码经验,仿写双向链表

 一个集合的基本功能是增删改查,总结一下这些功能的大致思路:

1)”增“元素: 可以在链表的尾部增加元素或在链表的中部插入元素。在尾部添加元素需要维护原尾部节点新添加节点的相互链接关系;而在中部插入新元素需要维护新插入节点插入点原节点插入入节点前驱节点 这三个节点间的相互链接关系。可以统一起来看,”增”元素都是插入元素,需要维护新插入节点、新插入节点的/节点间的相互链接关系(在尾部添加元素时,其后继节点为空而已)。

2)“删”元素:维护待删节点的前后节点的相互链接关系,即将前后节点直接链接起来,另外还要将待删节点的各属性赋空(利于垃圾回收)。同时得考虑特殊情况下——在头部或尾部删除节点,此时还要更新头节点或尾节点的引用。

3)“改”元素:先根据索引或元素值找到对应的Node节点,再重设该节点的item属性。

4)“查”元素:根据索引,循环遍历找到对应的Node节点,获取该节点的item属性。

和LinkedList相似的双向链表:

package collection;

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

public class LinkList<E> implements Iterable<E>, List<E> {
    // 链表的所含元素个数
    private int size = 0;
    // 链表的头节点
    private Node<E> head = null;
    // 链表的尾节点
    private Node<E> tail = null;
    /*
     * 链表结构被修改的次数,防止在迭代遍历过程中,修改链表结构
     */
    int modCount = 0;

    /**
     * 添加一个元素
     * 
     * @param e
     * @return
     */
    public boolean add(E e) {
        return linkTail(e);
    }

    /**
     * 在链表尾部新链接一个元素
     * 
     * @param e
     * @return
     */
    private boolean linkTail(E e) {
        final Node<E> oldTail = tail;

        final Node<E> newNode = new Node<>(oldTail, e, null);
        tail = newNode;
        if (oldTail == null)
            head = newNode;
        else {
            oldTail.next = newNode;
        }

        modCount++;
        size++;
        return true;
    }

    /**
     * 移除指定下标处的元素
     * 
     * @param index
     * @return
     */
    public E remove(int index) {
        checkElementIndex(index);
        Node<E> nodeRemove = fastNodeAt(index);// 快速查找到指定下标对应的节点
        return unlink(nodeRemove); // 取消这个节点在链表结构中链接
    }

    /**
     * 根据下标快速查找节点
     */
    private Node<E> fastNodeAt(int index) {
        if (index < size >> 1) {// 如果index小于size的一半,则从头部开始查找
            Node<E> current = head;

            for (int i = 0; i < index; i++)
                current = current.next;
            return current;

        } else {// 如果index大于size的一半,则从尾部开始查找
            Node<E> current = tail;
            for (int i = size - 1; i > index; i--)
                current = current.prev;
            return current;

        }
    }

    /**
     * 取消指定节点在链表结构中的链接
     */
    private E unlink(Node<E> node) {

        Node<E> prev = node.prev;
        Node<E> next = node.next;
        E oldData = node.data;

        /*
         * 维护被移除节点的前驱节点的链接关系
         */
        if (prev == null) {
            /**
             * 当被移除节点是头节点时,更新后的头节点就是被移除节点的下一节点
             *  此时被移除节点的前节点本来就为空,不用再去赋为空值
             */
            head = next;
        } else {
            prev.next = next;// 更新后,被移除节点的前节点对应的 后节点是 被移除节点的后节点
            // 被移除节点的前节点赋空,若不赋空则一直存在对前置节点的引用,可能出现内存泄漏
            node.prev = null;
        }
        /*
         * 维护被移除节点的后继节点的链接关系
         */
        if (next == null) {
            /**
             * 当被移除节点是尾节点时,更新后的尾节点就是被移除节点的前驱节点 
             * 此时被移除节点的后继节点本来就为空,不用再去赋为空值
             */
            tail = prev;
        } else {
            // 更新后,被移除节点的后继接节点对应的前驱结点 就被移除节点的前驱结点
            next.prev = prev;
            node.next = null;
        }
        node.data = null;
        // node=null;
        size--;
        modCount++;
        return oldData;
    }

    /**
     * 更新指定下标处的元素,
     * 
     * @param index
     * @param e
     * @return 原元素值
     */
    public E set(int index, E e) {
        checkElementIndex(index);// 快速查找到指定下标对应的节点
        Node<E> node = fastNodeAt(index);
        E oldData = node.data; // 保存老值
        node.data = e;
        return oldData;
    }

    /**
     * 获取指定下标的元素
     * 
     * @param index
     * @return
     */
    public E get(int index) {
        checkElementIndex(index);
        return fastNodeAt(index).data;
    }

    /**
     * 指定元素第一次出现的下标位置
     * 
     * @param obj
     * @return
     */
    public int indexOf(Object obj) {
        if (size == 0)// 不含任何元素,返回-1
            return -1;
        int index = 0;
        E curElement;
        for (Node<E> next = head; next != null; next = next.next) {// 从头节点开始遍历
            curElement = next.data;
            if (curElement == obj || (curElement != null && curElement.equals(obj)))
                // 找到了对应的元素,返回当前下标
                return index;
            index++;
        }
        return -1;// 没找到对应的元素
    }

    public Node<E> nodeOf(Object obj) {
        if (size == 0)
            return null;
        E curElement;
        for (Node<E> next = head; next != null; next = next.next) {// 从头节点开始遍历
            curElement = next.data;
            if (curElement == obj || (curElement != null && curElement.equals(obj))) {
                return next;

            }
        }
        return null;
    }

    /**
     * 返回指定元素最后一次出现的下标位置
     * 
     * @param obj
     * @return
     */
    public int lastIndexOf(Object obj) {
        if (size == 0)// 不含任何元素,返回-1
            return -1;
        E curElement;
        int index = 0;
        for (Node<E> prev = tail; prev != null; prev = prev.prev) {// 从尾节点开始遍历
            curElement = prev.data;
            if (curElement == obj || (curElement != null && curElement.equals(obj)))
                return index;
            index++;
        }
        return -1;
    }

    public boolean remove(Object obj) {
        if (size == 0)// 不含任何元素,false
            return false;
        E curElement;
        for (Node<E> next = head; next != null; next = next.next) {// 从头节点开始遍历
            curElement = next.data;
            if (curElement == obj || (curElement != null && curElement.equals(obj))) {
                unlink(next);
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(int index, E e) {

        checkElementPosition(index);
        if (index == size) {
            linkTail(e);
        } else {
            linkBefore(index, e);
        }
    }

    private boolean linkBefore(int index, E e) {
        Node<E> node = fastNodeAt(index);
        Node<E> prev = node.prev;
        Node<E> newNode = new Node<>(prev, e, node);
    
        if (prev == null) {
            head = newNode;

        } else {
            prev.next = newNode;

        }
        node.prev = newNode;
        size++;
        modCount++;
        return true;
    }

//    private Node<E> nodeAt(int index) {
//        Node<E> targetNode = null;
//        if (index < (size >> 1)) {// 如果index小于size的一半,则从头部开始查找这个元素
//            Node<E> next = null;
//            int i = 0;
//            for (Node<E> current = head; current != null;) {
//                if (i == index) {
//                    targetNode = current;
//                    break;
//                }
//                next = current.next;
//                current = next;
//                i++;
//            }
//        } else {
//            Node<E> prev = null;
//            int i = size - 1;
//            for (Node<E> current = tail; current != null;) {
//                if (i == index) {
//                    targetNode = current;
//                    break;
//                }
//                prev = current.prev;
//                current = prev;
//                i--;
//            }
//        }
//        return targetNode;
//    }



    /*
     * 检查元素下标对应的元素是否存在
     * 
     */
    private void checkElementIndex(int index) {
        if (index >= size || index < 0)
            throw new IndexOutOfBoundsException(indexOutRangeMsg(index));

    }

    /*
     * 检查在插入元素时,插入位置是否正确
     * 
     */
    private void checkElementPosition(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(indexOutRangeMsg(index));

    }

    private String indexOutRangeMsg(int index) {
        return " index [" + index + "] ,  size [" + size + "]";
    }

    // 表示节点的静态内部类
    private static class Node<E> {
        // 前一个节点
        private Node<E> prev;
        // 下一个节点
        private Node<E> next;
        // 当前节点存储的数据
        private E data;
    
        public Node(Node<E> prev, E data, Node<E> next) {
            super();
            this.prev = prev;
            this.next = next;
            this.data = data;
        }

    }

    @Override
    public Iterator<E> iterator() {

        return new SimpleIterator();
    }

    private class SimpleIterator implements Iterator<E> {
        private int desireModCount = modCount;// 预期的的修改次数
        private Node<E> nextNode = head;// 下次遍历的节点
        private Node<E> lastRetNode = null;// 最终使用的节点
        private int nextIndex = 0;// 下标

        @Override
        public boolean hasNext() {

            return nextIndex < size;
        }

        @Override
        public E next() {
            checkModCount();
            if (!hasNext())
                throw new NoSuchElementException();
            lastRetNode = nextNode;
            E data = lastRetNode.data;
            nextNode = nextNode.next;
            nextIndex++;
            return data;
        }

        @Override
        public void remove() {
            checkModCount();
            if (lastRetNode == null)
                throw new IllegalStateException("");
            Node<E> lastNode = lastRetNode.next;
            LinkList.this.unlink(lastRetNode);

            if (lastNode == lastRetNode)
                nextNode = lastNode;
            else
                nextIndex--;

            lastRetNode = null;
            desireModCount = modCount;

        }

        /*
         * 校验在迭代过程中,是否使用了非迭代的方式改变了链表结构
         */
        private void checkModCount() {
            if (desireModCount != modCount)
                throw new IllegalStateException("迭代过程中的结构被改变了");
        }
    }

    @Override
    public boolean contains(Object o) {

        return indexOf(o) != -1;
    }

    @Override
    public Object[] toArray() {
        if (size == 0)
            return new Object[] {};
        Object[] objs = new Object[size];
        int i = 0;
        for (Node<E> next = head; next != null; next = next.next) {
            objs[i] = next.data;
            i++;
        }
        return objs;
    }

    @SuppressWarnings("unchecked")
    @Override
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = head; x != null; x = x.next)
            result[i++] = x.data;

        
        return a;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        if (c == null)
            throw new NullPointerException();

        for (Object o : c) {
            if (indexOf(o) == -1)
                return false;
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        if (c == null)
            throw new NullPointerException();

        return addAll(size, c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        checkElementPosition(index);
        if (c.size() == 0)
            return false;
        Node<E> prev, insertPoint;
        if (index == size) {
            prev = tail;
            insertPoint = null;
        } else {
            insertPoint = fastNodeAt(index);
            prev = insertPoint.prev;
        }

        Object[] elementsAdd = c.toArray();

        for (Object o : elementsAdd) {
            @SuppressWarnings("unchecked")
            E e = (E) o;
            Node<E> newNode = new Node<E>(prev, e, null);
            if (prev == null)
                head = newNode;
            else
                prev.next = newNode;
            prev = newNode;
        }

        if (insertPoint == null)
            tail = prev;
        else {
            prev.next = insertPoint;
            insertPoint.prev = prev;
        }

        size += elementsAdd.length;
        modCount++;
        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        if (c == null)
            throw new NullPointerException();
        boolean removeFlag = false;
        Iterator<E> itor = this.iterator();
        while (itor.hasNext()) {
            if (c.contains(itor.next())) {
                itor.remove();
                removeFlag = true;

            }

        }
        return removeFlag;
    }

    @Override
    public boolean retainAll(Collection<?> c) {

        if (c == null)
            throw new NullPointerException();
        boolean retainFlag = false;
        Iterator<E> itor = this.iterator();
        while (itor.hasNext()) {
            if (!c.contains(itor.next())) {
                itor.remove();
                retainFlag = true;
            }
        }
        return retainFlag;
    }

    @Override
    public void clear() {
        if (size == 0)
            return;
        for (Node<E> curNode = head; curNode != null;) {
            Node<E> nextNode = curNode.next;
            curNode.prev = null;
            curNode.data = null;
            curNode.next = null;
            curNode = nextNode;
        }
        size = 0;
        head = null;
        tail = null;
        modCount++;
    }

    @Override
    public ListIterator<E> listIterator() {
        throw new UnsupportedOperationException();

    }

    @Override
    public ListIterator<E> listIterator(int index) {

        throw new UnsupportedOperationException();
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {

        throw new UnsupportedOperationException();
    }

}

View Code

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注