devbox
空白诗007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

基于Java的链表 常见使用方法_java使用链表的方式

作者：空白诗007 | 2024-07-14 03:57:53

赞

踩

java使用链表的方式

一、链表
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

1.单向链表
单向链表，它包含两个域，一个信息域和一个指针域。信息域用来存储链表中要存放的值，指针域则指向下一个节点。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。其结构图如下：


2、双向链表
双向链表在单链表的基础上，每个节点新增了一个指针域，用来指向前一个节点。其结构图如下：


二、链表的基本操作
首先创建一个LinkedList类。

0.链表节点的对象
创建一个ListNode类，包含两个属性，一个为链表节点的值，另一个为下一个节点的地址。
创建size属性记录链表长度

  1. public class LinkedList {
  2.  
  3. 	//定义节点
  4. 	static class ListNode {
  5. 		int val; // 链表存储的值
  6. 		ListNode next; // 指针，指向下一个节点
  7. 		ListNode() {
  8. 			
  9. 		}
  10. 		ListNode(int val) { 
  11. 			this.val = val; 
  12. 		}
  13. 		ListNode(int val, ListNode next) { 
  14. 			this.val = val;
  15. 			this.next = next; 
  16. 		}
  17. 	}
  18. 	
  19. 	int size; // 链表长度
  20. 	ListNode headNode; //链表头结点
  21. 	ListNode dummyHead = new ListNode(0);
  22. }

1.头插法
头插法，即在链表首部添加一个节点作为新的头结点。
首先要新建一个ListNode 对象作为要插入的节点，然后根据情况进行操作。如果当前链表为空链表，则将该节点直接作为头结点即可创建一个链表；如果当前链表不是空链表，则将要插入的节点的next指针指向原本的头节点。

  1. 	public void headInsertion(int val) {
  2. 		ListNode newListNode = new ListNode(); // 新建一个对象，即为要插入的节点
  3. 		newListNode.val = val; // 对节点存入要插入的值
  4. 		if (headNode == null) { //头结点为空即是个空链表，头结点直接指向要插入的节点即可
  5. 			headNode = newListNode;
  6. 		} else {
  7. 			newListNode.next = headNode; // 要插入的节点应放在第一个，所以它的下一个节点指向head
  8. 			headNode = newListNode; // 插入后新插入的节点是新的头结点
  9. 		}
  10. 		size ++;
  11. 	}

2.任意位置插入节点
insert方法为在任意位置插入节点，参数中的index为插入节点的位置，val为插入节点的值，如果index等于0，则和头插法过程相同。否则，需要先找到前一个节点， 将该节点的next指针指向前一个节点next指向的节点，然后再将前一个节点指向该节点。
插入过程图解如下：
（1）创建要插入的节点对象

（2）current节点指向next节点

（3）previous节点指向current节点，完成插入


   

  1. 	public void insert(int index, int val) {
  2. 		if (index > size) {
  3. 			System.out.println("越界");
  4. 			return;
  5. 		}
  6. 		ListNode newListNode = new ListNode(); // 存放添加元素的链表节点
  7. 		newListNode.val = val;
  8. 		if (index == 0) { // 插入到第0位，和头插法相同
  9. 			if (headNode == null) {
  10. 				headNode = newListNode;
  11. 			} else {
  12. 				newListNode.next = headNode;
  13. 				headNode = newListNode;
  14. 			}
  15. 			size ++;		
  16. 		} else {
  17. 			ListNode prevNode = headNode; // 创建一个指向头结点的指针
  18. 			for (int i = 0; i < index-1; i++) {
  19. 				prevNode = prevNode.next; // 用该指针找到要添加元素位置的前一个
  20. 			}
  21. 			newListNode.next = prevNode.next; // 添加的节点的next指针指向要添加位置的下一个
  22. 			prevNode.next = newListNode; //前一个节点的next指针指向添加的节点
  23. 			size ++;
  24. 		}
  25. 	}

3.尾插法
先找到原先最后一个节点，然后将其next指向要插入的节点即可。

  1. 	public void tailInsertion(int val) {
  2. 		ListNode newListNode = new ListNode();
  3. 		newListNode.val = val; 
  4. 		ListNode prevNode = headNode; // 创建一个指向头结点的指针
  5. 		for (int i = 0; i < size-1; i++) {
  6. 			prevNode = prevNode.next;// 用该指针找到要最后一个节点的前一个节点
  7. 		}
  8. 		newListNode.next = prevNode.next;
  9. 		prevNode.next = newListNode;
  10. 		size ++;
  11. 	}

