数组线性表

发表于 | 分类于 | 阅读次数:
字数统计: 1.8k | 阅读时长 ≈ 9

ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时，需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动时，代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

List

常用的List方法：

  • add 在最后或特定位置加入新的元素
  • clear 清除所有元素
  • contains 是否含有指定元素
  • get 获取特定索引元素
  • indexOf 返回特定元素第一次出现的索引，没有则返回-1
  • lastIndexOf 返回特定元素最后一次出现的索引，没有则返回-1
  • isEmpty 判断是否为空
  • iterator 返回迭代器
  • remove 移除特定元素
  • size 返回List大小
  • subList 根据传入的两个索引返回子列表

常用的List实现类有:

  1. ArrayList： 擅长随机访问的列表
  2. LinkedList： 擅长插入和删除操作的列表
  3. Vector： 与ArrayList类似，线程安全的列表

MyArrayList和MyLinkedList

可以使用ArrayList和LinkedList来存储线性表。使用数组实现ArrayList，使用链表实现LinkedList，前者开销比后者小。但是如果需要在线性表的开始位置插入和删除元素，那么LinkedList的效率会高一点。下表总结了ArrayList和LinkedList中方法的时间复杂度。

方法 ArrayList LinkedList
add(e: E) O(1) O(1)
add(index: int, e: E) O(n) O(n)
clear() O(1) O(1)
contains(e: E) O(n) O(n)
get(index: int) O(1)** O(n)
indexOf(e: E) O(n) O(n)
isEmpty() O(1) O(1)
lastIndexOf(e: E) O(n) O(n)
remove(e: E) O(n) O(n)
size() O(1) O(1)
remove(index: int) O(n) O(n)
set(index: int, e: E) O(n) O(n)
addFirst(e: E) O(n) O(1)**
removeFirst() O(n) O(1)**

ArrayList部分细节

使用数组来实现动态数据结构，处理方法是：当数组不能再存储线性表的新元素时，创建一个更大的新数组来替换当前数组。

add(int index, E e)

添加元素到指定位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void add(int index, E e) {
    ensureCapacity();
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = e;
    size++;     
}
private void ensureCapacity() {
    if (size >= data.length) {
        E[] newData = (E[]) new Object[2 * size + 1];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }
}

clear()

通过创建一个新数组并且将其复制给data，老的数组和保存在数组中的数据变成垃圾，将自动被JVM回收。

clear方法
1
2
3
4
public void clear() {
    data = (E[]) new Object[INITIAL_CAPACITY];
    size = 0;
}

remove(int index)

最后一个元素不再使用，设置为null。

remove方法
1
2
3
4
5
6
7
8
9
public E remove(int index) {
    checkIndex(index);
    E e = data[index];
    for (int j = index; j < size - 1; j++)
        data[j] = data[j + 1];
    data[size - 1] = null;
    size--;     
    return e;
}

ArrayList具体实现

采用集合的实现模式，在MyList接口中提供通用的操作，抽象类部分实现了包括集合操作的addAll、removeAll和containsAll等方法，最后在MyArrayList类中实现了数组线性表。
为了便于手机查看，采用倒序的显示方式。将接口、抽象类和测试用例放在最后。

MyArrayList实现类
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package algorithms.arrayList;

import java.util.Iterator;

public class MyArrayList<E> extends MyAbstractList<E> {
    private static final int  INITIAL_CAPACITY = 16;
    @SuppressWarnings("unchecked")
    private E[] data = (E[]) new Object[INITIAL_CAPACITY];  
    
    public MyArrayList() {      
        
    };      
    public MyArrayList(E[] objects) {
        for (int i = 0; i < objects.length; i++)
            add(objects[i]);
    }   

