数据结构与算法(1): 线性结构-表

发表于   |   分类于

数组

数组能够顺序存储相同类型的多个数据，数据的元素在内存上的存储地址是连续的。在声明数组的时候，需要指定数组的名称，它含有的数据类型以及数组的长度。
特点：数据是连续的，随机访问速度快。
（在Java中Collection集合中提供了ArrayList和Vector实现动态数组）

表（线性表）

线性表：零个或多个数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

  • 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
  • 线性表的链式存储结构，是由一系列结点组成，这些节点不必再内存中相连。结点包括存储元素的数据域和存储直接后继或前驱的指针域。

具体实现可以参见java集合类中的ArrayList和LinkedList。

数组实现

1
2
3
4
5
6
7
8
9
10
11
/**
 * 顺序存储结构：表的简单数组实现
 */
public class SequenceList {
	// 线性表的最大存储容量
    private static final int MAX_VALUE = 20;
    // 线性表实际存储位置
    private int[] data = new int[MAX_VALUE];
    // 线性表的当前长度
    private int length = 0;
}

单链表

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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
/**
 * 链式存储结构：单链表
 */
public class SingleLinkedList<T> {
    // 首元素
    private Node<T> head;
    // 尾元素
    private Node<T> last;
    // 元素个数
    private int theSize = 0;
    private static class Node<T>{
        private T value;
        private Node<T> next;
        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }
    public SingleLinkedList() {
    }
    /**
     * 增加一个数据到list
     * @param v
     */
    public void add(T v){
        Node<T> newNode = new Node<>(v, null);
        if (isEmpty()){
            head = newNode;
            last = head;
        }else {
            last.next = newNode;
            last = newNode;
        }
        theSize++;
    }
    /**
     * 在index处添加元素v，其他元素后移
     * @param index
     * @param v
     */
    public void add(int index, T v){
        if (index == 0){
            Node<T> newNode = new Node<>(v, head);
            head = newNode;
        }else {
            checkIndex(index);
            Node<T> current = head;
            for (int i = 0; i < index - 1; i++){
                current = current.next;
            }
            Node<T> newNode = new Node<>(v, current.next);
            current.next = newNode;
        }
        theSize++;
    }
    /**
     * 根据索引获取值
     * @param index
     * @return
     */
    public T get(int index){
        return node(index).value;
    }
    /**
     * 是否包含传入的对象
     * @param obj
     * @return
     */
    public boolean contains(Object obj){
        return indexOf(obj) != -1;
    }
    /**
     * 删除list中首次出现的value
     * @param v
     * @return
     */
    public boolean remove(Object obj){
        Node<T> current = head;
        Node<T> prev = current;
        for (int i = 0; i < size(); i++){
            if (current.value.equals(obj)){
                if (i == 0){
                    head = current.next;
                    theSize--;
                    return true;
                }
                prev.next = current.next;
                theSize--;
                return true;
            }
            prev = current;
            current = current.next;
        }
        return false;
    }
    /**
     * 根据索引值删除元素
     * @param index
     * @return
     */
    public T remove(int index){
        checkIndex(index);
        theSize--;
        if (index == 0){
            Node<T> current = head;
            T val = current.value;
            head = current.next;
            current.value = null;
            current.next = null;
            return val;
        }else {
            Node<T> prev = node(index-1);
            Node<T> current = prev.next;
            T val = current.value;
            prev.next = current.next;
            current.value = null;
            current.next = null;
            return val;
        }
    }
    /**
     * 清空链表
     */
    public void clear(){
        head = null;
        theSize = 0;
    }
    /**
     * 打印全部链表
     */
    public void print(){
        if (head == null || size() == 0){
            System.out.println("链表为空");
        }else {
            Node<T> current = head;
            while (current != null){
                System.out.print(current.value + " ");
                current = current.next;
            }
        }
        System.out.println();
    }
    /**
     * Returns the index of the first occurrence of the specified element
     * in this list
     * @param obj
     * @return
     */
    public int indexOf(Object obj){
        int index = 0;
        if (obj == null){
            for (Node<T> x = head; x != null; x = x.next){
                if (x.value != null){
                    return index;
                }
                index++;
            }
        }else {
            for (Node<T> x = head; x != null; x = x.next){
                if (obj.equals(x.value)){
                    return index;
                }
                index++;
            }
        }
        return -1;
    }
    public int size(){
        return this.theSize;
    }
    public boolean isEmpty(){
        return this.size() == 0;
    }
    /**
     * Returns the (non-null) Node at the specified element index.
     */
    private Node<T> node(int index){
        checkIndex(index);
        Node<T> current = head;
        for (int i = 0; i < index; i++){
            current = current.next;
        }
        return current;
    }
    private void checkIndex(int index){
        if (index < 0 || index > size() - 1){
            throw new IndexOutOfBoundsException("传入索引无效:"+index);
        }
    }
}

