devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构(三)：单链表和双链表_java 单项链表与双向链表的区别

作者：小丑西瓜9 | 2024-05-03 18:48:30

赞

踩

java 单项链表与双向链表的区别

目录

单链表

模拟实现单链表

双链表

模拟实现双链表

单链表

在实现单链表之前，先看看数组和单链表之间的区别：

数组：
1）数组需要维护下标
2）数组定义时需要指定数组长度
3）当在数组的某些位置增加和删除元素时，还要编写代码处理元素的移动
4）时间性能：查找O(1)、插入和删除O(n)
5）空间性能：需要预分配存储空间，分大了浪费，小了容易溢出

单链表：
1）长度可变，扩展性好
2）内存利用高（可以不连续）
3）时间性能：查找O(n)、插入和删除O(1)
4）空间性能：不需要分配存储空间，只要有就可以分配，元素个数不受限制

单链表的逻辑结构如下图所示：

单链表的存储结构图如下：

了解了单链表的特性后，接下来我们举一个例子，用代码将其实现。

模拟实现单链表

  1. package com.chtw.linkedlist;
  2.  
  3. public class SingleLinkedListDemo {
  4.  
  5. 	public static void main(String[] args) {
  6. 		// 测试
  7. 		// 先创建节点
  8. 		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  9. 		HeroNode hero2 = new HeroNode(5, "卢俊义", "玉麒麟");
  10. 		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  11. 		HeroNode hero4 = new HeroNode(8, "林冲", "豹子头");
  12. 		
  13. 		HeroNode hero5 = new HeroNode(4, "宋江", "及时雨");
  14. 		HeroNode hero6 = new HeroNode(6, "卢俊义", "玉麒麟");
  15. 		HeroNode hero7 = new HeroNode(7, "吴用", "智多星");
  16. 		HeroNode hero8 = new HeroNode(2, "林冲", "豹子头");
  17.  
  18. 		// 创建链表
  19. 		SingleLinkedList singleLinkedList = new SingleLinkedList();
  20. 		SingleLinkedList singleLinkedList1 = new SingleLinkedList();
  21.  
  22. 		// 加入
  23. 		/*
  24. 		 * singleLinkedList.add(hero1); singleLinkedList.add(hero2);
  25. 		 * singleLinkedList.add(hero3); singleLinkedList.add(hero4);
  26. 		 */
  27. 		singleLinkedList.addByOrder(hero1);
  28. 		singleLinkedList.addByOrder(hero4);
  29. 		singleLinkedList.addByOrder(hero3);
  30. 		singleLinkedList.addByOrder(hero2);
  31. 		
  32. 		singleLinkedList1.addByOrder(hero5);
  33. 		singleLinkedList1.addByOrder(hero6);
  34. 		singleLinkedList1.addByOrder(hero7);
  35. 		singleLinkedList1.addByOrder(hero8);
  36. 		// 测试一下单链表的反转功能
  37. 		System.out.println("原来链表1的情况~~");
  38. 		singleLinkedList.list();
  39. 		
  40. 		System.out.println("原来链表2的情况~~");
  41. 		singleLinkedList1.list();
  42. 		
  43. 		/*System.out.println("原来链表的情况~~");
  44. 		singleLinkedList1.list();*/
  45.  
  46.  
  47. 		/*
  48. 		 * System.out.println("size=" + singleLinkedList.getLength());
  49. 		 * System.out.println("倒数第2个=" + singleLinkedList.findLastIndexNode(2));
  50. 		 */
  51.  
  52. 		// 测试删除
  53. 		/*singleLinkedList.delete(2);
  54. 		System.out.println("删除节点后的链表");*/
  55. 		//测试反转
  56. 		/*System.out.println("反转链表后~");
  57. 		singleLinkedList.reversetList();*/
  58. 		
  59. 		System.out.println("连接两个列表后~");
  60. 		singleLinkedList.mergeSingleLinkedList(singleLinkedList.getHead(), singleLinkedList1.getHead());
  61. 		
  62.  
  63. 	}
  64.  
  65. 	
  66. }
  67.  
  68. /**
  69.  * HeroNode节点
  70.  * 
  71.  * @author CHTW
  72.  *
  73.  */
  74. class HeroNode {
  75. 	public int no;
  76. 	public String name;
  77. 	public String nickName;
  78. 	public HeroNode next;
  79.  
  80. 	public HeroNode(int no, String name, String nickName) {
  81. 		super();
  82. 		this.no = no;
  83. 		this.name = name;
  84. 		this.nickName = nickName;
  85. 	}
  86.  
  87. 	@Override
  88. 	public String toString() {
  89. 		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
  90. 	}
  91.  
  92. }
  93.  
  94. /**
  95.  * 创建单链表
  96.  * 
  97.  * @author CHTW
  98.  *
  99.  */
  100. class SingleLinkedList {
  101. 	// 先初始化一个头节点, 头节点不要动, 不存放具体的数据
  102. 	private HeroNode head = new HeroNode(0, "", "");
  103.  
  104. 	// 返回头节点
  105. 	public HeroNode getHead() {
  106. 		return head;
  107. 	}
  108.  
  109. 	/** 添加节点的方法-->在链表的最后面添加*/	
  110. 	public void add(HeroNode heroNode) {
  111. 		// 头节点不能动，创建一个局部临时的辅助变量（指针）
  112. 		HeroNode temp = head;
  113. 		// 遍历链表
  114. 		while (true) {
  115. 			// 找到链表的最后
  116. 			if (temp.next == null) {
  117. 				break;
  118. 			}
  119. 			// 如果没有找到最后, 将temp后移
  120. 			temp = temp.next;
  121. 		}
  122. 		// 当退出while循环时，temp就指向了链表的最后
  123. 		// 将最后这个节点的next 指向 新的节点
  124. 		temp.next = heroNode;
  125. 	}
  126.  
  127. 	 /**添加节点的方法-->按照no进行排序*/
  128. 	public void addByOrder(HeroNode heroNode) {
  129. 		// 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  130. 		// 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  131. 		HeroNode temp = head;
  132. 		boolean flag = false; // flag标志添加的编号是否存在，默认为false
  133. 		while (true) {
  134. 			if (temp.next == null) {// 说明temp已经在链表的最后
  135. 				break;
  136. 			}
  137. 			if (temp.next.no > heroNode.no) { // 位置找到，就在temp的后面插入
  138. 				break;
  139. 			} else if (temp.next.no == heroNode.no) {// 说明希望添加的heroNode的编号已然存在
  140. 				flag = true; // 说明编号存在
  141. 				break;
  142. 			}
  143. 			temp = temp.next; // 后移，遍历当前链表
  144. 		}
  145. 		// 判断flag 的值
  146. 		if (flag) { // 不能添加，说明编号存在
  147. 			System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
  148. 		} else {
  149. 			// 插入到链表中, temp的后面
  150. 			heroNode.next = temp.next;
  151. 			temp.next = heroNode;
  152. 		}
  153. 	}
  154.  
  155. 	// 遍历链表
  156. 	public void list() {
  157. 		if (head.next == null) {
  158. 			System.out.println("链表为空~~");
  159. 			return;
  160. 		}
  161. 		// 头节点不能动，创建一个局部临时的辅助变量（指针）
  162. 		HeroNode temp = head.next;
  163. 		while (true) {
  164. 			// 判断是否为空
  165. 			if (temp == null) {
  166. 				break;
  167. 			}
  168. 			System.out.println(temp);
  169. 			// 将temp后移， 一定小心
  170. 			temp = temp.next;
  171. 		}
  172. 	}
  173.  
  174. 	/**
  175. 	 * 获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
  176. 	 * 
  177. 	 * @param head
  178. 	 *            链表的头节点
  179. 	 * @return 返回的就是有效节点的个数
  180. 	 */
  181. 	public int getLength() {
  182. 		if (head.next == null) { // 空链表
  183. 			return 0;
  184. 		}
  185. 		int length = 0;
  186. 		// 定义一个辅助的变量, 这里我们没有统计头节点
  187. 		HeroNode cur = head.next;
  188. 		while (cur != null) {
  189. 			length++;
  190. 			cur = cur.next; // 遍历
  191. 		}
  192. 		return length;
  193. 	}
  194.  
  195. 	/**
  196. 	 * 查找单链表中的倒数第k个结点 【新浪面试题】
  197. 	 *  思路 
  198. 	 *  1. 接收一个index 
  199. 	 *  2. index 表示是倒数第index个节点
  200. 	 * 	3.先把链表从头到尾遍历，得到链表的总的长度 getLength 
  201. 	 * 	4. 得到size 后，我们从链表的第一个开始遍历(size-index)个，就可以得到
  202. 	 *  5. 如果找到了，则返回该节点，否则返回null
  203. 	 */
  204. 	public HeroNode findLastIndexNode(int index) {
  205. 		// 判断如果链表为空，返回null
  206. 		if (head.next == null) {
  207. 			return null;// 没有找到
  208. 		}
  209. 		// 第一个遍历得到链表的长度(节点个数)
  210. 		int size = getLength();
  211. 		// 第二次遍历 size-index 位置，就是我们倒数的第K个节点
  212. 		// 先做一个index的校验
  213. 		if (index <= 0 || index > size) {
  214. 			return null;
  215. 		}
  216. 		// 定义给辅助变量， for 循环定位到倒数的index
  217. 		HeroNode cur = head.next;
  218. 		for (int i = 0; i < size - index; i++) {
  219. 			cur = cur.next;
  220. 		}
  221. 		return cur;
  222. 	}
  223.  
  224. 	/**
  225. 	 * 删除节点函数 
  226. 	 * 1. 判断链表是否为空 
  227. 	 * 2. 遍历链表，查找到no一直的节点 创建一个辅助变量cur，cur辅助节点找到待删除节点的前一个节点
  228. 	 * 3.删除节点操作 
  229. 	 * 	1)先找到该节点 
  230. 	 * 	2)cur.next = cur.next.next;
  231. 	 * 
  232. 	 * @param no
  233. 	 */
  234. 	public void delete(int no) {
  235. 		HeroNode cur = head;
  236. 		boolean flag = false;
  237. 		while (true) {
  238. 			// 到达链表尾部
  239. 			if (cur.next == null) {
  240. 				break;
  241. 			}
  242. 			if (cur.next.no == no) {
  243. 				flag = true;
  244. 				break;
  245. 			}
  246. 			cur = cur.next;// 后移，遍历
  247. 		}
  248. 		if (flag) {
  249. 			// 删除节点
  250. 			cur.next = cur.next.next;
  251. 		} else {
  252. 			System.out.println("要删除的节点不存在！");
  253. 		}
  254.  
  255. 	}
  256.  
  257. 	/** 修改节点的信息, 根据no编号来修改，即no编号不能改.
  258. 	 *  说明
  259. 	 *  1. 根据 newHeroNode 的 no 来修改即可
  260. 	 */
  261. 	public void update(HeroNode newHeroNode) {
  262. 		// 判断是否空
  263. 		if (head.next == null) {
  264. 			System.out.println("链表为空~");
  265. 			return;
  266. 		}
  267. 		// 找到需要修改的节点, 根据no编号
  268. 		// 定义一个辅助变量
  269. 		HeroNode temp = head.next;
  270. 		boolean flag = false; // 表示是否找到该节点
  271. 		while (true) {
  272. 			if (temp == null) {
  273. 				break; // 已经遍历完链表
  274. 			}
  275. 			if (temp.no == newHeroNode.no) {
  276. 				// 找到
  277. 				flag = true;
  278. 				break;
  279. 			}
  280. 			temp = temp.next;
  281. 		}
  282. 		// 根据flag 判断是否找到要修改的节点
  283. 		if (flag) {
  284. 			temp.name = newHeroNode.name;
  285. 			temp.nickName = newHeroNode.nickName;
  286. 		} else { // 没有找到
  287. 			System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  288. 		}
  289. 	}
  290. 	
  291. 	/**
  292. 	 * 单链表的反转
  293. 	 */
  294. 	public void reversetList() {
  295. 		// 如果当前链表为空，或者只有一个节点，无需反转，直接返回
  296. 		if (head.next == null || head.next.next == null) {
  297. 			return;
  298. 		} 
  299. 		// 定义一个辅助的指针(变量)，帮助我们遍历原来的链表
  300. 		HeroNode cur = head.next;
  301. 		HeroNode next = null;// 指向当前节点[cur]的下一个节点
  302. 		HeroNode reverseHead = new HeroNode(0, "", "");
  303. 		// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
  304. 		while (cur != null) {
  305. 			next = cur.next;// 先暂时保存当前节点的下一个节点，因为后面需要使用
  306. 			cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的最前端
  307. 			reverseHead.next = cur; // 将cur 连接到新的链表上
  308. 			cur = next;// 让cur后移
  309. 		}
  310. 		// 将head.next 指向 reverseHead.next , 实现单链表的反转
  311. 		head.next = reverseHead.next;
  312. 	}
  313. 	
  314. 	/**
  315. 	 * 合并两个有序的单链表，合并之后的链表依然有序
  316. 	 * @param oldNode1
  317. 	 * @param oldNode2
  318. 	 * @return
  319. 	 */
  320. 	public void mergeSingleLinkedList(HeroNode oldNode1, HeroNode oldNode2) {
  321. 		HeroNode temp1 = oldNode1.next;
  322. 		HeroNode temp2 = oldNode2.next;
  323. 		
  324. 		HeroNode newHead = new HeroNode(0, "", "");
  325. 		
  326. 		if(oldNode1.next == null){
  327. 			newHead.next = oldNode2.next;
  328.         }else if(oldNode2.next == null){
  329.         	newHead.next = oldNode1.next;
  330.         }
  331. 		
  332. 		HeroNode temp3 = newHead;
  333. 		
  334. 		while(temp1 != null || temp2 != null){
  335. 			
  336. 			//链表1为空
  337.             if(temp1 == null && temp2 != null){
  338.                 temp3.next = temp2;
  339.                 temp2 = temp2.next;
  340.             }else if(temp2 == null && temp1 != null){//链表2为空
  341.                 temp3.next = temp1;
  342.                 temp1 = temp1.next;
  343.             }else {//链表都不为空
  344.                 if (temp1.no <= temp2.no) {
  345.                     temp3.next = temp1;
  346.                     temp1 = temp1.next;
  347.                 } else {
  348.                     temp3.next = temp2;
  349.                     temp2 = temp2.next;
  350.                 }
  351.             }
  352.             temp3 = temp3.next;
  353.         }
  354. 		SingleLinkedList singleLinkedList = new SingleLinkedList();
  355.         singleLinkedList.show(newHead);
  356.  
  357. 		
  358. 	}
  359. 	
  360.  
  361. }

