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

Java实现单向链表——精简_tail->next = newnode; tail = newnode;

作者：AllinToyou | 2024-05-08 02:06:44

赞

踩

tail->next = newnode; tail = newnode;

文章目录

引言

实现思路

 添加元素

 插入元素

 删除元素

查找元素 

更新元素 

显示链表 

实现代码（完整）

总结

留言 

引言

       链表是一种重要的数据结构。它的存储空间是不连续的，单向链表是最简单的一种链表。本文主要介绍单向链表，及其“增删改查”等功能的实现。我们希望设计出来的链表不仅仅只能存储一种类型的数据。而是可以像ArrayList集合那样，存储任意类型的数据，因此设计的时候要结合泛型。

实现思路

       链表是由一个个的节点链接起来的，这里介绍的是单向链表，每个节点都要有一个数据域“value”用来存储数据，和指向下一个节点的引用“next”，它就像是一根链子，把每一个节点链接起来。除了最后一个节点之外，其余的每个节点的“next”都指向它的下一个节点，这样就形成了一个链表。

为了方便之后进行“增删改查”操作，链表要有一个头结点“head”,尾结点“tail”及链表的长度“size”。

       首先要有一个私有的静态内部类，这个类是“节点类”,它是为整个链表服务的，我们要存入链表中的数据就要被封装成一个个节点，然后链接在链表中。显然，每个节点都是根据这个节点类创建出来的。

  1. 	private static class ListNode<T> {// 定义私有节点内部类
  2. 		T value;// 用来存储数据(数据域)
  3. 		ListNode<T> next;// 用来存储下一节点的引用(地址域)
  4.  
  5. 		public ListNode(T val) {// 构造方法，
  6. 			this.value = val;
  7. 		}

 添加元素

       添加元素时，我们只需要把要添加的元素封装成一个节点，然后链接在链表的尾部即可。如果链表为空，那么链表的头结点和尾结点都是这个节点。否则就把这个节点直接链接到“尾结点”后面。同时它就是新的“尾结点”

  1. 	public void append(T val) {// 添加元素，直接添加在链表的末尾
  2. 		ListNode<T> newNode = new ListNode<T>(val);
  3. 		// 如果尾结点为空，那么这个链表一个节点都没有，即第一次添加节点
  4. 		if (tail == null) {
  5. 			head = tail = newNode;
  6. 		} else {// 否则直接把节点链接在链表尾部
  7. 			tail.next = newNode;
  8. 			tail = newNode;
  9. 		}
  10. 		size++;
  11. 	}

 插入元素

       插入元素时，如果是在链表头部插入新节点newNode，那么直接让newNode的next指向头结点，然后newNode就是新的头结点。如果是在链表尾部插入，则直接添加元素方法append()即可。如果是在中间某个位置插入新节点newNode，那么通过for循环，从头结点开始，找到要插入位置的前一个节点prev，和prev的下一个节点after；然后让prev的next指向newNode，newNode的next指向after，链表长度加1即可。如图：

  1. public boolean insert(int position, T val) {// 插入节点，可以在链表的任意位置插入节点
  2. 		if (position > size || position < 0) {//如果插入的位置不合法，做出提示
  3. 			System.out.println("请输入正确的下标:0-" + (size - 1));
  4. 			return false;
  5. 		}
  6. 		ListNode<T> newNode = new ListNode<T>(val);
  7. 		if (position == 0) {// 在链表头结点中插入节点
  8. 			newNode.next = head;
  9. 			head = newNode;
  10. 			if (tail == null) {
  11. 				tail = newNode;// 如果第一次添加元素，此时尾结点也是此节点
  12. 			}
  13. 			size++;
  14. 			return true;
  15. 		} else if (position == size) {// 在链表尾结点中插入节点
  16. 			this.append(val);
  17. 			return true;
  18.  
  19. 		} else {
  20. 			ListNode<T> prev = head;
  21. 			//找到要插入位置的前一个节点
  22. 			for (int i = 0; i < position - 1; i++) {
  23. 				prev = prev.next;
  24. 			}
  25. 			//此时prev的下一个节点就就是要插入位置的后一个节点
  26. 			ListNode<T> after = prev.next;
  27. 			//更改指向，即完成了添加元素
  28. 			prev.next = newNode;
  29. 			newNode.next = after;
  30. 			size++;
  31. 			return true;
  32. 		}
  33. 	}

 删除元素

       删除元素时，如果删除的节点是“头结点”，那么新的“头结点”就是原头结点的下一个节点，然后再判断链表的长度是否为0，如果为0，那么尾结点为null，删除的节点是其他的节点的话，就要从“头结点”开始遍历链表，找到要删除的节点“cur”和它前一个节点“prev”。然后让“prev”的next指向 “cur”的“next”即可。

  1. 	public boolean delete(T val) {
  2. 		if (head != null && head.value.equals(val)) {
  3. 			head = head.next;
  4. 			size--;
  5. 			// 删除后如果长度为0,头结点和尾结点都为空
  6. 			if (size == 0) {
  7. 				tail = null;
  8. 			}
  9. 			return true;
  10. 		} else {
  11. 			ListNode<T> prev = head;//标记要删除的节点的前一个节点
  12. 			ListNode<T> cur = head;//标记要删除的节点
  13. 			//从头结点开始遍历链表，找到了要删除的节点
  14. 			while (prev != null && cur != null) {
  15. 				if (cur.value.equals(val)) {//此条件如果成立，则找到了要删除的节点
  16. 					if (cur == tail) {//如果它是尾结点，那么新的尾结点就是前一个节点
  17. 						tail = prev;
  18. 					}
  19. 					prev.next = cur.next;//让前一个节点指向要删除节点的下一个节点
  20. 					size--;
  21. 					return true;
  22. 				}
  23. 				prev = cur;
  24. 				cur = cur.next;
  25. 			}
  26. 		}
  27. 		return false;
  28. 	}

查找元素 

       查找元素，通过使用for循环，从头结点开始查找。找到目标节点后，将index返回。如果没有找到 ，就返回-1。

  1. 	public int search(T val) {// 查找元素，返回该元素在链表中的下标，如果没有则返回-1
  2. 		ListNode<T> cur = head;
  3. 		//从头结点遍历链表，寻找目标节点
  4. 		for (int index = 0; cur != null; index++) {
  5. 			//如果某个节点的value内容和val一样，即找到了目标节点
  6. 			if (cur.value.equals(val)) {
  7. 				return index;
  8. 			}
  9. 			cur = cur.next;
  10. 		}
  11. 		//遍历链表没找到目标节点，返回-1
  12. 		return -1;
  13. 	}

更新元素 

       更新元素时，通过while循环查找要更新的节点。找到目标节点之后，把它的“value”修改成要修改的数据“newVal”即可。

  1. 	public boolean update(T oldVal, T newVal) {// 更新链表中的某个节点中的值
  2. 		ListNode<T> cur = head;
  3. 		// 从头结点开始遍历链表，寻找要更新的节点
  4. 		while (cur != null) {
  5. 			//找到目标节点后，更新它的值
  6. 			if (cur.value.equals(oldVal)) {
  7. 				cur.value = newVal;
  8. 				return true;
  9. 			}
  10. 			cur = cur.next;
  11. 		}
  12. 		return false;
  13. 	}

显示链表 

       显示链表可以先创建一个ArrayList集合对象“NodeList”。通过while循环，把链表的每个节点都添加进去，然后把“”NodeList打印输出即可。也可以创建一个StringJoiner对象，通过循环把每个节点的value 添加进去，然后打印输出。

  1. public void display() {// 用于显示链表
  2.  
  3. 		ArrayList<ListNode<T>> NodeList = new ArrayList<LinkedList.ListNode<T>>();
  4. 		StringJoiner sj = new StringJoiner(",", "[", "]");
  5. 		ListNode<T> cur = head;
  6. 		// 通过while循环遍历链表所有节点
  7. 		while (cur != null) {
  8. 			// 把链表节点添加到ArrayList集合中
  9. 			NodeList.add(cur);
  10. 			cur = cur.next;
  11. 		}
  12. 		System.out.println(NodeList);// 打印
  13.  
  14. //		while (cur != null) {
  15. //			sj.add(cur.value.toString());
  16. //			cur = cur.next;
  17. //		}
  18. //		System.out.println(sj.toString());
  19. 	}

实现代码（完整）

LinkedList.java

  1.  
  2. import java.util.ArrayList;
  3. import java.util.StringJoiner;
  4.  
  5. public class LinkedList<T> {
  6. 	ListNode<T> head;// 链表的头结点
  7. 	ListNode<T> tail;// 链表的尾结点
  8. 	int size;// 链表的长度
  9.  
  10. 	private static class ListNode<T> {// 定义私有节点内部类
  11. 		T value;// 用来存储数据(数据域)
  12. 		ListNode<T> next;// 用来存储下一节点的引用(地址域)
  13.  
  14. 		public ListNode(T val) {// 构造方法，
  15. 			this.value = val;
  16. 		}
  17.  
  18. 		@Override
  19. 		// 重写toString()方法，便于查看链表内容，如果链表中放入自己定义的类的对象，那么在该类中一定要重写toString()方法
  20. 		public String toString() {
  21. 			// TODO Auto-generated method stub
  22. 			return this.value.toString();
  23. 		}
  24. 	}
  25.  
  26. 	public LinkedList() {// 链表的构造方法，
  27. 		head = null;
  28. 		tail = null;
  29. 		size = 0;
  30. 	}
  31.  
  32. 	public void append(T val) {// 添加元素，直接添加在链表的末尾
  33. 		ListNode<T> newNode = new ListNode<T>(val);
  34. 		// 如果尾结点为空，那么这个链表一个节点都没有，即第一次添加节点
  35. 		if (tail == null) {
  36. 			head = tail = newNode;
  37. 		} else {// 否则直接把节点链接在链表尾部
  38. 			tail.next = newNode;
  39. 			tail = newNode;
  40. 		}
  41. 		size++;
  42. 	}
  43.  
  44. 	public boolean insert(int position, T val) {// 插入节点，可以在链表的任意位置插入节点
  45. 		if (position > size || position < 0) {
  46. 			System.out.println("请输入正确的下标:0-" + (size - 1));
  47. 			return false;
  48. 		}
  49. 		ListNode<T> newNode = new ListNode<T>(val);
  50. 		if (position == 0) {// 在链表头结点中插入节点
  51. 			newNode.next = head;
  52. 			head = newNode;
  53. 			if (tail == null) {
  54. 				tail = newNode;// 如果第一次添加元素，此时尾结点也是此节点
  55. 			}
  56. 			size++;
  57. 			return true;
  58. 		} else if (position == size) {// 在链表尾结点中插入节点
  59. 			this.append(val);
  60. 			return true;
  61.  
  62. 		} else {
  63. 			ListNode<T> prev = head;
  64. 			// 找到要插入位置的前一个节点
  65. 			for (int i = 0; i < position - 1; i++) {
  66. 				prev = prev.next;
  67. 			}
  68. 			// 此时prev的下一个节点就就是要插入位置的后一个节点
  69. 			ListNode<T> after = prev.next;
  70. 			// 更改指向，即完成了添加元素
  71. 			prev.next = newNode;
  72. 			newNode.next = after;
  73. 			size++;
  74. 			return true;
  75. 		}
  76. 	}
  77.  
  78. 	public void display() {// 用于显示链表
  79.  
  80. 		ArrayList<ListNode<T>> NodeList = new ArrayList<LinkedList.ListNode<T>>();
  81. 		StringJoiner sj = new StringJoiner(",", "[", "]");
  82. 		ListNode<T> cur = head;
  83. 		// 通过while循环遍历链表所有节点
  84. 		while (cur != null) {
  85. 			// 把链表节点添加到ArrayList集合中
  86. 			NodeList.add(cur);
  87. 			cur = cur.next;
  88. 		}
  89. 		System.out.println(NodeList);// 打印
  90.  
  91. //		while (cur != null) {
  92. //			sj.add(cur.value.toString());
  93. //			cur = cur.next;
  94. //		}
  95. //		System.out.println(sj.toString());
  96. 	}
  97.  
  98. 	// 用于删除链表的元素
  99. 	public boolean delete(T val) {
  100. 		if (head != null && head.value.equals(val)) {
  101. 			head = head.next;
  102. 			size--;
  103. 			// 删除后如果长度为0,头结点和尾结点都为空
  104. 			if (size == 0) {
  105. 				tail = null;
  106. 			}
  107. 			return true;
  108. 		} else {
  109. 			ListNode<T> prev = head;// 标记要删除的节点的前一个节点
  110. 			ListNode<T> cur = head;// 标记要删除的节点
  111. 			// 从头结点开始遍历链表，找到了要删除的节点
  112. 			while (prev != null && cur != null) {
  113. 				if (cur.value.equals(val)) {// 此条件如果成立，则找到了要删除的节点
  114. 					if (cur == tail) {// 如果它是尾结点，那么新的尾结点就是前一个节点
  115. 						tail = prev;
  116. 					}
  117. 					prev.next = cur.next;// 让前一个节点指向要删除节点的下一个节点
  118. 					size--;
  119. 					return true;
  120. 				}
  121. 				prev = cur;
  122. 				cur = cur.next;
  123. 			}
  124. 		}
  125. 		return false;
  126. 	}
  127.  
  128. 	public int search(T val) {// 查找元素，返回该元素在链表中的下标，如果没有则返回-1
  129. 		ListNode<T> cur = head;
  130. 		// 从头结点遍历链表，寻找目标节点
  131. 		for (int index = 0; cur != null; index++) {
  132. 			// 如果某个节点的value内容和val一样，即找到了目标节点
  133. 			if (cur.value.equals(val)) {
  134. 				return index;
  135. 			}
  136. 			cur = cur.next;
  137. 		}
  138. 		// 遍历链表没找到目标节点，返回-1
  139. 		return -1;
  140. 	}
  141.  
  142. 	public boolean update(T oldVal, T newVal) {// 更新链表中的某个节点中的值
  143. 		ListNode<T> cur = head;
  144. 		// 从头结点开始遍历链表，寻找要更新的节点
  145. 		while (cur != null) {
  146. 			//找到目标节点后，更新它的值
  147. 			if (cur.value.equals(oldVal)) {
  148. 				cur.value = newVal;
  149. 				return true;
  150. 			}
  151. 			cur = cur.next;
  152. 		}
  153. 		return false;
  154. 	}
  155. }

Main.java 

  1. public class Main {
  2. 	public static void main(String[] args) {
  3. 		LinkedList<String> list = new LinkedList<String>();
  4. 		list.append("关羽");
  5. 		list.append("张飞");
  6. 		list.append("赵云");
  7. 		list.append("马超");
  8. 		list.append("黄忠");
  9. 		list.display();
  10. 		System.out.println("---------------------------------");
  11. 		int index1 = list.search("赵云");
  12. 		System.out.println("赵云的位置："+index1);
  13. 		int index2 = list.search("刘备");
  14. 		System.out.println("刘备的位置："+index2);
  15. 		System.out.println("---------------------------------");
  16. 		list.insert(2, "刘备");
  17. 		list.delete("马超");
  18. 		list.update("张飞", "孙权");
  19. 		list.display();
  20. 		
  21. 	}
  22. }

测试结果 ：

总结

       单向链表只有指向下一个节点的引用“next”，因此，遍历只能从头结点开始从前往后遍历，直到尾结点。

       要实现链表的“插入”，“删除”，“更新”等操作，关键是要通过对链表的遍历找到“目标节点”，然后更改其引用“next”的指向即可。

留言 

由于水平有限，一些细节可能没有考虑到位，还请理解！本文仅供参考使用，如有帮助，不甚荣幸！

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

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

  

闽ICP备14008679号