Songbirds


春

表与java中表的实现

  • ~16.50K 字
  1. 1. 3.1 抽象数据类型
  2. 2. 3.2表ADT
    1. 2.1. 3.2.1表的简单数组实现
    2. 2.2. 3.2.2简单链表
  3. 3. 3.3 Java Collections API中的表
    1. 3.1. 3.3.1 Collections接口
    2. 3.2. 3.3.2 Iterator接口
    3. 3.3. 3.3.3 List接口与继承的类
    4. 3.4. 3.3.4 LikedList中的remove方法
    5. 3.5. 3.3.5 ListIterator接口
  4. 4. 3.4 ArrayList类的实现
    1. 4.1. 3.4.1 基本类
    2. 4.2. 3.4.2 嵌套类与内部类
  5. 5. 3.5 LinkedList实现
    1. 5.1. 3.5.1 基本类

《数据结构与算法分析Java语言描述》第二章3.1到3.5节读书笔记

3.1 抽象数据类型

抽象数据类型(ADT)：是带有一组操作的一些对象的集合

  对于集合ADT，可以有像添加(add)、删除(remove)、与包含(contain)这样的一些操作。也可以只要两种操作，并(union)和查找(find)。
ADT的实现一般取决与程序设计者，当ADT被程序设计者正确的实现后，使用该语言可以不必要知道他们如何实现。


3.2表ADT

形如A0,A1,A2,…,AN−1A_0,A_1,A_2,\ldots, A_{N-1}，这个表的大小为N，如果该表的大小为0，则该表称为空表，除空表外的任何表，AiA_i后继Ai−1A_{i-1}(或继Ai−1A_{i-1}之后，i<N)，并称Ai−1A_{i-1}前驱Ai(i>0)A_i(i>0)。

  常用操作(不同的语言有不同的实现)：

  1. printList：java没有直接实现，如果是List，可以直接打印，因为其父类AbstractCollection重写了toString方法。
    如果是数组，可以通过Arrays.toString(数组)，方法实现打印。
  2. makeEmpty：如果是List，有clear()方法，将所有元素置为null。
  3. find：找到某元素第一次出现的位置，jdk好像没实现
  4. insert：jdk实现的是add方法，有重载，不指定index，则默认最后，可以指定index。
  5. findKth：查找某个index下的元素，如果是List，有get(index)方法，数组则int[index]。
  6. remove：移除某个index的元素

3.2.1表的简单数组实现

  数组的实现，使printList可以用线性的时间O(N)执行，findKth则花费常数时间。插入和删除开销昂贵，在最坏的情况下，在索引为0的位置插入，需要将所有元素向后移动一位。而删除一个位置则需要将所有元素向前移动一位。两种操作的时间都为O(N)。但是如果所有元素都操作在表的高端(末端，数组有容量的情况下，否则需要昂贵的扩容)。添加和删除只需要O(1)的时间。

3.2.2简单链表

  链表由一系列节点组成，这些节点在内存中可以不相连，每个节点均含有表元素和包含该元素后继节点的链 link(指针)，称之为next链。最后一个节点的next链为null。
  执行printList与find(x)，可以从表的头的第一个节点开始使用后继的next遍历该表即可，这种操作和数组一样，是线性的时间。
  remove方法通过修改一个next指针实现，insert方法使用new操作符从系统中新增一个节点，此后执行两次引用调整。如图所示，链表的插入与删除都只需要花费常数的时间。

  双向链表：让每一个节点持有一个指向它在表中的前驱节点的链


3.3 Java Collections API中的表

表ADT是在Collections API中的实现数据结构之一。

3.3.1 Collections接口

  Collection接口扩展Iterable接口(可迭代)，实现该接口的类可以拥有简单的for循环，

1
2
3
4
5
6
// 此静态方法void前面的<AnyType>是引用类上的<AnyType>泛型
public static <AnyType> void print(Collection<AnyType> coll) {
    for (AnyType item : coll) {
        System.out.println(item);
    }
}

