集合深度学习02—List

List接口

重复的方法看父级
扩展的方法都和索引相关

一、List接口中常用方法：

• 增加：add(int index, E element)
• 删除：remove(int index) remove(Object o) //显然第一个是特有的，第二个是继承的
• 修改：set(int index, E element)
• 查看：get(int index) //这里就有新的了，可以获取指定位置的元素
• 判断：

add(int index, E element) 在指定下标位置添加元素

ArrayList还是数组复制，在那个位置断开 原前+新元素+原后

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
1
2
3
4
5
6
7
8

LinkedList底层是链表

    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    /**
     * Links e as last element.
     */
    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++;
    }
    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //获取指定位置的原结点的前置节点
        final Node<E> pred = succ.prev;
        //创建新结点，前置结点的后继结点为当前新结点。
        //当前新结点的后继结点为原本位置结点
        final Node<E> newNode = new Node<>(pred, e, succ);
        //原本位的前置结点为新本位结点
        succ.prev = newNode;
        //如果原结点没有前置结点，即为头结点
        if (pred == null)
        // 则头结点为新节点
            first = newNode;
        else
        //否则原前置结点的下一个结点为新节点
            pred.next = newNode;
        //总数++
        size++;
        modCount++;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

删除：remove(int index) remove(Object o)
如果我调用 remove(2)，删除的是数字2，还是下标为2的元素？

读以下代码可知，传 int 类型，删的是这个位置的，其他类型，删第一个同值元素。

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

get(0); //获取元素的方法

ArrayList实现

    transient Object[] elementData; 
    
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
   
   E elementData(int index) {
        return (E) elementData[index];
    }
1
2
3
4
5
6
7
8
9
10

LinkedList实现

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
   private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
   private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
    
  Node<E> node(int index) {
  		// 细节，这里还优化了，如果索引为在列表前半段，顺序找，
  		//                            在后半段，则逆序找
  		//   难怪用 双向链表 ， 快
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

二、遍历方法

方式1：普通for循环

        for(int i = 0;i<list.size();i++){
            System.out.println(list.get(i));
        }
1
2
3

方式2：增强for循环

        for(Object obj:list){
            System.out.println(obj);
        }
1
2
3

方式3：迭代器

        Iterator it = list.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
1
2
3
4