Share the source code of several common methods in ArrayList

jdk1.7.0_79

## The above explains the relevant# The source code of several common methods in ##ArrayList

- "Source code analysis of common methods in ArrayList", this article will briefly describe the common methods in LinkedList Parse . LinkedList

is implemented based on a linked list

, which means that it has the advantages and disadvantages of a linked list, with slow random access and fast insertion and deletion speeds. Since it is a linked list, it has a node data structure, and there is no problem of capacity. Just add one at the end.

//LinkedList$Nodeprivate 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;
    }
}

The first constructor that takes no parameters by default constructs an empty linked list.

//1.LinkedList，默认构造方法public LinkedList() {
}

The second constructor can pass a collection as a parameter, and the elements in the collection need to be a subclass of

LinkedList

.

//2.LinkedList，能将一个集合作为参数的构造方法public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

The two construction methods are relatively simple. Next, let’s look at the insertion and deletion of elements.

public boolean add(E e) {
    linkLast(e);    //将元素添加到链表尾部return true;
}

//LinkedList#linkLastvoid linkLast(E e) {final Node<E> l = last;    //链表尾指针引用暂存final Node<E> newNode = new Node<>(l, e, null);    //构造新节点last = newNode;    //将链表的尾指针指向新节点if (l == null)    //此时为第一次插入元素first = newNode;elsel.next = newNode;    
    size++;    //链表数据总数+1modCount++;    //modCount变量在《有关ArrayList常用方法的源码解析》提到过，增删都会+1，防止一个线程在用迭代器遍历的时候，另一个线程在对其进行修改。}

Students who have studied "Data Structure" believe that the operation of linked lists will not be unfamiliar. Let's take a look at deleting elements at specified positions

remove(int)

method.

//LinkedList#removepublic E remove(int index) {
    checkElementIndex(index);    //检查是否越界 index >= 0 && index <= sizereturn unlink(node(index));    //调用node方法查找并返回指定索引位置的Node节点}

//LinkedList#node，根据索引位置返回Node节点Node<E> node(int index) {if (index < (size >> 1)) {    //size >> 1 = size / 2，如果索引位于链表前半部分，则移动fisrt头指针进行查找Node<E> x = first;for (int i = 0; i < index; i++)
            x = x.next;return x;
    } else {    //如果索引位于链表后半部分，则移动last尾指针进行查找Node<E> x = last;for (int i = size - 1; i > index; i--)
            x = x.prev;return x;
    }
}

Find the

index

position After ##Node, call the unlink method to remove the node.

//LinkedList#unlink，一看即懂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;
}

You can see the advantages and disadvantages of

LinkedList

and ArrayList from the code, since only a simple linked list data structure is involved, other methods will not be parsed.

The above is the detailed content of Share the source code of several common methods in ArrayList. For more information, please follow other related articles on the PHP Chinese website!