4.删除第index个元素
找到第index-1个节点，将其直接指向第index+1个节点即可。需要注意空链表或者越界情况。
删除过程图解如下：
（1）找到要删除的节点对象current

（2）previous指针指向next节点即可删除。

  1. 	public void deleteByIndex(int index) {
  2. 		if (index > size) {
  3. 			System.out.println("越界");
  4. 			return;
  5. 		}
  6. 		if (headNode == null) {
  7. 			System.out.println("空链表");
  8. 		} else {
  9. 			if (index == 0) { // 删除第一个元素，直接把头结点指向第二个元素即可
  10. 				headNode = headNode.next;
  11. 				size --;
  12. 			} else {
  13. 				ListNode prevNode = headNode; // 创建一个指向头结点的指针
  14. 				for (int i = 0; i < index-1; i++) {
  15. 					prevNode = prevNode.next; // 用该指针找到要删除元素位置的前一个
  16. 				}
  17. 				System.out.println("delete："+prevNode.next.val);
  18. 				// 要删除的元素的前一个节点的next指针指向下一个节点，完成删除
  19. 				prevNode.next = prevNode.next.next; 
  20. 				size --;
  21. 			}
  22. 		}
  23. 	}

5.删除val元素
删除值为val的节点，以此遍历找到值为val的节点，并对其删除即可。

  1. 	public void deleteByValue(int val) {
  2. 		if (headNode == null) {
  3. 			System.out.println("空链表");
  4. 		} else {
  5. 			while(val == headNode.val){// 如果头结点是要删除的元素
  6. 				headNode = headNode.next;
  7. 				size --;
  8. 			}
  9. 			ListNode prevNode = headNode; // 创建指针，指向被操作的节点的前一位
  10. 			ListNode currentNode = headNode; // 创建指针，指向被操作的节点
  11. 			while(prevNode != null && currentNode != null){
  12. 				if(currentNode.val == val) {
  13. 					prevNode.next = currentNode.next;
  14. 					size--;
  15. 				} else {
  16. 					prevNode = currentNode;
  17. 				}
  18. 				currentNode = currentNode.next;
  19. 			}
  20. 		}
  21. 	}

 6.获取第index节点的值
遍历找到即可。

  1. 	public void getElum(int index) {
  2. 		if (index > size) {
  3. 			System.out.println("越界");
  4. 			return;
  5. 		}
  6. 		ListNode currentNode = headNode;
  7. 		for (int i = 0; i < index; i++) {
  8. 			currentNode = currentNode.next;
  9. 		}
  10. 		int result = currentNode.val;
  11. 		System.out.println(result);
  12. 	}

7.将第Index个节点的值修改为val
找到第index节点，修改val即可。

  1. 	public void update(int index, int val) {
  2. 		if (index > size) {
  3. 			System.out.println("越界");
  4. 			return;
  5. 		}
  6. 		ListNode currentNode = headNode;
  7. 		for (int i = 0; i < index; i++) {
  8. 			currentNode = currentNode.next;
  9. 		}
  10. 		currentNode.val = val;
  11. 	}

8.创建一个链表

  1. 	// 创建一个链表  1->2
  2. 	public void creatLinkList() {
  3. 		ListNode node1 = new ListNode();
  4. 		node1.val = 2;
  5. 		ListNode node2 = new ListNode();
  6. 		node2.val = 1;
  7. 		node1.next = node2;
  8. 		headNode = node1;
  9. 		size++;
  10. 		size++;
  11. 	}

9.按顺序打印链表

  1. 	public void display(){
  2. 		ListNode current = headNode;
  3. 		while(current != null){
  4. 			System.out.print(current.val);
  5. 			if (current.next != null) {
  6. 				System.out.print("->");
  7. 			}
  8. 			current = current.next;
  9. 		}
  10. 		System.out.println();
  11. 	}