3.3.2 Iterator接口

  实现Iterator接口的集合必须实现iterator接口方法，返回一个iterator，该iterator将当前位置的概念在对象内部存储。该iterator是java.util包中定义。
  每次对next调用，都给出该集合的下一项，hasNext()用来返回是否存在下一项。对于实现Iterable接口的增强for循环，编译器会重写，将其转换为由迭代器iterator进行迭代。所以前面的print被编译器改写为。

1
2
3
4
5
6
7
public static <AnyType> void print(Collection<AnyType> coll) {
    Iterator<AnyType> iterator = coll.iterator();
    while (iterator.hasNext()) {
        AnyType item = iterator.next();
        System.out.println(item);
    }
}

  iterator接口还有一个remove方法，该方法删除next返回的项，虽然Collection接口也有remove方法，但是Iterator方法有更多优点。Collecction的remove方法，必须要指定删除那一项，而Iterator可以在遍历的过程中删除。如果直接使用for循环remove集合中的某个元素，则会抛出异常，这时就应该使用迭代器的remove方法。

3.3.3 List接口与继承的类

  List接口继承了Collection接口，如下包括其自己定义的一些重要的方法

1
2
3
4
5
6
7
8
public interface MyList<T> extends Collection<T> {
    T get(int index);
    T set(int index, T newVal);
    void add(int index, T x);
    void remove(int index);
    // 此方法将产生更加复杂的迭代器
    ListIterator<T> listIterator();
}

  List ADT有两种流行的实现方式，ArrayList是可变数组的具体实现，具有数组的特点，get与set花费常数的时间，add与remove的花费线性O(N)的时间(不在末端的情况)。LinkedList则实现了一种双向链表。具有一系列操作首尾位置的方法，其具有链表的特点，get的时间近似线性。
构造一个新的List

1
2
3
4
5
6
public static void makeList1(List<Integer> lst, int N) {
    lst.clearn();
    for (int i = 0; i < N; i++) {
        lst.add(i);
    }
}

  该构造，无论传入的是ArrayList还是LinkedList都是O(N)，每次都是在末尾添加。不考虑ArrayList的扩容。

在表的前端插入元素

1
2
3
4
5
6
public static void makeList(List<Integer> lst, int N) {
    lst.clearn();
    for (int i = 0; i < N; i++) {
        lst.add(0, i);
    }
}

  该构造，对于ArrayList是O(N2)O(N^2)，因为其每次插入花费时间O(N)，对于LinkedList则花费时间O(N)

求表中所有元素的和

