表

算法与数据结构
  1. 表的简单数组实现
  2. 简单链表
  3. 一些情况下的时间复杂度对比

本文是阅读《数据结构与算法分析 Java语言描述》所做的备忘笔记。

表的简单数组实现

对表的所有操作都可以通过使用数组来实现。虽然数组是由固定的容量创建的，但在需要的时候可以使用双倍的容量创建一个不同的数组。他解决了使用数组带来的最严重的问题，即从历史上看为了使用一个数组，需要对表的大小进行估计。而这种估计在Java或者任何现代编程语言都是不需要的。

1
2
3
4
5
6
7
Int{] arr=new int [10];

//下面我们决定需要扩大 arr. 
Int[] newArr = new int[arr.Length *2]; 
for (int i=0; i <arr. Length; i++)
    newArri] =arr[i]; 
arr = newArr;

数组的实现可以使得printList以线性时间被执行，而findKth操作则花费常数时间，这正是我们所能够预期的。不过，插人和删除的花费却潜藏着昂贵的开销，这要看插人和删除发生在什么地方。最坏的情形下，在位置0的插人（即在表的前端插人）首先需要将整个数组后移一个位置以空出空间来，而删除第一个元素则需要将表中的所有元素前移一个位置，因此这两种操作的最坏情况为 O (N）。平均来看，这两种操作都需要移动表的一半的元素，因此仍然需要线性时间。另一方面，如果所有的操作都发生在表的高端，那就没有元素需要移动，而添加和删除则只花费 0 (1) 时间。
存在许多情形，在这些情形下的表是通过在高端进行插人操作建成的，其后只发生对数组的访问（即只有findKth操作）。在这种情况下，数组是表的一种恰当的实现。然而，如果发生对表的一些插人和删除操作，特别是对表的前端进行，那么数组就不是一种好的选择。下一节处理另一种数据结构：链表（linked list）。

数组列表的代码实现：

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
public class MyArrayList<T> implements Iterable<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private T[] theItems;
    private int currentSize;

    private int modCount = 0;

    public MyArrayList() {
        doClear();
    }
    
    public int size() {
        return currentSize;
    }

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

    public T get(int idx) {
        if (idx < 0 || idx >= theItems.length) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return theItems[idx];
    }

    public T set(int idx, T x) {
        if (idx < 0 || idx >= theItems.length) {
            throw new ArrayIndexOutOfBoundsException();
        }
        T oldVal = theItems[idx];
        theItems[idx] = x;
        return oldVal;
    }

    private void ensureCapacity(int newSize) {
        if (newSize <= currentSize) {
            return;
        }
        T[] oldItems = theItems;
        theItems = (T[]) new Object[newSize];
        for (int i = 0; i < currentSize; i++) {
            theItems[i] = oldItems[i];
        }
        oldItems = null;
    }

    public boolean add(T x) {
        add(size(), x);
        return true;
    }

    private void add(int idx, T x) {
        if (currentSize == theItems.length) {
            ensureCapacity(currentSize * 2 + 1);
        }
        for (int i = currentSize; i > idx; i--) {
            theItems[i] = theItems[i - 1];
        }
        theItems[idx] = x;
        modCount++;
        currentSize++;
    }

    public T remove(int idx) {
        if (idx < 0 || idx >= theItems.length) {
            throw new ArrayIndexOutOfBoundsException();
        }
        T removeItem = theItems[idx];
        for (int i = idx; i < currentSize - 1; i++) {
            theItems[i] = theItems[i + 1];
        }
        currentSize--;
        modCount++;
        return removeItem;
    }
    
    public void clear() {
        doClear();
    }

    private void doClear() {
        currentSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    private class ArrayListIterator implements Iterator<T> {

        private int expectedModCount = 0;

        private boolean isOkToRemove = false;
        private int current;

        @Override
        public boolean hasNext() {
            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
            return current < currentSize;
        }

        @Override
        public T next() {
            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T val = theItems[current++];
            isOkToRemove = true;
            return val;
        }

        @Override
        public void remove() {
            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
            if (!isOkToRemove) {
                throw new IllegalStateException();
            }
            MyArrayList.this.remove(--current);
            expectedModCount++;
            isOkToRemove = false;
        }
    }
    @Override
    public Iterator<T> iterator() {
        return new ArrayListIterator();
    }
}

简单链表

为了避免插人和删除的线性开销，我们需要保证表可以不连续存储，否则表的每个部分都可能需要整体移动。下图指出链表的一般想法。
此处输入图片的描述
为了执行printList或find(x），只要从表的第一个节点开始然后用一些后继的next链遍历该表即可。这种操作显然是线性时间的，和在数组实现时一样，不过其中的常数可能会比用数组实现时要大。findKth 操作不如数组实现时的效率高；findKth(i）花费O(i）的时间并以这种明显的方式遍历链表而完成。在实践中这个界是保守的，因为调用findKth常常是以（按i）排序后的方式进行。例如，findKth (2), findKth (3)，findKth (4) 以及 findKth(6)可通过对表的一次扫描同时实现。
remove 方法可以通过修改一个 next 引用来实现。下图给出在原表中删除第三个元素的结果。
此处输入图片的描述
Insert 方法需要使用 new操作符从系统取得一个新节点，此后执行两次引用的调整。其一般想法在图 3-3 中给出，其中的虚线表示原来的 next 引用。
此处输入图片的描述
我们看到，在实践中如果知道变动将要发生的地方，那么向链表插人或从链表中删除一项的操作不需要移动很多的项，而只涉及常数个节点链的改变。
在表的前端添加项或删除第一项的特殊情形此时也属于常数时间的操作，当然要假设到链表前端的链是存在的。只要我们拥有到链表最后节点的链，那么在链表末尾进行添加操作的特殊情形（即让新的项成为最后一项）可以花费常数时间。因此，典型的链表拥有到该表两端的链。删除最后一项比较复杂，因为必须找出指向最后节点的项，把它的 next 链改成 null，然后再更新持有最后节点的链。在经典的链表中，每个节点均存储到其下一节点的链，而拥有指向最后节点的链并不提供最后节点的前驱节点的任何信息。
保留指向最后节点的节点的第3个链的想法行不通，因为它在删除操作期间也需要更新。我们的做法是，让每一个节点持有一个指向它在表中的前驱节点的链，如下图所示，我们称之为双链表（doubly linked list）。
此处输入图片的描述

简单双链表的代码实现：

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
public class MyLinkedList<T> implements Iterable<T> {

    private static class Node<T> {

        public T data;
        public Node<T> prev;
        public Node<T> next;

        public Node(T data) {
            this(data, null, null);
        }

        public Node(T data, Node<T> prev, Node<T> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }

    }
    private int modCount = 0;

    private int currentSize;

    private Node<T> beginMarker;
    private Node<T> endMarker;

    public MyLinkedList() {
        doClear();
    }

    public void clear() {
        doClear();
    }
    
    private void doClear() {
        currentSize = 0;
        beginMarker = new Node<T>(null, null, null);
        endMarker = new Node<T>(null, beginMarker, null);
        beginMarker.next = endMarker;
        currentSize = 0;
        modCount++;
    }

    public int size() {
        return currentSize;
    }

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

    public boolean add(T x) {
        add(size(), x);
        return true;
    }

    public void add(int idx, T x) {
        addBefore(getNode(idx, 0, size()), x);
    }

    private void addBefore(Node<T> p, T x) {
        Node<T> newNode = new Node<T>(x, p.prev, p.next);
        p.prev.next = newNode;
        p.prev = newNode;
        modCount++;
        currentSize++;
    }

    public T get(int idx) {
        return getNode(idx).data;
    }

    public T set(int idx, T newVal) {
        Node<T> node = getNode(idx);
        T oldVal = node.data;
        node.data = newVal;
        return oldVal;
    }
    
    private Node<T> getNode(int idx) {
        return getNode(idx, 0, size() - 1);
    }

    private Node<T> getNode(int idx, int lower, int upper) {

        if (idx < lower || idx > upper) {
            throw new IndexOutOfBoundsException();
        }

        Node<T> p;

        if (idx < size() / 2) {
            p = beginMarker.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;
    }

    public T remove(int idx) {
        return remove(getNode(idx));
    }

    public T remove(Node<T> p) {
        p.prev.next = p.next;
        p.next.prev = p.prev;
        modCount++;
        currentSize--;
        return p.data;
    }

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

    private class LinkedListIterator implements Iterator<T> {
        private int expectedModCount = modCount;
        
        private boolean isOkToRemove = false;
        private Node<T> current = beginMarker.next;

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

        @Override
        public T next() {

            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T nextItem = current.data;
            current = current.next;
            isOkToRemove = true;
            return nextItem;
        }

        @Override
        public void remove() {
            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
            if (!isOkToRemove) {
                throw new IllegalStateException();
            }
            isOkToRemove = false;
            expectedModCount++;
            MyLinkedList.this.remove(current.prev);
        }
    }
}

一些情况下的时间复杂度对比

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

不管 ArrayList 还是 LinkedList 作为参数被传递，makeListl 的运行时间都是 O (N），因为对 add 的每次调用都是在表的末端进行从而均花费常数时间（可以忽略对ArrayList偶尔进行的扩展）。另一方面，如果我们通过在表的前端添加一些项来构造一个 List:

1
2
3
4
5
public static void makeList2 (List<Integer> lst, int N){
    lst.clear ();
    for (inti=0; i <N; i++)
        lst. Add (0，i);
}

那么，对于 LinkedList 它的运行时间是 O (N），但是对于 ArrayList 其运行时间则是 O (N2），因为在 ArrayList 中，在前端进行添加是一个 0 (N）操作。下一个例程是计算 List 中的数的和：

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

这里，ArrayList 的运行时间是 O (N），但对于LinkedList来说，其运行时间则是0(N2），因为在 LinkedList 中，对 get 的调用为 0 (N）操作。可是，要是使用一个增强的 for 循环，那么它对任意 List 的运行时间都是0(N），因为迭代器将有效地从-项到下-项推进。

对搜索而言，ArrayList 和 LinkedList 都是低效的，对 Collection 的 contains 和 remove 两个方法（它们都以 AnyIype为参数）的调用均花费线性时间。

在ArrayList中有一个容量的概念，它表示基础数组的大小。在需要的时候，ArrayList将自动增加其容量以保证它至少具有表的大小。如果该大小的早期估计存在，那么ensureCapacity可以设置容量为一个足够大的量以避免数组容量以后的扩展。再有，trimToSize 可以在所有的 ArrayList添加操作完成之后使用以避免浪费空间。

另外建议阅读下《数据结构与算法分析 Java语言描述》 P50，关于remove的例子。

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器