单向链表

单向链表**

博客分类：

• 数据结构 数据结构

【链表】 是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。 由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多， 但是查找一个节点或者访问特定编号的节点则需要O(n)的时间， 而顺序表相应的时间复杂度分别是O(㏒ n)和O(1)。 【单向链表】 是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始 一个节点包含两个域，一个信息域和一个指针域，指针域指向下一个节点，最后一个节点指向一个空值 单向链表有一个头节点，可以不存储任何信息，包含一个指向第一个节点的指针 特点: 1.访问节点速度慢，需要从头节点一次遍历链表 2.更新节点快，节点不需要移动，更改相应指针即可

单向链表节点类定义如下：

Java代码

1. public class Node{
3. AnyType element;
5. Node next;
7. }

要实现单向列表的相关操作，可定义类SingleLinkedList如下： Java代码

1. public class SingleLinkedList{
3. private static class Node{
5. AnyType element;
7. Node next;
9. public Node(AnyType element){
10. this.element = element;
11. }
13. }
15. private Node header = new Node(null);
17. private int size = 0;
19. public boolean isEmpty(){
20. return size==0;
21. }
23. public void makeEmpty(){
24. header = null;
25. }
27. public int size(){
28. return size;
29. }
31. ///
32. /* Get element by index
33. / //
34. public AnyType get(int index){
35. return getNode(index).element;
36. }
38. ///
39. /* Add the element to the end of this list
40. / //
41. public void add(AnyType element){
42. add(new Node(element));
43. }
45. ///
46. /* Inserts the specified element at the specified position in this list
47. /* 插入逻辑：
48. /* 1.创建一个新节点
49. /* 2.将原index节点的前一个节点的指针指向新节点
50. /* 3.将新节点的指针指向index节点
51. /* 4.插入后，新节点的位置为index
52. / //
53. public void add(int index,AnyType element){
54. Node newNode = new Node(element);
55. Node previous = getNode(index-1);
56. //index节点
57. Node node = previous.next;
58. //将原index节点的前一个节点的指针指向newNode
59. previous.next = newNode;
60. //将newNode的指针指向index节点
61. newNode.next = node;
62. size++;
63. }
65. ///
66. /* Inserts the specified element at the specified position in this list
67. /* 删除逻辑：
68. /* 1.获得index节点的前一个节点previousNode
69. /* 2.获得index节点的后一个节点nextNode
70. /* 3.将previousNode的指针指向nextNode
71. / //
72. public void remove(int index){
73. Node previous = getNode(index-1);
74. Node next = previous.next.next;
75. previous.next = next;
76. size--;
77. }
80. ///
81. /* 定义此方法是为了便于测试
82. / //
83. public List getElements(){
84. if(isEmpty()){
85. return null;
86. }else{
87. List elements = new ArrayList();
88. Node node = (Node) header;
89. while(node.next!=null){
90. node = node.next;
91. elements.add(((Element)node.element).getValue());
92. }
93. return elements;
94. }
95. }
98. //private methods
99. private Node getNode(int index){
100. if(isEmpty()){
101. throw new RuntimeException("List is empty");
102. }
103. int i = 0;
104. Node node = header;
105. while(i<=index){
106. node = node.next;
107. i++;
108. }
109. return node;
110. }
112. private void add(Node newNode){
113. Node node = header;
114. while(node.next!=null){
115. node = node.next;
116. }
117. node.next = newNode;
118. size++;
119. }
121. }

如何实现链表反向： Java代码

1. ///
2. /* 链表反向
3. / //
4. public void reverse(){
5. if(!isEmpty()){
6. reverse(header.next,header.next.next);
7. }
8. }

Java代码

1. private void reverse(Node node,Node nextNode){
2. if(nextNode.next!=null){
3. reverse(nextNode,nextNode.next);
4. }else{
5. //如果该节点是表尾，那么用头节点指向此节点
6. header.next = nextNode;
7. }
8. //该节点的指针指向前一个节点P，并将节点P的指针设置为空
9. nextNode.next = node;
10. node.next = null;
11. }

来源： [http://tangyanbo.iteye.com/blog/1472811](http://tangyanbo.iteye.com/blog/1472811)