数据结构Java实现----链表

一.单向链表（递归）

MyLinkList类

  1 package List;
  2 
  3 // 单向链表
  4 public class MyLinkList {
  5     private Node root; // 根结点
  6     private int size; // 结点个数
  7     private int index; // 脚标
  8     private Object[] reData; // 保存数据的数组
  9 
 10     // 构造方法
 11     public MyLinkList() {
 12         this.root = new Node("head");
 13         System.out.println("创建了带头指针的链表");
 14     }
 15 
 16     public MyLinkList(Object data) {
 17         if (data == null)
 18             System.out.println("参数错误");
 19         this.root = new Node(data);
 20         this.size++;
 21         System.out.println("创建成功" + data);
 22     }
 23 
 24     // 是否是空表
 25     public boolean isEmpty() {
 26         return this.size == 0;
 27     }
 28 
 29     // 返回长度
 30     public int size() {
 31         return this.size;
 32     }
 33     
 34     // 清空链表
 35     public void clear(){
 36         this.root = null;
 37         this.size = 0;
 38     }
 39 
 40     // 判断两个链表是否相等
 41     public boolean equals(Object obj){
 42         // 常规判断
 43         if(obj == null)
 44             return false;
 45         if(obj == this)
 46             return true;
 47         
 48         // 是MyLinkList类
 49         if(obj instanceof MyLinkList){
 50             MyLinkList linkList = (MyLinkList)obj;
 51             
 52             // 根结点相同
 53             if(!this.root.data.equals(linkList.root.data)){
 54                 System.out.println("根节点不相同");
 55                 return false;
 56             }
 57             // 长度相同
 58             if(this.size != linkList.size) {
 59                 System.out.println("长度不同");
 60                 return false;
 61             }
 62             
 63             // 各个结点相同
 64             if(this.size==1){ // 只含有根结点
 65                 return true;
 66             }
 67             return this.root.next.equals(linkList.root.next);
 68         }
 69         
 70         // 不是MyLinkList类
 71         return false;
 72             
 73     }
 74 
 75     // 添加单个数据
 76     public boolean addData(Object data) {
 77         if (data == null) {
 78             System.out.println("参数错误");
 79             return false;
 80         }
 81 
 82         // 把data封装成带指针域的结点
 83         Node node = new Node(data);
 84 
 85         if (this.root.next == null)
 86             this.root.next = node;
 87         else
 88             this.root.next.addNode(node);
 89         System.out.println("添加成功" + data);
 90         this.size++;
 91         return true;
 92     }
 93 
 94     // 添加多个数据
 95     public boolean addDatas(Object[] datas) {
 96         if (datas == null) {
 97             System.out.println("参数错误");
 98             return false;
 99         }
100 
101         // 循环添加结点
102         for (int index = 0; index < datas.length; ++index) {
103             Node data = new Node(datas[index]);// 封装结点
104             this.root.addNode(data);
105             this.size++;
106         }
107         return true;
108     }
109 
110     // 查找数据是否存在
111     public boolean contains(Object data) {
112         if (data == null || this.isEmpty())
113             return false;
114         return this.root.containsNode(data);
115     }
116 
117     // 查找指定位置下的数据
118     public Object get(int index) {
119         // 参数错误
120         if (this.isEmpty() || index < 0 || index > this.size)
121             return null;
122 
123         if (this.root.data.equals("head")) { // 带头指针
124             if (index == 1) // 返回第一个有效数据
125                 return this.root.next.data;
126             else {
127                 this.index = 0;
128                 return this.root.next.getNode(index);
129             }
130         } else { // 不带头指针
131             if (index == 1) // 返回第一个有效数据
132                 return this.root.data;
133             else {
134                 this.index = 1;
135                 return this.root.next.getNode(index);
136             }
137 
138         }
139     }
140 
141     // 删除数据
142     public boolean deleteData(Object data) {
143         if (data == null || this.isEmpty()) {
144             return false;
145         }
146         // 是根结点
147         if (this.root.data.equals(data)) {
148             this.root = this.root.next;
149             this.size--;
150             return true;
151         }
152 
153         // 不是根节点
154         else
155             return this.root.deleteNode(data);
156     }
157 
158     // 打印所有数据
159     public void print() {
160         if (this.isEmpty())
161             System.out.print("空表--------");
162         else
163             this.root.printNode();
164         System.out.println("");
165     }
166 
167     // 返回数组数据
168     public Object[] toArray() {
169         if (this.isEmpty())
170             return null;
171 
172         // 数组保存
173         this.index = 0; // 数组下标
174         if (this.root.data.equals("head")) // 链表带头指针
175             reData = new Object[++this.size];
176         else
177             reData = new Object[this.size];
178         this.root.toArray();
179         return reData;
180     }
181 
182     // 结点类（内部）
183     class Node {
184         Object data; // 数据域
185         Node next; // 指针域
186 
187         // 构造方法
188         public Node(Object data) {
189             this.data = data;
190         }
191 
192         // 添加结点
193         public void addNode(Node node) {
194             if (this.next == null)
195                 this.next = node;
196             else
197                 this.next.addNode(node);
198         }
199 
200         // 打印结点数据
201         public void printNode() {
202             System.out.print(this.data + " ");
203             if (this.next != null)
204                 this.next.printNode();
205         }
206 
207         // 删除结点
208         public boolean deleteNode(Object data) {
209             if (this.next == null) {
210                 System.out.println("删除失败" + data);
211                 return false;
212             }
213             if (this.next.data.equals(data)) {
214                 System.out.println("删除成功" + this.next.data);
215                 MyLinkList.this.size--;
216                 this.next = this.next.next;
217                 return true;
218             }
219             return this.next.deleteNode(data);
220         }
221 
222         // 返回数组
223         public void toArray() {
224             MyLinkList.this.reData[MyLinkList.this.index++] = this.data;
225             if (this.next != null)
226                 this.next.toArray();
227         }
228 
229         // 查找指定结点
230         public Object getNode(int index) {
231             if (++MyLinkList.this.index == index)
232                 return this.data;
233             return this.next.getNode(index);
234         }
235 
236         // 查找结点
237         public boolean containsNode(Object data) {
238             if (this.data == data)
239                 return true;
240             if (this.next != null)
241                 return this.next.containsNode(data);
242             return false;
243         }
244         
245         // 重写equals()
246         public boolean equals(Node node){
247             // 数据域是否相同
248             if(!this.data.equals(node.data)) {
249                 System.out.println("数据域不同this:"+this.data+" linkList:"+node.data);
250                 return false;
251             }
252             // 还有下个结点
253             if(this.next!=null)
254                 return this.next.equals(node.next);
255             // 没有下个结点且到目前为止所有结点数据域相同
256             return true;
257             
258         }
259     }
260 }

