java单链表和双_Java链表，单链表和双链表

Java-链表

1、什么是链表&＃xff1f;

2、链表的特点是什么&＃xff1f;

3、链表的实现原理&＃xff1f;

4、如何自己写出一个链表&＃xff1f;

1、什么是链表&＃xff1f;

链表是一种物理存储单元上非连续、非顺序的存储结构&＃xff0c;数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

每一个链表都包含多个节点&＃xff0c;节点又包含两个部分&＃xff0c;一个是数据域(储存节点含有的信息)&＃xff0c;一个是引用域(储存下一个节点或者上一个节点的地址)。

链表的理解示意图

2、链表的特点是什么&＃xff1f;

获取数据麻烦&＃xff0c;需要遍历查找&＃xff0c;比数组慢

方便插入、删除

3、链表的实现原理

创建一个节点类&＃xff0c;其中节点类包含两个部分&＃xff0c;第一个是数据域(你到时候要往节点里面储存的信息)&＃xff0c;第二个是引用域(相当于指针&＃xff0c;单向链表有一个指针&＃xff0c;指向下一个节点&＃xff1b;双向链表有两个指针&＃xff0c;分别指向下一个和上一个节点)

创建一个链表类&＃xff0c;其中链表类包含三个属性&＃xff1a;头结点、尾节点和大小&＃xff0c;方法包含添加、删除、插入等等方法。

单向链表的节点类&＃xff1a;

1 public class Node {

2 public Object data;

3 public Node next;

4

5 public Node(Object e){

6 this.data &＃61; e;

7 }

8 }

双向链表的节点类&＃xff1a;

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 &＃61; e;

10 next &＃61; null;

11 pre &＃61; null;

12 }

13 }

4、如何自己写出一个链表&＃xff1f;

代码如下(以双向链表为例&＃xff0c;有详细的注释&＃xff0c;单向链表同理)&＃xff1a;

首先创建了一个节点类

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 &＃61; e;

12 next &＃61; null;

13 pre &＃61; null;

14 }

15 }

然后创建了一个链表类

1 package MutuLink;

2

