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

2018-07-20 05:50:05来源：博客园阅读 ()

一.单向链表（递归）

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