Java-链表
1、什么是链表？
2、链表的特点是什么？
3、链表的实现原理？
4、如何自己写出一个链表？
1、什么是链表？
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
每一个链表都包含多个节点，节点又包含两个部分，一个是数据域(储存节点含有的信息)，一个是引用域(储存下一个节点或者上一个节点的地址)。
链表的理解示意图
2、链表的特点是什么？
获取数据麻烦，需要遍历查找，比数组慢
方便插入、删除
3、链表的实现原理
创建一个节点类，其中节点类包含两个部分，第一个是数据域(你到时候要往节点里面储存的信息)，第二个是引用域(相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点)
创建一个链表类，其中链表类包含三个属性：头结点、尾节点和大小，方法包含添加、删除、插入等等方法。
单向链表的节点类：
1 public class Node {
2 public Object data;
3 public Node next;
4
5 public Node(Object e){
6 this.data = e;
7 }
8 }
双向链表的节点类：
1 public class Node {
2 public Object e;
3 public Node next;
4 public Node pre;
5 public Node(){
6
7 }
8 public Node(Object e){
9 this.e = e;
10 next = null;
11 pre = null;
12 }
13 }
4、如何自己写出一个链表？
代码如下(以双向链表为例，有详细的注释，单向链表同理)：
首先创建了一个节点类
1 package MutuLink;
2
3 public class Node {
4 public Object e;
5 public Node next;
6 public Node pre;
7 public Node(){
8
9 }
10 public Node(Object e){
11 this.e = e;
12 next = null;
13 pre = null;
14 }
15 }
然后创建了一个链表类
1 package MutuLink;
2
3 public class MyList {
4 private Node head;
5 private Node tail;
6 private int size = 0;
7
8 public MyList() {
9 head = new Node();
10 tail = new Node();
11 head.next =null;
12 tail.pre = null;
13 }
14
15 public boolean empty() {
16 if (head.next == null)
17 return true;
18 return false;
19 }
20 //找到所找下标节点的前一个节点
21 public Node findpre(int index){
22 Node rnode = head;
23 int dex = -1;
24 while(rnode.next != null){
25 //找到了插入节点的上一个节点
26 if( dex== index - 1){
27 return rnode;
28 }
29 rnode = rnode.next;
30 dex++;
31 }
32 return null;
33 }
34 public Node findthis(int index){
35 Node rnode = head;
36 //把rnode想象为指针，dex为指向的下标，这个地方很容易错，因为当指向最后一个节点时没有判断IF就跳出循环了
37 int dex = -1;
38 while(rnode.next != null){
39 if(dex == index)
40 return rnode;
41 rnode = rnode.next;
42 dex++;
43 }
44 if(dex == size - 1){
45 return rnode;
46 }
47 // Node test = new Node(new Students("haha",1,2));
48 return null;
49 }
50
51 // 往链表末尾加入节点
52 public void add(Object e) {
53 Node node = new Node(e);
54 Node rnode = head;
55 //如果是空链表的话插入一个节点，这个节点的pre不能指向上一个节点，必须指空
56 if (this.empty()) {
57 rnode.next = node;
58 rnode.next.pre = null;
59 tail.pre = node;
60 size++;
61 } else {
62 while (rnode.next != null)
63 rnode = rnode.next;
64 rnode.next = node;
65 node.pre = rnode;
66 tail.pre = node;
67 size++;
68 }
69 }
70 //往链表的某一个标插入一个节点
71 public boolean add(int index,Object e){
72 if(index <0||index>=size)
73 return false;
74 Node node = new Node(e);
75 Node prenode = this.findpre(index);
76 node.next = prenode.next;
77 prenode.next.pre = node;
78 prenode.next = node;
79 node.pre = prenode;
80 size++;
81 return true;
82 }
83 public boolean add(int index,MyList myl){
84 if(index <0 || index >= size)
85 return false;
86 Node prenode = this.findpre(index);
87 // myl.tail.pre.next = prenode.next;
88 // prenode.pre = myl.tail.pre;
89 // tail.pre = null;
90 // prenode.next = myl.head.next;
91 // myl.head.next.pre = prenode;
92 // head.next = null;
93 myl.tail.pre.next = prenode.next;
94 prenode.next.pre = myl.tail.pre.pre;
95 myl.head.next.pre = prenode.pre;
96 prenode.next = myl.head.next;
97 myl.head = null;
98 myl.tail = null;
99 size+=myl.size;
100 return true;
101 }
102
103 public Object remove(int index){
104 Object ob= this.get(index);
105 if(index <0 || index >= size)
106 return null;
107 //特殊情况，当移除节点是最后一个节点的时候
108 //较为复杂通过画图来写代码
109 if(index == size - 1){
110 Node prenode = this.findpre(index);
111 this.tail.pre = this.tail.pre.pre;
112 this.tail.pre.next.pre = null;
113 this.tail.pre.next =null;
114 size--;
115 return ob;
116 }
117 //比较复杂，通过画图解决
118 else{
119 Node prenode = this.findpre(index);
120 prenode.next = prenode.next.next;
121 prenode.next.pre.next = null;
122 prenode.next.pre = prenode.next.pre.pre;
123 size--;
124 return ob;
125 }
126 }
127
128
129 public Object get(int index){
130 Node thisnode = this.findthis(index);
131 return thisnode.e;
132 }
133 public int size(){
134 return size;
135 }
136 }
最后测试
1 package MutuLink;
2
3 import java.util.Random;
4
5 public class manage {
6 public static void main(String[] args) {
7 String name = "";
8 int credit;
9 int age;
10 int size;
11 MyList myl = new MyList();
12 Random random = new Random();
13 size = random.nextInt(5) + 1;
14 for (int i = 0; i < size; i++) {
15 credit = random.nextInt(5);
16 age = random.nextInt(5) + 18;
17 for (int j = 0; j < 4; j++) {
18 name += (char) (random.nextInt(26) + 97);
19 }
20 Students stu = new Students(name, credit, age);
21 myl.add(stu);
22 name = "";
23 }
24
25 System.out.println("Size of myl1 is "+ myl.size());
26 for(int i = 0; i < myl.size() ;i++){
27 Students stu2 = (Students) myl.get(i);
28 stu2.show();
29 }
30 // //测试能否在链表末尾加入节点(成功)
31 // for(int i = 0; i < myl.size() ;i++){
32 // Students stu2 = (Students) myl.get(i);
33 // stu2.show();
34 // }
35 // //测试能否通过下标加入一个节点(成功)
36 // Students stu3 = new Students("cyt",5,18);
37 // myl.add(1, stu3);
38 // System.out.println("Size is "+ myl.size());
39 // for(int i = 0; i < myl.size() ;i++){
40 // Students stu2 = (Students) myl.get(i);
41 // stu2.show();
42 // }
43
44 MyList myl2 = new MyList();
45 size = random.nextInt(5) + 1;
46 for (int i = 0; i < size; i++) {
47 credit = random.nextInt(5);
48 age = random.nextInt(5) + 18;
49 for (int j = 0; j < 4; j++) {
50 name += (char) (random.nextInt(26) + 97);
51 }
52 Students stu2 = new Students(name, credit, age);
53 myl2.add(stu2);
54 name = "";
55 }
56 System.out.println("Size is of myl2 "+ myl2.size());
57 for(int i = 0; i < myl2.size() ;i++){
58 Students stu2 = (Students) myl2.get(i);
59 stu2.show();
60 }
61
62
63
64 myl.add(1, myl2);
65 System.out.println("Size is of myl1 "+ myl.size());
66 for(int i = 0; i < myl.size() ;i++){
67 Students stu2 = (Students) myl.get(i);
68 stu2.show();
69 }
70
71
72 }
73
74 }
结果输出：