    @Override
    public void add(int index, E e) {
        ensureCapacity();
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;     
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public void clear() {
        data = (E[]) new Object[INITIAL_CAPACITY];
        size = 0;
    }

    @Override
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i]))
                return true;
        }
        return false;       
    }

    @Override
    public E get(int index) {
        checkIndex(index);
        return data[index];
    }   
    
    @Override
    public int indexOf(E e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i]))
                return i;
        }
        return -1;
    }

    @Override
    public int lastIndexOf(E e) {
        for (int i = size - 1; i >= 0; i--) {
            if (e.equals(data[i]))
                return i;
        }
        return -1;
    }

    @Override
    public E remove(int index) {
        checkIndex(index);
        E e = data[index];
        for (int j = index; j < size - 1; j++)
            data[j] = data[j + 1];
        data[size - 1] = null;
        size--;     
        return e;
    }

    @Override
    public E set(int index, E e) {
        checkIndex(index);
        E old = data[index];
        data[index] = e;
        return old;
    }
    
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i < size - 1)
                res.append(", ");
        }
        return res.toString() + "]";
    }
    
    @SuppressWarnings("unchecked")
    public void trimToSize() {
        if (size != data.length) {
            E[] newData = (E[]) new Object[size];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
    }
    
    @Override
    public Iterator<E> iterator() {
        return new ArrayListIterator();
    }
    
    @SuppressWarnings("unchecked")
    private void ensureCapacity() {
        if (size >= data.length) {
            E[] newData = (E[]) new Object[2 * size + 1];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
    }
    
    private void checkIndex(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("index " + index + " ouf of bounds");
    }

    private class ArrayListIterator implements Iterator<E> {
        private int current = 0;
        
        @Override
        public boolean hasNext() {
            return (current < size);
        }       
        
        @Override
        public E next() {
            return data[current++];
        }
        
        @Override
        public void remove() {
            MyArrayList.this.remove(current);
        }       
    }
}

接口、抽象类和测试用例

MyList接口

MyList接口
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
package algorithms.arrayList;

public interface MyList<E> extends Iterable<E> {
    void add(E e);
    
    void add(int index, E e);
    
    void clear();
    
    boolean contains(E e);
    
    E get(int index);
    
    int indexOf(E e);
    
    boolean isEmpty();
    
    int lastIndexOf(E e);
    
    boolean remove(E e);
    
    E remove(int index);
    
    Object set(int index, E e);
    
    int size();
    
    boolean addAll(MyList<E> otherList);
    
    boolean removeAll(MyList<E> otherList);
    
    boolean retainAll(MyList<E> otherList); 
}

MyAbstractList抽象类

MyAbstractList抽象类
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package algorithms.arrayList;

public abstract class MyAbstractList<E> implements MyList<E> {  
    protected int size = 0 ;
    
    protected MyAbstractList() {
        
    };  
    protected MyAbstractList(E[] objects) {
        for (int i = 0; i < objects.length; i++)
            add(objects[i]);
    }
    
    @Override
    public void add(E e) {
        add(size, e);
    }
    
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean remove(E e) {
        if (indexOf(e) >= 0) {
            remove(indexOf(e));
            return true;
        } else {
            return false;
        }
    }   

    @Override
    public int size() {
        return size;
    }
    
    @Override
    public boolean addAll(MyList<E> otherList) {
        boolean changed = false;
        for ( int i = 0; i < otherList.size(); i++) {
            E e = otherList.get(i);
            if (!contains(e)) {
                add(e);
                changed = true;
            }
        }
        return changed;
    }

    @Override
    public boolean removeAll(MyList<E> otherList) {
        boolean changed = false;
        for (int i = 0; i < otherList.size(); i++) {
            E e = otherList.get(i);
            if (contains(e)) {
                remove(e);
                changed = true;
            }
        }
        return changed;
    }

    @Override
    public boolean retainAll(MyList<E> otherList) {
        boolean changed = false;
        for (int i = size - 1; i >= 0; i--) {
            E e = otherList.get(i);
            if (!otherList.contains(e)) {
                remove(e);
                changed = true;
            }
        }
        return changed;
    }

}

MyArrayList测试用例

MyArrayList测试用例
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
package algorithms.arrayList;

public class TestMyArrayList {
    public static void main(String[] args) {
        String[] array1 = {"Tom", "George", "Peter", "Jean", "Jane"};
        MyList<String> list1 = new MyArrayList<>(array1);

        String[] array2 = {"Tom", "George", "Michael", "Michelle", "Daniel"};
        MyList<String> list2 = new MyArrayList<>(array2);
        System.out.println("Create two MyArrayLists:");
        print(list1, list2);        
        
        System.out.println("Invoke list1.addAll(list2):");
        list1.addAll(list2);
        print(list1, list2);
        System.out.println("Recreate list1 and list2 with the same initial values,"
         + "\ninvoke list1.removeAll(list2), and displays list1 and list2:");
        list1.clear();
        list1.addAll(new MyArrayList<>(array1));
        list1.removeAll(list2);
        print(list1, list2);
        
        System.out.println("Recreate list1 and list2 with the same initial values," 
        + "\ninvokes list1.retainAll(list2), and displays list1 and list2:");
        list1.clear();
        list1.addAll(new MyArrayList<>(array1));
        list1.retainAll(list2);
        print(list1, list2);
    }

    public static void print(MyList<String> list1, MyList<String> list2) {
        System.out.println("List1: " + list1);
        System.out.println("List2: " + list2);
        System.out.println();
    }
}
0%