Java学习路线-13:链表定义与实现
第30 章 : 链表的定义与使用
134 链表实现简介
链表本质是一个动态的对象数组,它可以实现若干个对象的存储
链表利用引用的逻辑关系来实现类似于数组的数据处理操作
实现链表,需要一个公共结构-节点:
1、保存数据
2、连接下一个结构
Node<E>
-E data
-next
- 1
- 2
- 3
还需要一个管理Node节点的类
客户端:数据的增删改查
链表LinkImpl:处理Node细节 -> ILink<T>
Node:存储数据
- 1
- 2
- 3
private class Node<T>{ private T data; // 数据 private Node<T> nextNode; // 下一节点 public Node(T data){ this.data = data ; } public void setNextNode(Node<T> nextNode){ this.nextNode = nextNode ; } public Node<T> getNextNode(){ return this.nextNode ; } public T getData(){ return this.data; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
简单的单向链表实现
135 数据增加
public void add(E e);
- 1
136 获取数据集合个数
public int size();
- 1
137 空集合判断
public boolean isEmpty();
- 1
138 返回集合数据
public Object[] toArray();
- 1
139 根据索引取得数据
public E get(int index);
- 1
数组获取数据的时间复杂度为1
链表获取数据的时间复杂度为n
140 修改链表指定索引数据
public void set(int index, E data);
- 1
141 判断链表数据是否存在
public boolean contains(E data);
- 1
142 删除链表数据
public void remove(E data);
- 1
两种情况
删除根节点数据
删除非根节点数据
引用修改
143 清空链表
public void clean();
- 1
只用设置头节点为空即可
完整代码
// 定义链表的接口
interface ILink<E>{ public void add(E e); // 添加元素 public int size(); // 获取元素个数 public boolean isEmpty(); // 判断是否为空 public Object[] toArray(); //转为对象数组 public E get(int index); // 根据索引取得数据 public void set(int index, E data); //修改数据 public boolean contains(E data); // 判断数据是否存在 public boolean remove(E data); // 链表数据 public void clean(); // 清空链表
}
// 实现链表
class LinkImpl<T> implements ILink<T>{ private Node<T> rootNode; // 记录头指针 private int count ; // 计数统计 private Object[] dataList; // 数据列表 private int foot; //角标 // 链表节点,内部类,便于外部类直接访问其私有属性 private class Node<T>{ private T data; // 数据 private Node<T> nextNode; // 下一节点 public Node(T data){ this.data = data ; } public void addNode(Node<T> node){ if(!this.hasNextNode()){ this.nextNode = node; } else{ this.nextNode.addNode(node); } } public boolean hasNextNode(){ return this.nextNode != null; } public void toArrayNode(){ LinkImpl.this.dataList[LinkImpl.this.foot++] = this.data; if(this.hasNextNode()){ this.nextNode.toArrayNode(); } } public Node<T> getNode(int index){ if(LinkImpl.this.foot++ == index){ return this ; }else{ return this.nextNode.getNode(index); } } public boolean containsNode(T data){ // 比较对象 不能是null if(this.data.equals(data)){ return true; } else { // 有后续节点继续 if(this.hasNextNode()){ return this.nextNode.containsNode(data); } else { // 没有找到数据 return false; } } } public boolean removeNode(Node<T> preNode, T data){ if(this.data.equals(data)){ preNode.nextNode = this.nextNode; return true; } else { // 有后续节点,继续移除操作 if(this.hasNextNode()){ return this.nextNode.removeNode(this, data); } else{ return false; } } } } public void add(T data){ // 不接受null 类型的值 if(!isValidData(data)){ return; } Node<T> newNode = new Node<T>(data); // 添加第一个元素的时候,头节点为null if (this.count == 0){ this.rootNode = newNode; } else { this.rootNode.addNode(newNode); } this.count++; } public int size(){ return this.count; } public boolean isEmpty(){ return this.count == 0; } public Object[] toArray(){ if(this.isEmpty()){ return null; } // 角标清零,创建空数组 this.foot = 0; this.dataList = new Object[this.count]; // 递归获取节点数据 this.rootNode.toArrayNode(); return this.dataList; } // 检查索引是否在有效范围内 private boolean isValidIndex(int index){ if(index < 0 || index >= count){ return false; } else{ return true; } } // 检查是否为有效数据 private boolean isValidData(T data){ if(data == null){ return false; } else{ return true; } } public T get(int index){ if(!this.isValidIndex(index) || this.isEmpty()){ return null ; } // 重置下标 this.foot = 0; return this.rootNode.getNode(index).data; } public void set(int index, T data){ if(!this.isValidIndex(index) || this.isEmpty() ){ return ; } // 重置下标 this.foot = 0; this.rootNode.getNode(index).data = data; } public boolean contains(T data){ if(!isValidData(data) || this.isEmpty()){ return false; } return this.rootNode.containsNode(data); } public boolean remove(T data){ if(!isValidData(data) || this.isEmpty()){ return false; } boolean removeResult = false; // 移除头节点 if(this.rootNode.data.equals(data)){ this.rootNode = this.rootNode.nextNode; removeResult = true; } else{ removeResult = this.rootNode.nextNode.removeNode(this.rootNode, data); } if(removeResult == true){ this.count --; } return removeResult; } public void clean(){ this.rootNode = null; this.count = 0; } public void printLink(){ Object[] list = this.toArray(); if (list == null){ System.out.println("null"); return; } for(int i=0; i < this.count; i++){ if(i == 0){ System.out.print("[ "); } else { System.out.print("-> "); } System.out.print(list[i]); if (i == count - 1){ System.out.print(" ]"); } } System.out.println(); }
}
class Demo{ public static void main(String[] args) { LinkImpl<Integer> link = new LinkImpl<Integer>(); System.out.println("添加前:" + link.size() + " " + link.isEmpty()); // 添加前:0 true link.add(2); link.add(3); link.add(4); link.add(5); System.out.println("添加后:" + link.size() + " " + link.isEmpty()); // 添加后:4 false link.printLink(); // [ 2-> 3-> 4-> 5 ] System.out.println(link.get(2)); // 4 link.set(2, 6); System.out.println(link.get(2)); // 6 System.out.println(link.contains(10)); // false System.out.println(link.contains(5)); // true link.printLink(); // [ 2-> 3-> 6-> 5 ] link.remove(2); System.out.println(link.contains(2)); link.printLink(); // [ 3-> 6-> 5 ] link.clean(); link.printLink(); // null }
}
- 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
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
144 综合实战:宠物商店
要求
宠物上架,下架,查询宠物信息
设计
宠物接口
-猫
-狗
宠物链表接口
-宠物链表
宠物商店
-宠物列表
根据接口标准定义信息
145 综合实战:超市购物车
类与标准有关,降低类与类之间耦合
146 Eclipse简介
Eclipse 中文意思:日蚀
开发工具 + 操作系统 + 中间件 + 数据库
Eclipse EE + Linux + Tomcat + MySQL
https://www.eclipse.org/downloads/
147 使用JDT开发Java程序
项目目录
src *.java
bin *.class
- 1
- 2
UTF-8编码
快捷方式:
自动导包
代码格式化
代码纠正提示
代码提示
复制当前行
单行注释
代码自动生成
148 代码调试
断点break point
单步跳入 进入代码
单步跳过 直接到结果
单步返回 进入之后直接返回
恢复执行 取消断点,程序正常执行
149 junit测试工具
白盒测试
黑盒测试
用例测试 junit
testCase 一个测试
testSuite 一组测试
文章来源: pengshiyu.blog.csdn.net,作者:彭世瑜,版权归原作者所有,如需转载,请联系作者。
原文链接:pengshiyu.blog.csdn.net/article/details/102988061
- 点赞
- 收藏
- 关注作者
评论(0)