3 public class MyList {

4 private Node head;

5 private Node tail;

6 private int size &＃61; 0;

7

8 public MyList() {

9 head &＃61; new Node();

10 tail &＃61; new Node();

11 head.next &＃61;null;

12 tail.pre &＃61; null;

13 }

14

15 public boolean empty() {

16 if (head.next &＃61;&＃61; null)

17 return true;

18 return false;

19 }

20 //找到所找下标节点的前一个节点

21 public Node findpre(int index){

22 Node rnode &＃61; head;

23 int dex &＃61; -1;

24 while(rnode.next !&＃61; null){

25 //找到了插入节点的上一个节点

26 if( dex&＃61;&＃61; index - 1){

27 return rnode;

28 }

29 rnode &＃61; rnode.next;

30 dex&＃43;&＃43;;

31 }

32 return null;

33 }

34 public Node findthis(int index){

35 Node rnode &＃61; head;

36 //把rnode想象为指针&＃xff0c;dex为指向的下标&＃xff0c;这个地方很容易错&＃xff0c;因为当指向最后一个节点时没有判断IF就跳出循环了

37 int dex &＃61; -1;

38 while(rnode.next !&＃61; null){

39 if(dex &＃61;&＃61; index)

40 return rnode;

41 rnode &＃61; rnode.next;

42 dex&＃43;&＃43;;

43 }

44 if(dex &＃61;&＃61; size - 1){

45 return rnode;

46 }

47 // Node test &＃61; new Node(new Students("haha",1,2));

48 return null;

49 }

50

51 // 往链表末尾加入节点

52 public void add(Object e) {

53 Node node &＃61; new Node(e);

54 Node rnode &＃61; head;

55 //如果是空链表的话插入一个节点&＃xff0c;这个节点的pre不能指向上一个节点&＃xff0c;必须指空

56 if (this.empty()) {

57 rnode.next &＃61; node;

58 rnode.next.pre &＃61; null;

59 tail.pre &＃61; node;

60 size&＃43;&＃43;;

61 } else {

62 while (rnode.next !&＃61; null)

63 rnode &＃61; rnode.next;

64 rnode.next &＃61; node;

65 node.pre &＃61; rnode;

66 tail.pre &＃61; node;

67 size&＃43;&＃43;;

68 }

69 }

70 //往链表的某一个标插入一个节点

71 public boolean add(int index,Object e){

72 if(index <0||index>&＃61;size)

73 return false;

74 Node node &＃61; new Node(e);

75 Node prenode &＃61; this.findpre(index);

76 node.next &＃61; prenode.next;

77 prenode.next.pre &＃61; node;

78 prenode.next &＃61; node;

79 node.pre &＃61; prenode;

80 size&＃43;&＃43;;

81 return true;

82 }

83 public boolean add(int index,MyList myl){

84 if(index <0 || index >&＃61; size)

85 return false;

86 Node prenode &＃61; this.findpre(index);

87 // myl.tail.pre.next &＃61; prenode.next;

88 // prenode.pre &＃61; myl.tail.pre;

89 // tail.pre &＃61; null;

90 // prenode.next &＃61; myl.head.next;

91 // myl.head.next.pre &＃61; prenode;

92 // head.next &＃61; null;

93 myl.tail.pre.next &＃61; prenode.next;

94 prenode.next.pre &＃61; myl.tail.pre.pre;

95 myl.head.next.pre &＃61; prenode.pre;

96 prenode.next &＃61; myl.head.next;

97 myl.head &＃61; null;

98 myl.tail &＃61; null;

99 size&＃43;&＃61;myl.size;

100 return true;

101 }

102

103 public Object remove(int index){

104 Object ob&＃61; this.get(index);

105 if(index <0 || index >&＃61; size)

106 return null;

107 //特殊情况&＃xff0c;当移除节点是最后一个节点的时候

108 //较为复杂通过画图来写代码

109 if(index &＃61;&＃61; size - 1){

110 Node prenode &＃61; this.findpre(index);

111 this.tail.pre &＃61; this.tail.pre.pre;

112 this.tail.pre.next.pre &＃61; null;

113 this.tail.pre.next &＃61;null;

114 size--;

115 return ob;

116 }

117 //比较复杂&＃xff0c;通过画图解决

118 else{

119 Node prenode &＃61; this.findpre(index);

120 prenode.next &＃61; prenode.next.next;

121 prenode.next.pre.next &＃61; null;

122 prenode.next.pre &＃61; prenode.next.pre.pre;

123 size--;

124 return ob;

125 }

126 }

127

128

129 public Object get(int index){

130 Node thisnode &＃61; 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 &＃61; "";

8 int credit;

9 int age;

10 int size;

11 MyList myl &＃61; new MyList();

12 Random random &＃61; new Random();

13 size &＃61; random.nextInt(5) &＃43; 1;

14 for (int i &＃61; 0; i

15 credit &＃61; random.nextInt(5);

16 age &＃61; random.nextInt(5) &＃43; 18;

17 for (int j &＃61; 0; j <4; j&＃43;&＃43;) {

18 name &＃43;&＃61; (char) (random.nextInt(26) &＃43; 97);

19 }

20 Students stu &＃61; new Students(name, credit, age);

21 myl.add(stu);

22 name &＃61; "";

23 }

24

25 System.out.println("Size of myl1 is "&＃43; myl.size());

26 for(int i &＃61; 0; i

27 Students stu2 &＃61; (Students) myl.get(i);

28 stu2.show();

29 }

30 // //测试能否在链表末尾加入节点(成功)

31 // for(int i &＃61; 0; i

32 // Students stu2 &＃61; (Students) myl.get(i);

33 // stu2.show();

34 // }

35 // //测试能否通过下标加入一个节点(成功)

36 // Students stu3 &＃61; new Students("cyt",5,18);

37 // myl.add(1, stu3);

38 // System.out.println("Size is "&＃43; myl.size());

39 // for(int i &＃61; 0; i

40 // Students stu2 &＃61; (Students) myl.get(i);

41 // stu2.show();

42 // }

43

44 MyList myl2 &＃61; new MyList();

45 size &＃61; random.nextInt(5) &＃43; 1;

46 for (int i &＃61; 0; i

47 credit &＃61; random.nextInt(5);

48 age &＃61; random.nextInt(5) &＃43; 18;

49 for (int j &＃61; 0; j <4; j&＃43;&＃43;) {

50 name &＃43;&＃61; (char) (random.nextInt(26) &＃43; 97);

51 }

52 Students stu2 &＃61; new Students(name, credit, age);

53 myl2.add(stu2);

54 name &＃61; "";

55 }

56 System.out.println("Size is of myl2 "&＃43; myl2.size());

57 for(int i &＃61; 0; i

58 Students stu2 &＃61; (Students) myl2.get(i);

59 stu2.show();

60 }

61

62

63

64 myl.add(1, myl2);

65 System.out.println("Size is of myl1 "&＃43; myl.size());

66 for(int i &＃61; 0; i

67 Students stu2 &＃61; (Students) myl.get(i);

68 stu2.show();

69 }

70

71

72 }

73

74 }

结果输出&＃xff1a;