网站建设常用工具,二手书交易网站开发与设计,学生登录入口,查看网站被恶意镜像说明#xff1a;由于该数据结构是由java并且是原生实现#xff0c;所以与C有一些出入#xff0c;不过原理是相同的 1.链表的定义 为了表示线性表元素a与a1的逻辑关系#xff0c;存储数据时#xff0c;除了存储元素本身的信息之外#xff0c;还存储了直接后继元素的位置信…说明由于该数据结构是由java并且是原生实现所以与C有一些出入不过原理是相同的 1.链表的定义 为了表示线性表元素a与a1的逻辑关系存储数据时除了存储元素本身的信息之外还存储了直接后继元素的位置信息。这两部分组成的数据元素被称为“结点”一个结点分为两部分存放数据元素信息的部分被称为数据域 存放直接后继元素位置的部分被称为指针域。 单链表结点指针域只存放直接后继元素位置的链表也叫单向链表。 双链表结点指针域同时存放前驱元素和后继元素位置的链表也叫双向链表。 循环链表一般的链表尾结点最后一个结点的指针域一般null但是有的链表将最后一个节点的指针域指向头结点构成一个环称作循环链表。 头结点 一个链表的头节点就是指针域指向该链表的第一个结点的结点一般用来唯一确定一个链表也有的链表是不带头结点的那时我们通过链表的第一个结点来确定链表注意头结点的数据与是null 2.实现原理 链表的每一个结点包括两部分数据域和指针域数据域用来存储数据指针域用来存储后继结点的位置。 1 class LinkT{2 /**3 *用来存储数据4 */5 T data;6 /**7 *用来存储下一结点位置8 */9 Link next;
10 } 3.链表的基本操作 1.初始化 init() 创建一个链表 2.清空 clear() 清空一个链表 3.销毁 destroy() 销毁链表 4.在头部插入一个结点 insertFront() 5.在尾部插入一个结点 insertBackend() 6.在任意位置插入一个结点 insertIndex() 7.删除任意位置元素 delete() 8.查找元素 find() 9.获取指定位置节点的值 get() 4.代码实现 4.1链表代码实现 1 package com.xiaobai.linelist;2 3 /**4 * Author: xiaobai5 * Date: 2019/5/1 9:006 * email:7 * address:8 * desc 模拟单链表操作9 * Version 1.010 */11 SuppressWarnings(ALL)12 public final class LinkT {13 /**14 * data 是要存储的数据15 */16 private T data;17 /**18 * next是下一结点的引用位置19 */20 public LinkT next;21 22 /**23 * 初始化操作 构造方法返回一个空结点24 */25 public Link(){26 this.next null;27 this.data null;28 }29 30 /**31 * 构造一个新的链表结点32 * 新结点是没有后继结点的 所以直接null33 * param data 数据34 */35 public Link(T data){36 this.data data;37 this.next null;38 }39 40 /**41 * 清空链表操作42 * param link 要被清空的链表头节点43 */44 public void clear(){45 //让每一个结点的引用都为 null GC 自动回收46 LinkT link this;47 while(link.next!null){48 Link curr link.next;49 link.next link.next.next;50 curr null;51 }52 link null;53 }54 55 /**56 * 销毁链表 这里的销毁和清空我认为没有什么区别所以直接调用57 * 如果大家认为有区别的话可以与我交流58 * param link 被销毁的链表59 */60 public void destroy(){61 this.clear();62 }63 64 /**65 * 在链表的头部插入一个结点默认是带头结点的链表66 * param head 链表的头节点67 * param data 被插入的数据68 * return 插入结果69 */70 public boolean insertFront(T data){71 //先构建一个新的结点72 LinkT node new LinkT(data);73 try {74 //将结点插入到头部 即 新节点后继指向原来的第一个结点 头节点后继指向新节点75 node.next this.next;76 this.next node;77 return true;78 }catch (Exception e){79 e.printStackTrace();80 return false;81 }82 }83 84 /**85 * 在链表的尾部插入一个结点86 * param head 链表头节点87 * param data 要插入的数据88 * return 插入结果89 */90 public boolean insertBackend(T data){91 //先构建一个新的结点92 try {93 LinkT node new LinkT(data);94 //然后找到链表的尾95 LinkT point this.next;96 while(point.next!null){97 point point.next;98 }99 //插入
100 point.next node;
101 return true;
102 } catch (Exception e) {
103 e.printStackTrace();
104 return false;
105 }
106 }
107
108 /**
109 * 在任意位置插入一个结点
110 * param head 要插入的链表
111 * param i 插入位置 从0开始
112 * param data 插入的数据
113 * return 插入结果
114 */
115 public boolean insertIndex(int i,T data){
116 Link curr this.next;
117 //空链表 拒绝插入
118 if(null curr i 0){
119 return false;
120 }
121 int count 0;
122 //找到被插入的位置要找被插入位置前一个
123 while(count ! i-1 null ! curr){
124 curr curr.next;
125 count ;
126 }
127 //如果循环提前结束 说明i值过大
128 if(count ! i-1){
129 return false;
130 }
131 //开始插入节点
132 LinkT node new LinkT(data);
133 node.next curr.next;
134 curr.next node;
135 return true;
136 }
137
138 /**
139 * 删除任意位置元素
140 * param i 被删除的位置 从0 开始
141 * return 被删除的元素 删除失败返回null
142 */
143 public T delete(int i){
144 T del null;
145 int count 0;
146 LinkT curr this.next;
147 //找到被删除结点的前一个结点
148 while (curr ! null count i-1){
149 curr curr.next;
150 count;
151 }
152 //如果不满足条件 删除失败
153 if(count!i-1){
154 return del;
155 }
156 //如果找到 执行删除操作 GC 自动释放
157 del curr.next.data;
158 curr.next curr.next.next;
159 return del;
160 }
161
162 /**
163 * 查找元素是否存在 可能需要重写存储对象的equals方法
164 * param data 被查找元素
165 * return 查找结果
166 */
167 public boolean find(T data){
168 Link curr this.next;
169 while(curr ! null){
170 if(curr.data.equals(data)||curr.data data){
171 return true;
172 }
173 curr curr.next;
174 }
175 return false;
176 }
177
178 /**
179 * 获取指定位置的元素
180 * param i 位置
181 * return 获取到的值 没有返回null
182 */
183 public T get(int i) {
184 T data null;
185 LinkT curr this.next;
186 int count 0;
187 while(count!i curr!null){
188 curr curr.next;
189 count ;
190 }
191 if(count i curr! null){
192 data curr.data;
193 }
194 return data;
195 }
196
197 Override
198 public String toString() {
199 StringBuilder sb new StringBuilder().append(HashCode this.hashCode()).append( {head - );
200 LinkT curr this.next;
201 while (curr!null){
202 sb.append(curr.data - );
203 curr curr.next;
204 }
205 sb.append( null});
206 return sb.toString();
207 }
208 } 4.2 测试代码及结果 1 /**2 * Author: xiaobai3 * Date: 2019/5/1 9:424 * email: 5 * address:6 * Version 1.07 */8 public class TestLink {9 public static void main(String[] args) {
10 System.out.println(初始化链表);
11 LinkInteger link new Link();
12 System.out.println(当前链表: link);
13
14 System.out.println(在前端插入一个元素 5);
15 link.insertFront(5);
16 System.out.println(当前链表: link);
17
18 for(int i1;i10;i){
19 link.insertBackend(i);
20 }
21 System.out.println(依次从后端继续插入10个数后 link);
22
23 link.insertIndex(3,100);
24 //索引从0开始
25 System.out.println(在第三个位置上插入100以后的链表 link);
26
27 System.out.println(在第100个位置上插入0 link.insertIndex(100,0));
28
29 System.out.println(删除第三个位置上的元素link.delete(3));
30 System.out.println(link);
31
32 System.out.println(查找元素10的结果link.find(10));
33 System.out.println(查找元素100的结果link.find(100));
34
35 System.out.println(获取第3个结点的值 link.get(3));
36 System.out.println(获取第999个结点的值 link.get(999));
37
38 link.clear();
39 System.out.println(执行清空操作后的链表 link);
40
41 link.destroy();
42
43 }
44 } 运行结果图 转载于:https://www.cnblogs.com/xiaobai1202/p/10799114.html
