Java学习路线-13:链表定义与实现

举报
彭世瑜 发表于 2021/08/13 23:10:20 2021/08/13
【摘要】 第30 章 : 链表的定义与使用 134 链表实现简介 链表本质是一个动态的对象数组,它可以实现若干个对象的存储 链表利用引用的逻辑关系来实现类似于数组的数据处理操作 实现链表,需要一个公共结构-节点: 1、保存数据 2、连接下一个结构 Node<E> -E data -next 123 还需要一个管理Node节点的类 客户端:数据的增删改查 ...

第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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。