转载

LinkedList源码解析(二)

size()返回结合中存储的节点数量

public int size() {
        return size;
    }

add(E e)向集合末尾添加一个元素

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

remove(Object o)移除一个元素

public boolean remove(Object o) {
        if (o == null) {//如果o是null
            for (Node<E> x = first; x != null; x = x.next) {//从第一个节点指针指向的节点开始循环
                if (x.item == null) {//比较节点的值,的内存地址
                    unlink(x);//取消节点
                    return true;//操作成功
                }
            }
        } else {//如果o是不是null
            for (Node<E> x = first; x != null; x = x.next) {//从第一个节点指针指向的节点开始循环
                if (o.equals(x.item)) {//调用o的equals方法和节点的值作比较
                    unlink(x);//取消节点
                    return true;//操作成功
                }
            }
        }
        return false;//操作失败
    }

addAll(Collection<? extends E> c)向集合末尾加入集合c

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

clear()清空集合

public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {//从first指针指向的节点开始循环
            Node<E> next = x.next;//获取x的next
            x.item = null;//x的值置空
            x.next = null;//x的next置空
            x.prev = null;//x的prev置空
            x = next;//x赋值为next下一次循环使用
        }
        first = last = null;//第一个节点指针和最后一个节点的指针置空
        size = 0;//数据长度0
        modCount++;//操作数不清空
    }

get(int index)获取index索引节点数据

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

set(int index, E element)设置index索引处的节点位数为element

public E set(int index, E element) {
        checkElementIndex(index);//index在范围内
        Node<E> x = node(index);//获取索引处的节点
        E oldVal = x.item;//获取节点旧的值
        x.item = element;//给节点的值赋值新值
        return oldVal;//返回旧的值
    }

add(int index, E element)根据索引插入数据

public void add(int index, E element) {
        checkPositionIndex(index);//index在范围内

        if (index == size)/、如果索引位index等于数据长度
            linkLast(element);//尾插入
        else
            linkBefore(element, node(index));//否则插入在index索引对应节点之前
    }

remove(int index)移除索引index处的数据

public E remove(int index) {
        checkElementIndex(index);//index在范围内
        return unlink(node(index));
    }

isElementIndex(int index)判断参数是否是现有元素的索引

private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

isPositionIndex(int index)判断参数是否是现有元素的索引(迭代器或添加操作)

private boolean isPositionIndex(int index) {
        return index >= 0 && index < size;
    }

构造一个IndexOutOfBoundsException详细消息

private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

lastIndexOf(Object o)返回指定元素最后一次出现的索引

public int lastIndexOf(Object o) {
        int index = size;//初始下标赋值
        if (o == null) {//o为null
            for (Node<E> x = last; x != null; x = x.prev) {//last指针指向的节点开始向前循环
                index--;
                if (x.item == null)//节点的值作内存比较
                    return index;//返回下标
            }
        } else {//o不为null
            for (Node<E> x = last; x != null; x = x.prev) {//last指针指向的节点开始向前循环
                index--;
                if (o.equals(x.item))//调用o的equals方法和节点的值比较
                    return index;
            }
        }
        return -1;
    }

peek()索但不删除此列表的头部(null返回null)

public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;//如果是null的话不返回对象,返回null
    }

element()检索但不删除此列表的头部(null会抛出异常)

public E element() {
        return getFirst();
    }

getFirst()返回此列表中的第一个元素(null会抛出异常)

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

poll()检索并删除此列表的头部(null返回null)

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);//不为null时候,删除并返回第一个节点
    }

remove()检索并删除此列表的头部

public E remove() {
        return removeFirst();
    }

offer(E e)将指定的元素添加为此列表的尾部

public boolean offer(E e) {
        return add(e);
    }

offerFirst(E e)在指定列表第一个节点前面插入e

public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

offerLast(E e)在指定列表最后一个节点后面插入e

public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

peekFirst()检索但不删除此列表的第一个节点(null返回null)

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

peekFirst()检索但不删除此列表的最后一个节点(null返回null)

public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

pollFirst()检索并删除此列表的第一个节点(null返回null)

public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

pollLast()检索并删除此列表的第最后一个节点(null返回null)

public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

push(E e)将元素插入到第一个节点签名

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

pop()移除第一个节点

public E pop() {
        return removeFirst();
    }

removeFirstOccurrence(Object o)删除此中第一次出现的指定元素

public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

removeLastOccurrence(Object o)删除此中最后一次出现的指定元素

//和lastIndexOf类似,找到后直接调用unlink
 public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
原文  https://segmentfault.com/a/1190000019444106
正文到此结束
Loading...