三、最终代码展示(包含测试)

  1. package linkedList;
  2.  
  3. public class SingleLinkedList {
  4.  
  5. 	//定义节点
  6. 	static class ListNode {
  7. 		int val; // 链表存储的值
  8. 		ListNode next; // 指针，指向下一个节点
  9. 		ListNode() {
  10. 			
  11. 		}
  12. 		ListNode(int val) { 
  13. 			this.val = val; 
  14. 		}
  15. 		ListNode(int val, ListNode next) { 
  16. 			this.val = val;
  17. 			this.next = next; 
  18. 		}
  19. 	}
  20. 	
  21. 	int size; // 链表长度
  22. 	ListNode headNode; //链表头结点
  23. //	ListNode dummyHead = new ListNode(0);
  24. 	public SingleLinkedList() {
  25. 		headNode = null;
  26. 		size = 0;
  27. 	}
  28. 	
  29. 	//头插法
  30. 	public void headInsertion(int val) {
  31. 		ListNode newListNode = new ListNode(); // 新建一个对象，即为要插入的节点
  32. 		newListNode.val = val; // 对节点存入要插入的值
  33. 		if (headNode == null) { //头结点为空即是个空链表，头结点直接指向要插入的节点即可
  34. 			headNode = newListNode;
  35. 		} else {
  36. 			newListNode.next = headNode; // 要插入的节点应放在第一个，所以它的下一个节点指向head
  37. 			headNode = newListNode; // 插入后新插入的节点是新的头结点
  38. 		}
  39. 		size ++;
  40. 	}
  41. 	
  42. 	//头插法（使用虚拟头结点的方法）
  43. //	public void headInsertionVirtual(int val) {
  44. //		ListNode dummyHead = new ListNode(0, this.head);
  45. //		ListNode newListNode = new ListNode();
  46. //		newListNode.val = val;
  47. //		ListNode currentNode = dummyHead;
  48. //		currentNode.val = val;
  49. //		currentNode.next = dummyHead.next;
  50. //		size ++;
  51. //	}
  52. 	
  53. 	//任意位置插入
  54. 	public void insert(int index, int val) {
  55. 		if (index > size) {
  56. 			System.out.println("越界");
  57. 			return;
  58. 		}
  59. 		ListNode newListNode = new ListNode(); // 存放添加元素的链表节点
  60. 		newListNode.val = val;
  61. 		if (index == 0) { // 插入到第0位，和头插法相同
  62. 			if (headNode == null) {
  63. 				headNode = newListNode;
  64. 			} else {
  65. 				newListNode.next = headNode;
  66. 				headNode = newListNode;
  67. 			}
  68. 			size ++;		
  69. 		} else {
  70. 			ListNode prevNode = headNode; // 创建一个指向头结点的指针
  71. 			for (int i = 0; i < index-1; i++) {
  72. 				prevNode = prevNode.next; // 用该指针找到要添加元素位置的前一个
  73. 			}
  74. 			newListNode.next = prevNode.next; // 添加的节点的next指针指向要添加位置的下一个
  75. 			prevNode.next = newListNode; //前一个节点的next指针指向添加的节点
  76. 			size ++;
  77. 		}
  78. 	}
  79. 	
  80. 	//尾插法
  81. 	public void tailInsertion(int val) {
  82. 		ListNode newListNode = new ListNode();
  83. 		newListNode.val = val; 
  84. 		ListNode prevNode = headNode; // 创建一个指向头结点的指针
  85. 		for (int i = 0; i < size-1; i++) {
  86. 			prevNode = prevNode.next;// 用该指针找到要最后一个节点的前一个节点
  87. 		}
  88. 		newListNode.next = prevNode.next;
  89. 		prevNode.next = newListNode;
  90. 		size ++;
  91. 	}
  92. 	
  93. 	//删除第index个元素
  94. 	public void deleteByIndex(int index) {
  95. 		if (index > size) {
  96. 			System.out.println("越界");
  97. 			return;
  98. 		}
  99. 		if (headNode == null) {
  100. 			System.out.println("空链表");
  101. 		} else {
  102. 			if (index == 0) { // 删除第一个元素，直接把头结点指向第二个元素即可
  103. 				headNode = headNode.next;
  104. 				size --;
  105. 			} else {
  106. 				ListNode prevNode = headNode; // 创建一个指向头结点的指针
  107. 				for (int i = 0; i < index-1; i++) {
  108. 					prevNode = prevNode.next; // 用该指针找到要删除元素位置的前一个
  109. 				}
  110. 				System.out.println("delete："+prevNode.next.val);
  111. 				// 要删除的元素的前一个节点的next指针指向下一个节点，完成删除
  112. 				prevNode.next = prevNode.next.next; 
  113. 				size --;
  114. 			}
  115. 		}
  116. 	}
  117. 	
  118. 	//删除val元素
  119. 	public void deleteByValue(int val) {
  120. 		if (headNode == null) {
  121. 			System.out.println("空链表");
  122. 		} else {
  123. 			while(val == headNode.val){// 如果头结点是要删除的元素
  124. 				headNode = headNode.next;
  125. 				size --;
  126. 			}
  127. 			ListNode prevNode = headNode; // 创建指针，指向被操作的节点的前一位
  128. 			ListNode currentNode = headNode; // 创建指针，指向被操作的节点
  129. 			while(prevNode != null && currentNode != null){
  130. 				if(currentNode.val == val) {
  131. 					prevNode.next = currentNode.next;
  132. 					size--;
  133. 				} else {
  134. 					prevNode = currentNode;
  135. 				}
  136. 				currentNode = currentNode.next;
  137. 			}
  138. 		}
  139. 	}
  140. 	
  141. 	public void getElum(int index) {
  142. 		if (index > size) {
  143. 			System.out.println("越界");
  144. 			return;
  145. 		}
  146. 		ListNode currentNode = headNode;
  147. 		for (int i = 0; i < index; i++) {
  148. 			currentNode = currentNode.next;
  149. 		}
  150. 		int result = currentNode.val;
  151. 		System.out.println(result);
  152. 	}
  153. 	
  154. 	public void update(int index, int val) {
  155. 		if (index > size) {
  156. 			System.out.println("越界");
  157. 			return;
  158. 		}
  159. 		ListNode currentNode = headNode;
  160. 		for (int i = 0; i < index; i++) {
  161. 			currentNode = currentNode.next;
  162. 		}
  163. 		currentNode.val = val;
  164. 	}
  165. 	
  166. 	// 创建一个链表  1->2
  167. 	public void creatLinkList() {
  168. 		ListNode node1 = new ListNode();
  169. 		node1.val = 2;
  170. 		ListNode node2 = new ListNode();
  171. 		node2.val = 1;
  172. 		node1.next = node2;
  173. 		headNode = node1;
  174. 		size++;
  175. 		size++;
  176. 	}
  177. 	
  178. 	
  179. 	//打印链表
  180. 	public void display(){
  181. 		ListNode current = headNode;
  182. 		while(current != null){
  183. 			System.out.print(current.val);
  184. 			if (current.next != null) {
  185. 				System.out.print("->");
  186. 			}
  187. 			current = current.next;
  188. 		}
  189. 		System.out.println();
  190. 	}
  191. 	
  192. 	public static void main(String[] args) {
  193. 		SingleLinkedList singleLinkedList = new SingleLinkedList();
  194.  
  195. 		singleLinkedList.creatLinkList();
  196. 		singleLinkedList.headInsertion(5);
  197. 		singleLinkedList.headInsertion(8);
  198. 		singleLinkedList.headInsertion(9);
  199. 		singleLinkedList.headInsertion(5);
  200. 		singleLinkedList.display();
  201. 		
  202. 		singleLinkedList.insert(0,3);
  203. 		singleLinkedList.insert(0,3);
  204. 		singleLinkedList.insert(2,3);
  205. 		singleLinkedList.insert(2,3);
  206. 		singleLinkedList.insert(2,7);
  207. 		singleLinkedList.display();
  208. 		
  209. 		singleLinkedList.tailInsertion(1);
  210. 		singleLinkedList.display();
  211. 		
  212. 		singleLinkedList.deleteByIndex(1);
  213. 		singleLinkedList.display();
  214. 		
  215. 		singleLinkedList.deleteByValue(3);
  216. 		singleLinkedList.display();
  217. 		singleLinkedList.getElum(0);
  218.  
  219. 		singleLinkedList.update(1, 6);
  220. 		singleLinkedList.display();
  221. 	}
  222. }
  223.

                                     感谢大家的阅读，觉得有所帮助的朋友点点关注点点赞！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/空白诗007/article/detail/823037
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号