MyLinkList

TestMyLinkList类

 1 package List;
 2 
 3 // 单向链表测试
 4 public class TestMyLinkList {
 5 
 6     public static void main(String[] args) {
 7         // 创建一个链表
 8         MyLinkList linkList = new MyLinkList(5);
 9 
10         // 初始化一个链表
11         for (int index = 1; index < 10; ++index) {
12             int num = (int) (Math.random() * 11);
13             linkList.addData(num);
14         }
15 
16         // 打印链表的所有数据
17         linkList.print();
18 
19         // 删除结点
20         linkList.deleteData(5);
21         linkList.print();
22         linkList.deleteData(10);
23         linkList.print();
24 
25         System.out.println("第2个结点数据:" + linkList.get(2));
26         // 数组化
27         Object[] data = new Object[linkList.size()];
28         data = linkList.toArray();
29         for (Object index : data)
30             System.out.print(index + " ");
31         System.out.println("");
32         System.out.println("-------------------");
33         // 创建一个链表
34         MyLinkList linkList2 = new MyLinkList();
35 
36         // 待添加数据的数组
37         Object[] datas = { 5, "123", 26 };
38         linkList2.addDatas(datas);
39         System.out.println("包含'5'吗" + linkList2.contains(5));
40         linkList2.print();
41         System.out.println("----------------------------");
42         // 创建一个链表
43         MyLinkList linkList1 = new MyLinkList();
44         linkList1.addDatas(datas);
45         linkList1.print();
46         System.out.println("是否相等"+linkList2.equals(linkList1));
47     }
48 
49 }