main方法里面写了测试，测试的是将两个有序单链表连接起来，依然有序的结构，测试结果如下：

完善一些

  1. package com.chtw.linkedlist;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. public class SingleLinkedListTest {
  7.  
  8. 	public static void main(String[] args) {
  9. 		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  10. 		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  11. 		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  12. 		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  13. 		
  14. 		SingleLinkedListWithHead<HeroNode> linkedListWithHead = new SingleLinkedListWithHead<HeroNode>();
  15. 		linkedListWithHead.add(hero1);
  16. 		linkedListWithHead.add(hero2);
  17. 		linkedListWithHead.add(hero3);
  18. 		linkedListWithHead.add(hero4);
  19. 		
  20. 		System.out.println("==============原链表================");
  21. 		List<SingleLinkedListWithHead<HeroNode>.Node<HeroNode>> nodeList = linkedListWithHead.list();
  22. 		System.out.println(nodeList);
  23. 		
  24. 		System.out.println("==============删除一个后的链表================");
  25. 		linkedListWithHead.dele(hero4);
  26. 		
  27. 		List<SingleLinkedListWithHead<HeroNode>.Node<HeroNode>> nodeList1 = linkedListWithHead.list();
  28. 		System.out.println(nodeList1);
  29. 		
  30. 		System.out.println("==============查找index==1================");
  31. 		SingleLinkedListWithHead<HeroNode>.Node<HeroNode> a = linkedListWithHead.findValue(1);
  32. 		System.out.println(a);
  33. 		
  34. 		System.out.println("==============链表长度================");
  35. 		int size = linkedListWithHead.getLength();
  36. 		System.out.println(size);
  37. 	}
  38.  
  39. }
  40.  
  41. /**
  42.  * 带有头节点的单链表
  43.  * @author CHTW
  44.  *
  45.  */
  46. class SingleLinkedListWithHead<E>{
  47. 	
  48. 	//指定头节点
  49. 	private Node<E> head;
  50. 	
  51. 	@SuppressWarnings("hiding")
  52. 	class Node<E> {
  53. 		protected E element;
  54.         protected Node<E> next;
  55.         
  56.         //构造器
  57.         public Node(E data){
  58.             this.element = data;
  59.         }
  60.  
  61. 		@Override
  62. 		public String toString() {
  63. 			return "Node [element=" + element + "]";
  64. 		}
  65.         
  66.         
  67. 	}
  68. 	
  69. 	/**
  70. 	 * 构造器
  71. 	 */
  72. 	@SuppressWarnings("unchecked")
  73. 	public SingleLinkedListWithHead(){
  74. 		head = new Node<>((E)new Object());
  75. 	}
  76. 	/**
  77. 	 * 实现在链表的尾部插入数据
  78. 	 * @param data
  79. 	 */
  80. 	public void add(E data) {
  81. 		//创建新节点
  82.         Node<E> newNode = new Node<>(data);
  83.         //遍历当前链表，找到最后一个节点
  84.         Node<E> temp = head;
  85.         while(temp.next != null){
  86.             temp = temp.next;
  87.         }
  88.         //绑定最后的一个节点的next
  89.         temp.next = newNode;
  90. 	}
  91. 	
  92. 	/**
  93. 	 * 删除
  94. 	 * @param date
  95. 	 * @return
  96. 	 */
  97. 	public boolean dele(E data) { 
  98. 		//head节点需要单独处理
  99.         if(head.element == data){
  100.             head = head.next;
  101.             return true;
  102.         }
  103.         //删除某一个正常节点
  104.         Node<E> tmp = head;
  105.         while(tmp.next != null){
  106.             if(tmp.next.element == data){
  107.                 tmp.next = tmp.next.next;
  108.                 return true;
  109.             }
  110.             tmp = tmp.next;
  111.         }
  112.         return false;
  113. 	}
  114. 	
  115. 	/**
  116. 	 * 获取长度
  117. 	 * @return
  118. 	 */
  119. 	public int getLength() {
  120. 		int length = 0;
  121. 		Node<E> temp = head;
  122. 		while(temp.next != null) {
  123. 			length ++;
  124. 			temp = temp.next;
  125. 		}
  126. 		return length;
  127. 	}
  128. 	
  129. 	/**
  130. 	 * 获取index处的元素
  131. 	 * @param index
  132. 	 * @return
  133. 	 */
  134. 	public Node<E> findValue(int index){
  135. 		if(index < 0) {
  136. 			return null;
  137. 		}else {
  138. 			Node<E> temp = head;
  139. 			while(index-- > 0 && temp.next != null) {
  140. 				temp = temp.next;
  141. 			}
  142. 			if(index<=0) {
  143. 				return temp;
  144. 			}
  145. 			return null;
  146. 		}
  147. 	}
  148. 	
  149. 	/**
  150. 	 * 遍历链表
  151. 	 * @return
  152. 	 */
  153. 	public List<Node<E>> list(){
  154. 		List<Node<E>> nodeList = new ArrayList<Node<E>>();
  155. 		Node<E> temp = head.next;
  156. 		while(temp != null) {
  157. 			nodeList.add(temp);
  158. 			temp = temp.next;
  159. 		}
  160. 		return nodeList;
  161. 	}
  162. 	
  163. 	
  164. }

 