双链表

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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
/**
 * 链式存储结构：双链表
 */
public class DoubleLinkedList<T> {
    private Node head;
    private Node tail;
    // 节点个数
    private int theSize = 0;
    private static class Node<T>{
        private T value;
        private Node prev;
        private Node next;
        Node(T value, Node prev, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
    public DoubleLinkedList() {
    }
    /**
     * 添加一个元素到双链表
     * @param v
     */
    public void add(T v){
        Node<T> newNode = new Node<>(v, tail, null);
        if (tail == null){
            head = newNode;
        }else {
            tail.next = newNode;
        }
        tail = newNode;
        theSize++;
    }
    /**
     * 根据索引获取元素
     * @param i
     * @return
     */
    public T get(int i){
        return node(i).value;
    }
    /**
     * 删除索引的元素
     * Removes the element at the specified position in this list
     * @param i
     * @return
     */
    public T remove(int i){
        return unlink(node(i));
    }
    /**
     * 删除传入的对象
     * Removes the first occurrence of the specified element from this list
     * @param obj
     * @return
     */
    public boolean remove(Object obj){
        if (obj == null){
            for (Node<T> x = head; x != null; x = x.next){
                if (x.value == null){
                    unlink(x);
                    return true;
                }
            }
        }else {
            for (Node<T> x = head; x != null; x = x.next){
                if (obj.equals(x.value)){
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 是否包含传入的对象
     * @param obj
     * @return
     */
    public boolean contains(Object obj){
        return indexOf(obj) != -1;
    }
    public int size(){
        return this.theSize;
    }
    public boolean isEmpty(){
        return this.size() == 0;
    }
    public void clear(){
        for (Node<T> x = head; x != null;){
            Node<T> next = x.next;
            x.value = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        head = tail = null;
        theSize = 0;
    }
    /**
     * Returns the index of the first occurrence of the specified element
     * in this list
     * @param obj
     * @return
     */
    public int indexOf(Object obj){
        int index = 0;
        if (obj == null){
            for (Node<T> x = head; x != null; x = x.next){
                if (x.value != null){
                    return index;
                }
                index++;
            }
        }else {
            for (Node<T> x = head; x != null; x = x.next){
                if (obj.equals(x.value)){
                    return index;
                }
                index++;
            }
        }
        return -1;
    }
    /**
     * Returns the index of the last occurrence of the specified element
     * in this list
     * @param obj
     * @return
     */
    public int lastIndexOf(Object obj){
        int index = size();
        if (obj == null){
            for (Node<T> x = tail; x != null; x = x.prev){
                index--;
                if (x.value == null){
                    return index;
                }
            }
        }else {
            for (Node<T> x = tail; x != null; x = x.prev){
                index--;
                if (obj.equals(x.value)){
                    return index;
                }
            }
        }
        return -1;
    }
    public void print(){
        if (head == null || size() == 0){
            System.out.println("链表为空");
        }else {
            Node<T> current = head;
            while (current != null){
                System.out.print(current.value + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
    /**
     * Returns the (non-null) Node at the specified element index.
     */
    private Node<T> node(int index){
        checkIndex(index);
        Node<T> current;
        if (index < (size() >> 1)){
            current = head;
            for (int i = 0; i < index; i++){
                current = current.next;
            }
        }else {
            current = tail;
            for (int i = size() - 1; i > index; i--){
                current = current.prev;
            }
        }
        return current;
    }
    private T unlink(Node<T> p){
        T val = p.value;
        Node<T> prev = p.prev;
        Node<T> next = p.next;
        if (prev == null){
            head = next;
        }else {
            prev.next = next;
            p.prev = null;
        }
        if (next == null){
            tail = prev;
        }else {
            next.prev = prev;
            p.next = null;
        }
        p.value = null;
        theSize--;
        return val;
    }
    private void checkIndex(int index){
        if (index < 0 || index > size() - 1){
            throw new IndexOutOfBoundsException("传入索引无效:"+index);
        }
    }
}

顺序存储结构和单链表结构的优缺点比较:

column 顺序存储结构 单链表存储结构
存储分配方式 连续的存储单元 任意的存储单元
时间性能 find:O(1), insert&delete:O(n) find:O(n), insert&delete:O(1)
空间性能 需要预分配存储空间 不需要预分配存储空间