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 }

结果输出：