双链表

在学习双链表之前，先看看单链表的缺点。

单向链表的缺点分析:

  1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
  2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点

为了能够实现双向查找的和自我删除的功能，引出了双向链表的概念。

双向链表的逻辑结构图如下所示：

接下来代码实现一波

模拟实现双链表

  1. package com.chtw.linkedlist;
  2. /**
  3.  * 双向链表
  4.  * 单向链表的缺点分析: 
  5.  * 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
  6.  * 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点
  7.  * @author CHTW
  8.  *
  9.  */
  10. public class DoubleLinkedListDemo {
  11. 	
  12. 	public static void main(String[] args) {
  13. 		//测试添加和显示
  14. 		HeroNodeDouble hero1 = new HeroNodeDouble(1, "宋江", "及时雨");
  15. 		HeroNodeDouble hero2 = new HeroNodeDouble(5, "卢俊义", "玉麒麟");
  16. 		HeroNodeDouble hero3 = new HeroNodeDouble(3, "吴用", "智多星");
  17. 		HeroNodeDouble hero4 = new HeroNodeDouble(8, "林冲", "豹子头");
  18. 		HeroNodeDouble hero5 = new HeroNodeDouble(2, "XXX", "XXXX头");
  19. 		
  20. 		HeroNodeDouble hero6 = new HeroNodeDouble(9 , "SSSS", "XXXSSX头");
  21. 		
  22. 		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  23. 		/*doubleLinkedList.add(hero1);
  24. 		doubleLinkedList.add(hero2);
  25. 		doubleLinkedList.add(hero3);
  26. 		doubleLinkedList.add(hero4);*/
  27. 		doubleLinkedList.addByOrder(hero1);
  28. 		doubleLinkedList.addByOrder(hero2);
  29. 		doubleLinkedList.addByOrder(hero3);
  30. 		doubleLinkedList.addByOrder(hero4);
  31. 		doubleLinkedList.addByOrder(hero5);
  32. 		System.out.println("原链表");
  33. 		doubleLinkedList.list();
  34. 		//doubleLinkedList.addByOrder(hero1);
  35. 		System.out.println("删除后的链表");
  36. 		doubleLinkedList.delete(hero4);
  37. 		doubleLinkedList.list();
  38. 		
  39. 		System.out.println("修改后的链表");
  40. 		doubleLinkedList.update(hero6);
  41. 		doubleLinkedList.list();
  42. 	}
  43. }
  44. class HeroNodeDouble{
  45. 	public int no;
  46. 	public String name;
  47. 	public String nickName;
  48. 	public HeroNodeDouble next;// 指向后一个节点, 默认为null
  49. 	public HeroNodeDouble pre;// 指向前一个节点, 默认为null
  50.  
  51. 	public HeroNodeDouble(int no, String name, String nickName) {
  52. 		super();
  53. 		this.no = no;
  54. 		this.name = name;
  55. 		this.nickName = nickName;
  56. 	}
  57.  
  58. 	@Override
  59. 	public String toString() {
  60. 		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
  61. 	}
  62. }
  63.  
  64. class DoubleLinkedList {
  65. 	
  66. 	//头节点
  67. 	private HeroNodeDouble head = new HeroNodeDouble(0, "", "");
  68.  
  69. 	public HeroNodeDouble getHead() {
  70. 		return head;
  71. 	}
  72.  
  73. 	
  74.  
  75. 	public void setHead(HeroNodeDouble head) {
  76. 		this.head = head;
  77. 	}
  78. 	/**
  79. 	 * 删除函数
  80. 	 * @param hero5
  81. 	 */
  82. 	public void delete(HeroNodeDouble heroNode) {
  83. 		//辅助变量
  84. 		HeroNodeDouble temp = head.next;
  85. 		if(temp == null) {
  86. 			System.out.println("链表为空~~");
  87. 			return;
  88. 		}
  89. 		boolean flag = false;
  90. 		//开始遍历
  91. 		while(true) {
  92. 			if(temp == null) {
  93. 				break;
  94. 			}
  95. 			if(temp.no == heroNode.no) {
  96. 				flag = true;
  97. 				break;
  98. 			}
  99. 			temp = temp.next;
  100. 		}
  101. 		
  102. 		//退出循环时，找到了要删除的节点
  103. 		if(flag) {
  104. 			temp.pre.next = temp.next;
  105. 			// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
  106. 			if (temp.next != null) {
  107. 				temp.next.pre = temp.pre;
  108. 			}		
  109. 		}else {
  110. 			System.out.println(temp+"节点不存在~");
  111. 		}
  112. 	}
  113. 	/**
  114. 	 * 在双链表的最后添加节点
  115. 	 */
  116. 	public void add(HeroNodeDouble heroNode) {
  117. 		// 因为head节点不能动，因此我们需要一个辅助遍历 temp
  118. 		HeroNodeDouble temp = head;
  119. 		// 遍历链表，找到最后
  120. 		while(true) {
  121. 			if(temp.next == null) {
  122. 				break;
  123. 			}
  124. 			temp = temp.next;
  125. 		}
  126. 		// 当退出while循环时，temp就指向了链表的最后
  127. 		// 形成一个双向链表
  128. 		temp.next = heroNode;
  129. 		heroNode.pre = temp;
  130. 	}
  131. 	
  132. 	/**
  133. 	 * 按照heroNode的no进行排序添加
  134. 	 * @param heroNode
  135. 	 */
  136. 	public void addByOrder(HeroNodeDouble heroNode) {
  137. 		// 因为head节点不能动，因此我们需要一个辅助遍历 temp，temp表示要插入节点的前一个节点
  138. 		HeroNodeDouble temp = head;
  139. 		boolean flag = true;
  140. 		// 遍历链表，找到最后
  141. 		while (true) {
  142. 			if (temp.next == null) {
  143. 				break;
  144. 			}
  145. 			if(temp.next.no == heroNode.no) {
  146. 				flag = false;
  147. 				System.out.printf("节点序号 %d 已存在~~\n",temp.next.no);
  148. 				break;
  149. 			}
  150. 			if(temp.next.no > heroNode.no && temp.no < heroNode.no) {
  151. 				break;
  152. 			} 
  153. 			temp = temp.next;
  154. 		}
  155. 		if(flag) {
  156. 			// 形成一个双向链表
  157. 			if(temp.next == null) {
  158. 				temp.next = heroNode;
  159. 				heroNode.pre = temp;
  160. 			}else {
  161. 				temp.next.pre = heroNode;
  162. 				heroNode.next = temp.next;
  163. 				temp.next = heroNode;
  164. 				heroNode.pre = temp;
  165. 			}
  166. 		}
  167. 		
  168. 		
  169. 	}
  170. 	
  171. 	/**
  172. 	 * 遍历双向链表
  173. 	 */
  174. 	public void list() {
  175. 		if(head.next == null) {
  176. 			System.out.println("链表为空~");
  177. 			return;
  178. 		}
  179. 		// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  180. 		HeroNodeDouble temp = head.next;
  181. 		//开始遍历
  182. 		while(true) {
  183. 			//到达链表的尾部
  184. 			if(temp == null) {
  185. 				break;
  186. 			}
  187. 			// 输出节点的信息
  188. 			System.out.println(temp);
  189. 			// 将temp后移， 一定小心
  190. 			temp = temp.next;
  191. 		}
  192. 		
  193. 	}
  194. 	public void update(HeroNodeDouble heroNode) {
  195. 		// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  196. 		HeroNodeDouble temp = head.next;
  197. 		boolean flag = false;
  198. 		// 开始遍历
  199. 		while (true) {
  200. 			// 到达链表的尾部
  201. 			if (temp == null) {
  202. 				break;
  203. 			}
  204. 			if(temp.no == heroNode.no) {
  205. 				flag = true;
  206. 				break;
  207. 			}
  208. 			temp = temp.next;
  209. 		}
  210. 		if(flag) {
  211. 			temp.name = heroNode.name;
  212. 			temp.nickName = heroNode.nickName;
  213. 		}else {
  214. 			System.out.println("该节点不存在~");
  215. 		}
  216. 	}
  217. }

测试结果：

 

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

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

  

闽ICP备14008679号