一、单链表的增删改查实现
增加功能
1、普通插入
思路：遍历到最后一个元素，将最后一个元素的next指向新增加的结点即可
temp.next = 新结点
2、按照No顺序插入
思路：遍历找到大于新结点No的前一个结点，注意是前一个结点，然后进行插入
因为如果是找到大于新结点的当前节点的话，无法在其前面进行插入操作
temp.next.no > node.no
node.next = temp.next;
temp.next = node;
删除功能
思路：找到需要删除这个结点的前一个结点
temp.next = temp.next.next
改查功能
修改和查询功能：直接遍历到当前结点进行操作就行，不需要遍历到
当前结点的前一个结点进行操作。
细心看代码就会发现这一点。
二、代码实现
package com.hao.demo;
/**
* Created with IntelliJ IDEA.
* @Author: Yzh
* @Date: 2021/07/28/16:37
* @Description:
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
Node node1 = new Node(1,"小明");
Node node2 = new Node(2,"小宏");
Node node3 = new Node(3,"分明");
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByNo(node1);
singleLinkedList.addByNo(node3);
singleLinkedList.addByNo(node2);
singleLinkedList.show();
singleLinkedList.update(new Node(2,"修改"));
singleLinkedList.show();
singleLinkedList.delete(3);
singleLinkedList.show();
try{
Node node = singleLinkedList.get(3);
System.out.println(node);
}catch(RuntimeException exception){
System.out.println(exception.getMessage());
}
singleLinkedList.delete(2);
singleLinkedList.show();
singleLinkedList.delete(1);
singleLinkedList.show();
}
}
class SingleLinkedList{
//成员属性
private Node head = new Node(0,"");//头结点不存储数据
/**
* @Author: yzh
* @Description: 根据no获得结点信息
* @Param: [no]
* @return: com.hao.demo.Node
* @Date: 2021/7/28
*/
public Node get(int no){
if(head.next==null){
throw new RuntimeException("单链表为空，不存在元素");
}
Node temp = head.next;
boolean flag = false;
while (true){
if(temp==null){
break;
}
if(temp.no == no){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
return temp;
}else {
throw new RuntimeException("不存在元素");
}
}
/**
* @Author: yzh
* @Description: 添加元素到单链表
* @Param: [node]
* @return: void
* @Date: 2021/7/28
*/
public void add(Node node){
//思路，当不考虑编号顺序时
// 1. 找到当前链表的最后节点[遍历]
// 2. 将最后这个节点的 next 指向 新的节点
Node temp = head;
while (true){
if (temp.next == null) break;//说明找到最后
temp = temp.next;
}
temp.next = node;
}
/**
* @Author: yzh
* @Description: 根据编号来进行链表的排序插入
* @Param: [node]
* @return: void
* @Date: 2021/7/28
*/
public void addByNo(Node node){
//因为单链表，因为我们遍历的 temp 是位于 添加位置的前一个节点，否则插入不了
Node temp = head;
boolean flag = false;
while (true){
if (temp.next==null) break;//已经遍历到最后了
if(temp.next.no > node.no){ //temp.next.no > node.no
break;//说明找到该节点了
}else if (temp.next.no==node.no){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
System.out.println("该no已经存在，无法进行插入");
}else {
node.next = temp.next;
temp.next = node;
}
}
/**
* @Author: yzh
* @Description: 利用no更新节点数据
* @Param: [newNode]
* @return: void
* @Date: 2021/7/28
*/
public void update(Node newNode){
//先判断单链表是否为空
if(head.next==null){
System.out.println("单链表为空");
return;
}
//不为空，遍历寻找no
Node temp = head.next;
boolean flag = false;
while (true){
if(temp == null){//遍历完链表
break;
}
if(temp.no == newNode.no){
flag = true;//找到了
break;
}
temp = temp.next;
}
if(flag){
temp.name = newNode.name;
}else {
System.out.println("没有找到对应的节点，不能修改");
}
}
/**
* @Author: yzh
* @Description: 根据no删除结点
* @Param: [no]
* @return: void
* @Date: 2021/7/28
*/
public void delete(int no){
if (head.next == null){
System.out.println("单链表为空");
return;
}
Node temp = head;
boolean flag = false;
while (true){
if(temp.next==null){
break;//遍历结束
}
if (temp.next.no == no){//找到要删除结点的前一个结点
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.next = temp.next.next;
}else {
System.out.println("要删除的节点不存在");
}
}
/**
* @Author: yzh
* @Description: 显示单链表
* @Param: []
* @return: void
* @Date: 2021/7/28
*/
public void show(){
if(head.next==null){
System.out.println("单链表为空");
return;
}
Node temp = head.next;
while (true){
if(temp==null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
class Node{
//成员变量
public int no;
public String name;
public Node next;
/**
* @Author: yzh
* @Description: 节点构造器，next属性由SingleLinkedList决定
* @Param: [no, name]
* @return:
* @Date: 2021/7/28
*/
public Node(int no, String name) {
this.no = no;
this.name = name;
}
/**
* @Author: yzh
* @Description: 重写toString方法
* @Param: []
* @return: java.lang.String
* @Date: 2021/7/28
*/
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}
总结
写的时候纠结的点就在于是遍历到哪一个结点，到底是当前结点还是当前
结点的前一个结点，因为假如对于增删两个操作要是遍历到当前结点的话，就无
法改变next域的指针指向。而对于查询和修改操作，直接是遍历到当前结点进
行操作的，所以可以直接遍历到当前结点。
|