TestMyLinkList

打印

 1 添加成功5
 2 添加成功1
 3 添加成功6
 4 添加成功6
 5 添加成功6
 6 添加成功1
 7 添加成功5
 8 添加成功2
 9 添加成功10
10 5 5 1 6 6 6 1 5 2 10 
11 5 1 6 6 6 1 5 2 10 
12 删除成功10
13 5 1 6 6 6 1 5 2 
14 第2个结点数据:1
15 5 1 6 6 6 1 5 2 
16 -------------------
17 包含'5'吗true
18 head 5 123 26 
19 ----------------------------
20 head 5 123 26 
21 是否相等true

TestMyLinkList-console

总结：1.避免空指针异常(NullPointException):先判断引用是否为null，后使用。

参考:https://www.cnblogs.com/dolphin0520/p/3811445.html

2018-7-19

二、双向链表(循环、头插法)

DoubleLink类

  1 package List;
  2 
  3 // 双向链表（循坏、头插法）
  4 public class DoubleLink {
  5     private Node root; // 表头
  6     private int size; // 长度
  7 
  8     // 结点类
  9     private class Node {
 10         Object data; // 数据域
 11         Node prev; // 前趋
 12         Node next; // 后继
 13 
 14         // 构造方法
 15         public Node(Object data, Node prev, Node next) {
 16             this.data = data;
 17             this.prev = prev;
 18             this.next = next;
 19         }
 20 
 21         public Node(Object data) {
 22             this.data = data;
 23         }
 24     }
 25 
 26     // 构造方法
 27     public DoubleLink() {
 28         this.root = new Node(null, null, null);
 29         this.root.prev = this.root.next = this.root;
 30         this.size = 0;
 31     }
 32 
 33     // 是否是空表
 34     public boolean isEmpty() {
 35         return this.size == 0;
 36     }
 37 
 38     // 返回长度
 39     public int size() {
 40         return this.size;
 41     }
 42 
 43     // 添加数据
 44     public boolean addData(Object data) {
 45         // 空引用
 46         if (data == null)
 47             return false;
 48 
 49         this.size++; // 增加长度
 50         Node node = new Node(data); // 封装结点
 51         // 添加结点
 52 
 53         if (this.isEmpty()) {
 54             this.root.next = node;
 55             this.root.prev = node;
 56 
 57             node.next = this.root;
 58             node.prev = this.root;
 59             return true;
 60         }
 61 
 62         // 头插法
 63         node.next = this.root.next; // 将新结点的后继指向头结点的后继
 64         node.prev = this.root; // 将新结点的前驱指向头结点
 65         this.root.next.prev = node; // 头结点的后继结点的前驱指向新结点
 66         this.root.next = node; // 头结点的后继节点指向新结点
 67         return true;
 68     }
 69 
 70     // 查找第index结点
 71     private Node getNode(int index) {
 72         Node oldNode = this.root;
 73         int foot = 0; // 脚标
 74         if (index <= this.size / 2) { // 正查找
 75             System.out.print("正查");
 76             while (true) {
 77                 if (foot++ == index)
 78                     break;
 79                 oldNode = oldNode.next;
 80             }
 81         } else {
 82             int LIndex = this.size + 1 - index;
 83             System.out.print("反查");
 84             while (true) {
 85                 if (foot++ == LIndex)
 86                     break;
 87                 oldNode = oldNode.prev;
 88             }
 89         }
 90         System.out.print(oldNode.data);
 91         return oldNode;
 92     }
 93 
 94     // 查找结点
 95     private Node getNode(Object data) {
 96         Node oldNode = this.root.next;
 97         while (true) {
 98             if (oldNode.data.equals(data))
 99                 return oldNode;
100             if (oldNode.next.data == null)
101                 return null;
102             oldNode = oldNode.next;
103         }
104 
105     }
106 
107     // 删除结点
108     private void removeNode(Node node) {
109         node.next.prev = node.prev; // 结点的后继结点的前驱指向结点的前驱
110         node.prev.next = node.next; // 结点的前驱结点的后继指向结点的后继
111         node = null;
112     }
113 
114     // 前插法
115     private boolean addNode(Node oldNode, Node newNode) {
116         oldNode.prev.next = newNode;
117         newNode.prev = oldNode.prev;
118         oldNode.prev = newNode;
119         newNode.next = oldNode;
120         return true;
121     }
122 
123     // 在index结点前插入新结点
124     public boolean addData(Object data, int index) {
125         if (data == null)
126             return false;
127         if (index <= 0 || index > this.size)
128             return false;
129 
130         Node newNode = new Node(data); // 封装结点
131 
132         // 查找结点
133         Node oldNode = getNode(index);
134         this.size++; // 增加长度
135         // 更改指针域
136         return addNode(oldNode, newNode);
137     }
138 
139     // 得到第index个结点的数据
140     public Object get(int index) {
141         if (this.isEmpty())
142             return null;
143         if (index <= 0 || index > this.size)
144             return null;
145 
146         // 查找结点
147         return getNode(index).data;
148     }
149 
150     // 查找数据是否存在
151     public boolean contains(Object data) {
152         if (data == null)
153             return false;
154         if (this.isEmpty())
155             return false;
156 
157         // 查找结点
158         if (getNode(data) == null)
159             return false;
160         else
161             return true;
162     }
163 
164     // 删除指定数据
165     public boolean remove(Object data) {
166         if (data == null)
167             return false;
168         if (this.isEmpty())
169             return false;
170 
171         // 查找结点
172         Node node = getNode(data);
173         if (node == null)
174             return false;
175 
176         // 删除结点
177         removeNode(node);
178         this.size--; // 长度减一
179         return true;
180     }
181 
182     // 删除第index个结点
183     public boolean removeIndex(int index) {
184         if (this.isEmpty())
185             return false;
186         if (index <= 0 || index > this.size)
187             return false;
188 
189         // 查找结点
190         Node node = getNode(index);
191         // 删除结点
192         removeNode(node);
193         this.size--; // 长度减一
194         return true;
195     }
196 
197     // equals()
198     public boolean equals(Object obj) {
199         if (obj == null)
200             return false;
201 
202         // 是DoubleLink类
203         if (obj instanceof DoubleLink) {
204             // 对象下转型为DoubleLink类
205             DoubleLink link = (DoubleLink) obj;
206 
207             // 比较长度
208             if (this.size != link.size)
209                 return false;
210 
211             Node thisNode = this.root.next;
212             Node linkNode = link.root.next;
213             // 比较每个结点的后继的数据域是否相同
214             while (true) {
215                 if (thisNode.data == null) // 只有头结点数据域为空
216                     break;
217 
218                 if (!thisNode.data.equals(linkNode.data)) // 结点数据域不相同
219                     return false;
220 
221                 thisNode = thisNode.next;
222                 linkNode = linkNode.next;
223             }
224         }
225         return true;
226     }
227 
228     // 获得所有数据
229     public Object[] toArray() {
230         if (isEmpty())
231             return null;
232 
233         Object[] datas = new Object[this.size];
234         int index = 0; // 数组脚标
235         Node node = this.root.prev; // 当前结点
236         while (true) {
237             if (node.data == null) // 只有头结点数据域为空
238                 break;
239             datas[index++] = node.data;
240             node = node.prev;
241         }
242 
243         return datas;
244     }
245 
246     // 打印信息
247     public void print() {
248         if (isEmpty())
249             System.out.println("空表");
250 
251         else {
252             Node node = this.root.next;
253             while (true) {
254                 if (node.data == null)
255                     break;
256                 System.out.print(node.data + " ");
257                 node = node.next;
258             }
259             System.out.println();
260         }
261     }
262 
263 }

