数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，是组织并存储数据以便能够有效使用的一种专门格式，用来反映一个数据的内部构成
数据之间有3种基本结构
线性结构 数据元素之间为一对一关系
树形结构 数据元素之间为一对多关系
网状结构(图状) 数据元素之间为多对多关系
线性结构
线性表
线性表是零个或多个数据元素的有限序列
线性表根据存储结构分为顺序线性表和链式线性表，顺序存储结构和链式存储结构，顺序存储结构的线性表称为顺序表，链式存储的线性表称为链表
线性表数据结构具有以下特征：
存在唯一的”首元素”
存在唯一的”尾元素”
除尾元素外，其余元素均有唯一的后继元素
除首元素外，其余元素均有唯一的前驱元素
顺序表
在内存中用一组地址连续的存储空间顺序存放线性表的各个元素，保证线性表元素逻辑上的有序性。
顺序表是将数据按顺序保存到内存中的，因此在顺序表中存取数据很方便，但是插入和删除数据时，需要移动大量的数据，java中的ArrayList实现原理就是数组
其进行写入和读取数据时，时间复杂度是O(1)，在进行插入和删除操作时，时间复杂度是O(n)
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
|
public class ShunXuBiao<T> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] array;
private int size;
private int length;
public static void main(String[] args) {
ShunXuBiao<Integer> shunXuBiao = new ShunXuBiao<>(2);
System.out.println(shunXuBiao.isEmpty());
shunXuBiao.add(100);
System.out.println(shunXuBiao.size());
shunXuBiao.add(10);
shunXuBiao.print();
shunXuBiao.add(0, 20);
shunXuBiao.print();
shunXuBiao.remove(1);
shunXuBiao.print();
shunXuBiao.clearAll();
shunXuBiao.add(30);
shunXuBiao.print();
}
public void print() {
System.out.println("-------------------");
for (int i = 0; i < size; i++) {
System.out.printf("%s\t", array[i]);
}
System.out.println();
System.out.println("-------------------");
}
public ShunXuBiao(int capacity) {
this.array = new Object[capacity];
this.size = 0;
this.length = capacity;
}
public ShunXuBiao() {
this(DEFAULT_CAPACITY);
}
public void clearAll() {
this.size = 0;
}
public int size() {
return this.size;
}
public void add(T element) {
ensureCapacity();
if (size < array.length) {
array[size] = element;
size++;
} else {
throw new RuntimeException("已超过数组容量");
}
}
public void add(int index, T element) {
ensureCapacity();
if (index < size && size < array.length) {
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = element;
size++;
} else {
throw new RuntimeException("数组下标越界");
}
}
public void ensureCapacity() {
if (size >= length) {
length = length << 1;
array = Arrays.copyOf(array, length);
}
}
public void remove(int index) {
if (index < size) {
for (int i = index; i < size-1; i++) {
array[i] = array[i + 1];
}
array[size - 1] = null;
size--;
}
}
public T get(int index) {
if (index < size) {
return (T) array[index];
}
throw new RuntimeException("数组越界");
}
public boolean isEmpty() {
return size == 0;
}
}
|
优缺点
优点
- 无须为表中元素之间的逻辑关系增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点
- 插入和删除操作需要移动大量元素，且如果没有足够的空间的话，需要将整个数组复制到其他地方
- 线性表长度变化较大时，难以确定存储空间的容量
- 初始过多而根本用不到时，将浪费内存
- 造成存储空间的碎片
链表
链表中数据元素是存储不连续的存储空间，是采用动态存储分配的一种结构，可以根据需要申请内存单元。链表中每个节点都包含两部分，一部分是实际数据，一部分是下一节点的地址，从而使得一系列随机的内存串在一起。操作链表时，需定义一个头指针变量，该变量指向链表的第一个节点，第一个节点又指向第二个节点，直到最后一个节点。最后一个节点不再指向其他节点，称为表尾，在表尾的地址部分放一个NULL，表示空指针，链表到此结束。
单向链表每个节点中只包含一个指针，双向链表每个节点包含两个指针，一个指向上一节点，一个指向下一节点
根据链接方式不同，链表分为单链表、循环链表、双向链表。
单链表
JAVA的LinkedList实现原理就是链表，单向链表实际上是由节点(Node)组成的，一个链表拥有不定数量的节点，数据在内存中存储时不连续，存储的数据分散在内存中，每个节点只能也只有它能知道下一节点的存储位置。由N个Node组成单向链表，每个Node记录该Node的数据和下一个Node。向外暴露的只有一个头节点(Head)
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
| public class LianBiao<E> {
public static void main(String[] args) {
LianBiao<Integer> lianBiao = new LianBiao<>();
lianBiao.addElement(10);
lianBiao.addElement(20);
lianBiao.print();
lianBiao.deleteElement(0);
lianBiao.print();
lianBiao.addElement(30);
lianBiao.print();
lianBiao.addElement(40);
lianBiao.deleteElement(1);
lianBiao.print();
System.out.println(lianBiao.getElement(0));
}
Node<E> head = null;
private int length = 0;
public void addElement(E element) {
Node<E> newNode = new Node<>(element);
if (head == null) {
head = newNode;
} else {
Node<E> temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
length++;
}
public void deleteElement(int index) {
if (index < 0 || index >= length) {
throw new RuntimeException("数组越界，无法删除");
}
if (index == 0) {
head = head.next;
length--;
} else {
int count = 1;
Node<E> preNode = head;
Node<E> curNode = preNode.next;
while (curNode != null) {
if (index == count) {
curNode = curNode.next;
preNode.next = curNode;
length--;
break;
} else {
preNode = curNode;
curNode = curNode.next;
count++;
}
}
}
}
public E getElement(int index) {
if (index < 0 || index > length) {
throw new RuntimeException("数组越界，无法获取");
}
if (index == 0) {
return head.data;
} else {
Node<E> curNode = head;
int count = 0;
while (curNode != null) {
if (count == index) {
return curNode.data;
}
curNode = curNode.next;
count++;
}
}
return null;
}
public void print() {
System.out.println("------------------------");
Node<E> temp = head;
while (temp != null) {
System.out.printf("%s\t", temp.data);
temp = temp.next;
}
System.out.println();
System.out.println("------------------------");
}
private static class Node<E> {
E data;
Node<E> next;
public Node(E data) {
this.data = data;
}
}
}
|
与顺序表对比
- 存储分配方式：顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
- 时间性能：查找时间复杂度，顺序表O(1)，单链表O(n)；插入和删除时间复杂度，顺序表O(n)，单链表O(1)
- 空间性能：顺序存储结构需要预分配存储空间，空间固定，分配过大会导致空间浪费，分配过小会导致数组下标越界；单链表不需要预先分配存储空间，元素个数不受限制
循环链表
对于单链表，每个节点只存储了后继节点，到了尾节点就结束了
而循环链表就是将单链表的尾节点的后继节点指向头节点，使得整个单链表形成一个环
双向链表
在单链表中只有指向next后继节点的指针，双向链表则是在单链表的每个节点上，则设置一个指向前驱节点的指针
优缺点
优点
- 插入数据时不需要进行扩容，且不需要移动后续元素
- 删除数据时也只需要修改前一个元素指向的地址即可
- 内存分散，分配时可以更容易分配
缺点
- 查询最后一个元素时，不能直接读取，因为不知道它所处的地址，需要先访问第一个元素，拿到第二个元素的地址，以此类推直到最后一个
队列
队列是一种特殊的线性表，只允许在表的前端进行删除操作(队头)，在表的后端进行插入操作(队尾)。当队列中没有元素时，称为空队列。先进先出(First In First Out，FIFO)的结构
栈
栈是一种线性表的特殊表现形式，按照后进先出(Last In First Out，LIFO)原则处理数据，仅允许在表的一端进行插入和删除操作，该操作端称为栈顶，另一端称为栈底。
基本操作：
- 入栈(Push) 将数据保存到栈顶。进行该操作时，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置
- 出栈(Pop) 将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素