1
2
3
4
5
6
7
public static int sum(List<Integer> lst {
    int total = 0;
    for (int i = 0; i < N; i++) {
        total += lst.get(i);
    }
    return total;
}

  对于ArrayList其时间为O(N)，LinkedList时间为O(N2)O(N^2)，因为其每次获取元素需要O(N)的时间。如果使用增强for循环，则两个都是O(N)，将使用迭代器一直迭代下去。对搜索而言，两者都是低效的，contains与remove方法均花费线性时间。

3.3.4 LikedList中的remove方法

考虑如下一个例子，删除表中的所有偶数。表[6,5,1,4,2]，删除后表中仅有5，1两个元素。

  对于ArrayList，其删除的操作是O(N)，不是，一个好策略，对于LinkedList，如果不使用迭代器则是O(N)(首先需要找到该元素才能删除)，如果使用迭代器，则一次删除为O(1)。 如果使用普通的while循环，那么对于ArrayList是O(N2)O(N^2)的时间，对于LinkedList也是O(N^2)的时间。

1
2
3
4
5
6
7
8
9
10
11
12
// 方法不高效,并且在循环中使用collection的remove方法是一个非法的操作
public static void removeEvensVer1(List<Integer> lst) {
    int i = 0;
    while (i < lst.size()) {
        if (lst.get(i) % 2 == 0) {
            lst.remove(i);
        } else {
            // 如果没有remove，则i++,(remove非法)
            i ++;
        }
    }
}

  如下，该方法使用了增强for循环(即使用了迭代器)，但是使用了collection的remove方法，该方法必须再次搜索该项，因此remove执行时间仍然为O(N)，总体时间为O(N2)O(N^2)，并且同上，对增强for循环使用的基础迭代器中，collection的remove元素也是非法的

1
2
3
4
5
6
7
8
9
// 方法不高效,并且在循环中使用collection的remove方法是一个非法的操作
public static void removeEvensVer1(List<Integer> lst) {
    for (Integer x : lst) {
        if (x % 2 == 0) {
            // collection的remove需要找到该元素，为O(N),且非法
            lst.remove(x);
        }
    }
}

  如下使用迭代器，对于LinkedList是O(N)的复杂度，对于ArrayList则依旧是O(N2)O(N^2)的复杂度(remove后，数组必须整体向前移动)

1
2
3
4
5
6
7
8
9
public static List<Integer> removeEvensVer3(List<Integer> lst) {
    Iterator<Integer> itr = lst.iterator();
        while (itr.hasNext()) {
            if (itr.next() % 2 == 0) {
            itr.remove();
        }
    }
    return lst;
}

3.3.5 ListIterator接口

  该接口只能被List使用，其扩展了Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface ListIterator<AnyType> extends Iteerator<AnyType> {
    // 前向遍历， 是否有前一项
    boolean hasPrevious();
    // 获取前一项
    AnyType previous();
    
    // 正向遍历，是否有后一项
    boolean hasNext();
    // 获取后一项
    AnyType next();
    
    // 在当前位置插入，即next项后移一位
    void add(AnyType x);
    // 设置当前项的值
    void set(AnyType newVal)
}

3.4 ArrayList类的实现

  此处手动实现一个MyArrayList，该类独立实现。将具有以下特点：

  1. 将保持基础数组，数组的容量，存储当前项数
  2. 将提供方法改变数组的容量，(将改变容量后的数组拷贝到新数组)
  3. 提供get与set实现
  4. 提供基本的例程，size()与isEmpty()实现，clear()实现，提供remove()，add()
  5. 实现Iterator接口，提供next，hasNext，remove。

3.4.1 基本类

  该类不检测非法的迭代器remove方法。会在之后的3.5节实现。

基本类主代码实现(点击展开)
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
public class MyArrayList<AnyType> implements Iterable<AnyType> {

    /**
     * 默认容量为10
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 定义size
     */
    private int theSize;

    /**
     * 定义数组
     */
    private AnyType[] theItems;

    // 空参构造方法，清空数组
    public MyArrayList() {
        doClear();
    }

    public void clear() {
        doClear();
    }

    /**
     * 清空方法
     */
    private void doClear() {
        theSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    /**
     * 获取数组元素的个数
     * @return
     */
    public int size() {
        return theSize;
    }

    /**
     * 判断数组的元素是否为空
     * @return
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 将数组的容量截取到元素个数的量
     */
    public void trimToSize() {
        ensureCapacity(size());
    }

    /**
     * 获取指定索引的元素
     */
    public AnyType get(int idx) {
        if (idx < 0 || idx >= size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return theItems[idx];
    }

    /**
     * 设置指定位置的值,并返回旧的值
     */
    public AnyType set(int idx, AnyType newVal) {
        if (idx < 0 || idx >= size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        AnyType old = theItems[idx];
        theItems[idx] = newVal;
        return old;
    }

    /**
     * 修改数组的容量
     */
    public void ensureCapacity(int newCapacity) {
        if (newCapacity < theSize) {
            return;
        }

        AnyType[] old = theItems;
        // 创建指定大小的空数组，用于存放截取后的数组
        theItems = (AnyType[]) new Object[newCapacity];
        for (int i = 0; i < size(); i++) {
            theItems[i] = old[i];
        }
    }

    /**
     * 向数组中添加指定的元素, 默认为已有的元素的个数最后
     */
    public boolean add(AnyType x) {
        add(size(), x);
        return true;
    }

    /**
     * 向数组的指定的位置添加元素
     */
    public void add(int idx, AnyType x) {
        // 如果数组的长度等于元素个数量，则数组需要扩容
        if (theItems.length == size()) {
            ensureCapacity(size() * 2 + 1);
        }
        // 将指定位置与指定位置之后的所有元素后移一位
        for (int i = theSize; i > idx; i--) {
            // 最后，idx + 1 = idx，即将idx位置的元素向后移动一位
            theItems[i] = theItems[i-1];
        }
        // 设置指定位置的值
        theItems[idx] = x;
        theSize++;
    }

    public AnyType remove(int idx) {
        AnyType removeItem = theItems[idx];
        // 将idx处的所有元素前移一位
        for (int i = idx; i < size() - 1; i++) {
            theItems[i] = theItems[i + 1];
        }
        theSize--;
        return removeItem;
    }

    /**
     * 获取迭代器
     */
    @Override
    public Iterator<AnyType> iterator() {
        return new ArrayListIterator();
    }

    /**
     * 内部类，用于创建迭代器
     */
    private class ArrayListIterator implements Iterator<AnyType> {

        private int current = 0;

        @Override
        public boolean hasNext() {
            return current < size();
        }

        @Override
        public AnyType next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return theItems[current++];
        }

        @Override
        public void remove() {
            MyArrayList.this.remove(current-1);
        }
    }
}

3.4.2 嵌套类与内部类

迭代器-内部类：可以使用，推荐这种(就是上面的实现)

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
public class MyArrayList2<AnyType> implements Iterable<AnyType> {
    // 定义数组大小
    private int theSize;
    // 定义数组
    private AnyType[] theItems;

    @Override
    public Iterator<AnyType> iterator() {
        // this指代这个类
        return new ArrayListIterator();
    }

    // 重新定义的private内部类，不能使用泛型，可以直接使用外部类参数(不冲突的情况)
    private class ArrayListIterator implements Iterator{
        // 当前索引下标位置
        private int current = 0;

        @Override
        public boolean hasNext() {
            return current < size();
        }

        @Override
        public AnyType next() {
            // 此处实际上无法使用theItems数组参数，因为此内部类是一个顶级内部类，而theItems是外部类的一个私有参数
            // 现在为做出修改后的，可以使用，不是顶级内部类，在外部参数与内部类冲突的情况下可以直接使用外部类参数theItems
            return theItems[current++];
        }

        @Override
        public void remove() {
            // 使用外部类的remove方法，与此内部类的remove(就是此方法)方法冲突，需要指明
            MyArrayList2.this.remove(--current);
        }
    }
}

迭代器-嵌套类：就是把内部类申明为静态的，同时指定泛型，构造函数传入外部参数，可以使用，但不推荐，使用上面的。故不再列出。


3.5 LinkedList实现

  同上，此处将手动实现一个LinkedList

  1. MyLinkedList类本身，包含到两端的链、表的大小和一些方法
  2. Node类，私有嵌套(静态内部)类，一个Node节点包含一个数据以及到前一个节点链和到下一个节点的链，还有构造方法
  3. LinkedListIterator类，抽象了位置的概念，私有类，实现Iterator，提供next方法、hasNext和remove实现

3.5.1 基本类

  该链表主要由Node节点组成，迭代器去遍历实现，迭代器存储当前节点的引用。该实现真实的链表前端额外创建一个节点，称为头节点，末端也额外创建一个节点，称为尾节点。使用这些节点的好处在于简化编码，删除头节点与尾节点都不再是特殊情况(删除算法也需要访问被删除的前一个节点)。

基本类主代码(点击展开)
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
public class MyLinkedList<AnyType> implements Iterable<AnyType> {
    // 使用了嵌套类Node，类时私有的，其属性是否私有无关紧要(只有MyLinkedList类能见到该类，其他外部类无法访问)
    private static class Node<AnyType> {
        public AnyType data;            // 节点内的数据
        public Node<AnyType> prev;      // 节点的上一个节点
        public Node<AnyType> next;      // 节点的下一个节点
        // 构造方法，创建一个新的节点；节点的数据，节点的上一个节点p,节点的下一个节点n
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
            data = d;
            prev = p;
            next = n;
        }
    }

    // 链表长度
    private int theSize;
    // 自从构造以来，对链表所做改变次数，当调用迭代器LinkedListIterator的方法时，
    // 和迭代器存储的modCount方法比较，如果不一致，则报并发异常ConcurrentModificationException
    private int modCount = 0;
    // 链表头节点
    private Node<AnyType> beginMaker;
    // 链表尾节点
    private Node<AnyType> endMarker;

    // 构造方法，创建时清除现有链表
    public MyLinkedList() {
        doClear();
    }
    // 供外部调用的clear方法
    public void clear() {
        doClear();
    }

    // 真正的doClear方法，
    private void doClear() {
        // 创建一个头节点，由于此时还没有尾节点故n节点为null
        beginMaker = new Node<>(null, null, null);
        // 创建尾节点，上一个节点指向头节点
        endMarker = new Node<>(null, beginMaker, null);
        // 现在可以指定下一个节点为尾节点
        beginMaker.next = endMarker;
        // 初始化长度为0
        theSize = 0;
        // 对节点的修改次数加1
        modCount++;
    }

    public int size() {
        return theSize;
    }

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

    // 向链表中添加元素，不指定位置，默认为尾节点前(即最后)
    public boolean add(AnyType x) {
        // 插入节点为原size()，因为索引下标为0开始，所以实际最大为size()-1
        add(size(), x);
        return true;
    }

    // 向链表中添加元素，指定插入下标
    public void add(int idx, AnyType x) {
        // 插入下标为x,则是插入原下标为x的前面
        addBefore(getNode(idx, 0, size()), x);
    }
    // 获取指定索引处的值data
    public AnyType get(int idx) {
        return getNode(idx).data;
    }
    // 设置指定索引处的值
    public AnyType set(int idx, AnyType newVal) {
        Node<AnyType> p = getNode(idx);
        AnyType oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }

    // 对外公开的remove方法，只需要从指定删除处的索引
    public AnyType remove(int idx) {
        return remove(getNode(idx));
    }

    // 在指定元素前添加节点
    private void addBefore(Node<AnyType> p, AnyType x) {
        Node<AnyType> newNode = new Node<>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        theSize++;
        modCount++;
    }
    //  真正的删除方法，将p从链表断开
    private AnyType remove(Node<AnyType> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        return p.data;
    }

    private Node<AnyType> getNode(int idx) {
        return getNode(idx, 0, size() -1);
    }
    // 获取指定索引处的节点
    private Node<AnyType> getNode(int idx, int lower, int upper) {
        Node<AnyType> p;
        if (idx < lower || idx > upper) {
            throw new IndexOutOfBoundsException();
        }
        // 如果节点在前半部分，从前面遍历
        if (idx < size() / 2) {
            p = beginMaker.next;
            for (int i = 0; i < idx; i++) {
                p = p.next;
            }
        } else {
            // 如果节点在后半部分，从前面遍历
            p = endMarker;
            for (int i = size(); i > idx; i--) {
                p = p.prev;
            }
        }
        return p;
    }


    @Override
    public Iterator<AnyType> iterator() {
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements Iterator<AnyType> {
        // 将current节点初始化为头节点的下一个节点
        private MyLinkedList.Node<AnyType> current = beginMaker.next;
        // 使期望的修改次数=外部类的修改次数
        private int expectedModCount = modCount;
        // 是否可以remove
        private boolean okToRemove = false;

        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        @Override
        public AnyType next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        @Override
        public void remove() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new IllegalStateException();
            }
            // 真正的remove,不改变currentt(ArrayList需要更改)
            MyLinkedList.this.remove(current.prev);
            expectedModCount++;
            okToRemove = false;
        }
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可