DoubleLink

TestDoubleLink类

 1 package List;
 2 
 3 // 双向链表测试类
 4 public class TestDoubleLink {
 5 
 6     public static void main(String[] args) {
 7         // TODO Auto-generated method stub
 8 
 9         // 初始化一个双向链表
10         DoubleLink link1 = new DoubleLink();
11         link1.print();
12         
13         // 添加数据
14         System.out.println("头插法添加10 5 12 null");
15         System.out.print("添加结果:"+link1.addData(10)+" ");
16         System.out.print(link1.addData(5)+" ");
17         System.out.print(link1.addData(12)+" ");
18         System.out.println(link1.addData(null));
19         link1.print();
20         
21         // 在指定位置前插入数据
22         System.out.println("
在第2为前插入一个40，在第4位前插入一个50");
23         System.out.println("插入结果："+link1.addData(40, 2)+"  "+link1.addData(50,4));
24         link1.print();
25         
26         // 检查是否指定数据
27         System.out.println("
检查是否含有数据:50 30");
28         System.out.println("检查结果:"+link1.contains(50)+"  "+link1.contains(30));
29         link1.print();
30         
31         // 删除指定数据
32         System.out.println("
删除指定数据:50 0");
33         System.out.println("删除结果:"+link1.remove(50)+" "+link1.remove(0));
34         link1.print();
35         
36         // 删除指定位置上的数据
37         System.out.println("
删除指定位置上的数据:第3位 第10位");
38         System.out.println("删除结果:"+link1.removeIndex(3)+" "+link1.removeIndex(10));
39         link1.print();
40         
41         
42         // 比较两个链表是否相同
43         DoubleLink link2 = new DoubleLink();
44         DoubleLink link3 = new DoubleLink();
45         link2.addData(10);
46         link2.addData(40);
47         link2.addData(12);
48         link3.addData(12);
49         link3.addData(40);
50         link3.addData(10);
51         System.out.println("
比较两个链表是否相同");
52         System.out.print("link1:");
53         link1.print();
54         System.out.print("link2:");
55         link2.print();
56         System.out.print("link3:");
57         link3.print();
58         System.out.println("link1和link2： "+link1.equals(link2)+"
link1和link3："+link1.equals(link3)+"
link1和null："+link1.equals(null));
59 
60     }
61 
62 }

TestDoubleLink

打印

 1 空表
 2 头插法添加10 5 12 null
 3 添加结果:true true true false
 4 12 5 10 
 5 
 6 在第2为前插入一个40，在第4位前插入一个50
 7 反查反查插入结果：true  true
 8 12 40 5 50 10 
 9 
10 检查是否含有数据:50 30
11 检查结果:true  false
12 12 40 5 50 10 
13 
14 删除指定数据:50 0
15 删除结果:true false
16 12 40 5 10 
17 
18 删除指定位置上的数据:第3位 第10位
19 反查删除结果:true false
20 12 40 10 
21 
22 比较两个链表是否相同
23 link1:12 40 10 
24 link2:12 40 10 
25 link3:10 40 12 
26 link1和link2： true
27 link1和link3：false
28 link1和null：false

TestDoubleLink-console

总结:1.避免查找错误：先执行查找函数，再改变链表长度。

参考:https://www.cnblogs.com/skywang12345/p/3561803.html

2018-7-20