Java数据结构学习笔记第一篇：
用程序后在那个的数据大致有四种基本的逻辑结构：
集合：数据元素之间只有"同属于一个集合"的关系
线性结构：数据元素之间存在一个对一个的关系
树形结构：数据元素之间存在一个对多个关系
图形结构或网状结构：数据元素之间存在多个对多个的关系
对于数据不同的逻辑结构，计算机在物理磁盘上通常有两种屋里存储结构
顺序存储结构
链式存储结构
本篇博文主要讲的是线性结构，而线性结构主要是线性表，非线性结构主要是树和图。
线性表的基本特征：
总存在唯一的第一个数据元素
总存在唯一的最后一个数据元素
除第一个数据元素外，集合中的每一个数据元素都只有一个前驱的数据元素
除最后一个数据元素外，集合中的每一个数据元素都只有一个后继的数据元素
1.线性表的顺序存储结构：是指用一组地址连续的存储单元一次存放线性表的元素。为了使用顺序结构实现线性表，程序通常会采用数组来保存线性中的元素，是一种随机存储的数据结构，适合随机访问。java中ArrayList类是线性表的数组实现。
|
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
|
import java.util.Arrays;public class SequenceList<T>{ private int DEFAULT_SIZE = 16; //保存数组的长度。 private int capacity; //定义一个数组用于保存顺序线性表的元素 private Object[] elementData; //保存顺序表中元素的当前个数 private int size = 0; //以默认数组长度创建空顺序线性表 public SequenceList() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一个初始化元素来创建顺序线性表 public SequenceList(T element) { this(); elementData[0] = element; size++; } /** * 以指定长度的数组来创建顺序线性表 * @param element 指定顺序线性表中第一个元素 * @param initSize 指定顺序线性表底层数组的长度 */ public SequenceList(T element , int initSize) { capacity = 1; //把capacity设为大于initSize的最小的2的n次方 while (capacity < initSize) { capacity <<= 1; } elementData = new Object[capacity]; elementData[0] = element; size++; } //获取顺序线性表的大小 public int length() { return size; } //获取顺序线性表中索引为i处的元素 public T get(int i) { if (i < 0 || i > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } return (T)elementData[i]; } //查找顺序线性表中指定元素的索引 public int locate(T element) { for (int i = 0 ; i < size ; i++) { if (elementData[i].equals(element)) { return i; } } return -1; } //向顺序线性表的指定位置插入一个元素。 public void insert(T element , int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("线性表索引越界"); } ensureCapacity(size + 1); //将index处以后所有元素向后移动一格。 System.arraycopy(elementData , index , elementData , index + 1 , size - index); elementData[index] = element; size++; } //在线性顺序表的开始处添加一个元素。 public void add(T element) { insert(element , size); } //很麻烦，而且性能很差 private void ensureCapacity(int minCapacity) { //如果数组的原有长度小于目前所需的长度 if (minCapacity > capacity) { //不断地将capacity * 2，直到capacity大于minCapacity为止 while (capacity < minCapacity) { capacity <<= 1; } elementData = Arrays.copyOf(elementData , capacity); } } //删除顺序线性表中指定索引处的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } T oldValue = (T)elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData , index+1 , elementData, index , numMoved); } //清空最后一个元素 elementData[--size] = null; return oldValue; } //删除顺序线性表中最后一个元素 public T remove() { return delete(size - 1); } //判断顺序线性表是否为空表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //将底层数组所有元素赋为null Arrays.fill(elementData , null); size = 0; } public String toString() { if (size == 0) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (int i = 0 ; i < size ; i++ ) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } }} |
2.线性表链式存储结构:将采用一组地址的任意的存储单元存放线性表中的数据元素。
链表又可分为：
单链表：每个节点只保留一个引用，该引用指向当前节点的下一个节点，没有引用指向头结点，尾节点的next引用为null。
循环链表：一种首尾相连的链表。
双向链表：每个节点有两个引用，一个指向当前节点的上一个节点，另外一个指向当前节点的下一个节点。
下面给出线性表双向链表的实现：java中LinkedList是线性表的链式实现，是一个双向链表。
|
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
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
|
public class DuLinkList<T>{ //定义一个内部类Node，Node实例代表链表的节点。 private class Node { //保存节点的数据 private T data; //指向上个节点的引用 private Node prev; //指向下个节点的引用 private Node next; //无参数的构造器 public Node() { } //初始化全部属性的构造器 public Node(T data , Node prev , Node next) { this.data = data; this.prev = prev; this.next = next; } } //保存该链表的头节点 private Node header; //保存该链表的尾节点 private Node tail; //保存该链表中已包含的节点数 private int size; //创建空链表 public DuLinkList() { //空链表，header和tail都是null header = null; tail = null; } //以指定数据元素来创建链表，该链表只有一个元素 public DuLinkList(T element) { header = new Node(element , null , null); //只有一个节点，header、tail都指向该节点 tail = header; size++; } //返回链表的长度 public int length() { return size; } //获取链式线性表中索引为index处的元素 public T get(int index) { return getNodeByIndex(index).data; } //根据索引index获取指定位置的节点 private Node getNodeByIndex(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } if (index <= size / 2) { //从header节点开始 Node current = header; for (int i = 0 ; i <= size / 2 && current != null ; i++ , current = current.next) { if (i == index) { return current; } } } else { //从tail节点开始搜索 Node current = tail; for (int i = size - 1 ; i > size / 2 && current != null ; i++ , current = current.prev) { if (i == index) { return current; } } } return null; } //查找链式线性表中指定元素的索引 public int locate(T element) { //从头节点开始搜索 Node current = header; for (int i = 0 ; i < size && current != null ; i++ , current = current.next) { if (current.data.equals(element)) { return i; } } return -1; } //向线性链式表的指定位置插入一个元素。 public void insert(T element , int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("线性表索引越界"); } //如果还是空链表 if (header == null) { add(element); } else { //当index为0时，也就是在链表头处插入 if (index == 0) { addAtHeader(element); } else { //获取插入点的前一个节点 Node prev = getNodeByIndex(index - 1); //获取插入点的节点 Node next = prev.next; //让新节点的next引用指向next节点，prev引用指向prev节点 Node newNode = new Node(element , prev , next); //让prev的next指向新节点。 prev.next = newNode; //让prev的下一个节点的prev指向新节点 next.prev = newNode; size++; } } } //采用尾插法为链表添加新节点。 public void add(T element) { //如果该链表还是空链表 if (header == null) { header = new Node(element , null , null); //只有一个节点，header、tail都指向该节点 tail = header; } else { //创建新节点,新节点的pre指向原tail节点 Node newNode = new Node(element , tail , null); //让尾节点的next指向新增的节点 tail.next = newNode; //以新节点作为新的尾节点 tail = newNode; } size++; } //采用头插法为链表添加新节点。 public void addAtHeader(T element) { //创建新节点，让新节点的next指向原来的header //并以新节点作为新的header header = new Node(element , null , header); //如果插入之前是空链表 if (tail == null) { tail = header; } size++; } //删除链式线性表中指定索引处的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } Node del = null; //如果被删除的是header节点 if (index == 0) { del = header; header = header.next; //释放新的header节点的prev引用 header.prev = null; } else { //获取删除点的前一个节点 Node prev = getNodeByIndex(index - 1); //获取将要被删除的节点 del = prev.next; //让被删除节点的next指向被删除节点的下一个节点。 prev.next = del.next; //让被删除节点的下一个节点的prev指向prev节点。 if (del.next != null) { del.next.prev = prev; } //将被删除节点的prev、next引用赋为null. del.prev = null; del.next = null; } size--; return del.data; } //删除链式线性表中最后一个元素 public T remove() { return delete(size - 1); } //判断链式线性表是否为空链表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //将底层数组所有元素赋为null header = null; tail = null; size = 0; } public String toString() { //链表为空链表时 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = header ; current != null ; current = current.next ) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } public String reverseToString() { //链表为空链表时 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = tail ; current != null ; current = current.prev ) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } }} |
线性表的两种实现比较
空间性能：
顺序表：顺序表的存储空间是静态分布的，需要一个长度固定的数组，因此总有部分数组元素被浪费。
链表：链表的存储空间是动态分布的，因此不会空间浪费。但是由于链表需要而外的空间来为每个节点保存指针，因此要牺牲一部分空间。
时间性能：
顺序表：顺序表中元素的逻辑顺序与物理存储顺序是保持一致的，而且支持随机存取。因此顺序表在查找、读取时性能很好。
链表：链表采用链式结构来保存表内元素，因此在插入、删除元素时性能要好
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://www.cnblogs.com/ECJTUACM-873284962/p/7485590.html
