数据结构 - 单链表的创建、插入、修改、删除和遍历(Java实现)

单链表的插入

  尾插法：使用一个临时结点直接找到最后一个结点 $temp$，然后 $temp.next = newNode, newNode.next = null$

  在中间结点插入一个结点：找到要插入结点的位置的前一个位置的结点 $temp$，让待插入结点的 $next$ 域指向 $temp$ 的后面的结点，最后让 $temp$ 的 $next$ 域指向待插入结点即可。即 $newNode.next = temp.next,temp.next = newNode.next$

//在链表的最后插入一个元素,尾插法
    public void insertList(PersonNode personNode) {
        PersonNode temp = head;
        while(temp.next != null) {//找到最后一个结点
            temp = temp.next;
        }
        temp.next = personNode;
    }

 //按照结点顺序插入
    public void insertListByOrder(PersonNode personNode) {
        PersonNode temp = head;
        while(temp.next != null && temp.next.STNumber != personNode.STNumber && temp.next.STNumber < personNode.STNumber) {
            temp = temp.next;
        }
        if(temp.next == null) {
            temp.next = personNode;
        } else if(temp.next.STNumber == personNode.STNumber) {
            System.out.printf("学号 %d 已经存在无法插入\n", personNode.STNumber);
        } else {
            personNode.next = temp.next;
            temp.next = personNode;
        }
    }

单链表的修改

  直接找到对应位置的结点，然后修改结点信息为新的值。

//根据学号修改结点信息
    public void updateList(int STNumber, String name) {
        if(head.next == null) {
            System.out.println("链表为空,无法进行修改!");
            return ;
        }
        PersonNode temp = head.next;
        while(temp != null && temp.STNumber != STNumber) {
            temp = temp.next;
        }
        if(temp == null) {
            System.out.printf("学号 %d 不存在,无法修改!\n", STNumber);
            return ;
        }
        temp.name = name;
    }

单链表的删除

  找到要删除的结点的前面一个位置的结点 $temp$，直接让 $temp.next = temp.next.next$

 //删除结点信息
    public void deleteList(int STNumber) {
        if(head.next == null) {
            System.out.println("链表为空,无法进行删除");
            return ;
        }
        PersonNode temp = head;
        while(temp.next != null && temp.next.STNumber != STNumber) {
            temp = temp.next;
        }
        if(temp.next == null) {
            System.out.printf("学号%d不存在,无法删除该学生\n", STNumber);
            return ;
        }
        temp.next = temp.next.next;
    }

单链表的遍历

  直接一边查看 $temp$ 是否为 $null$，一边输出结点信息

//遍历链表
    public void outputList() {
        if(head.next == null) {
            System.out.println("链表为空,请添加结点后进行遍历!");
            return ;
        }
        PersonNode temp = head.next;
        while(temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

整体测试代码

import org.w3c.dom.ls.LSOutput;

public class SingleLinkedListTest1 {
    public static void main(String[] args) {
        PersonNode person1 = new PersonNode(1, "111", "1", 1);
        PersonNode person2 = new PersonNode(2, "222", "2", 2);
        PersonNode person3 = new PersonNode(3, "333", "3", 3);
        SingleLinkedList1 singleLinkedList = new SingleLinkedList1();
        singleLinkedList.outputList();
        singleLinkedList.insertListByOrder(person1);
        singleLinkedList.insertListByOrder(person3);
        singleLinkedList.insertListByOrder(person2);
        singleLinkedList.outputList();
        singleLinkedList.updateList(1, "update1");
        singleLinkedList.updateList(4, "update4");
        singleLinkedList.outputList();
        singleLinkedList.deleteList(1);
        singleLinkedList.deleteList(4);
        singleLinkedList.deleteList(2);
        singleLinkedList.deleteList(3);
        singleLinkedList.deleteList(1);
        singleLinkedList.outputList();
    }
}

class SingleLinkedList1 {
    //初始化头结点
    private PersonNode head = new PersonNode(0, "", "", 0);
    //在链表的最后插入一个元素,尾插法
    public void insertList(PersonNode personNode) {
        PersonNode temp = head;
        while(temp.next != null) {//找到最后一个结点
            temp = temp.next;
        }
        temp.next = personNode;
    }
    //遍历链表
    public void outputList() {
        if(head.next == null) {
            System.out.println("链表为空,请添加结点后进行遍历!");
            return ;
        }
        PersonNode temp = head.next;
        while(temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
    //根据学号修改结点信息
    public void updateList(int STNumber, String name) {
        if(head.next == null) {
            System.out.println("链表为空,无法进行修改!");
            return ;
        }
        PersonNode temp = head.next;
        while(temp != null && temp.STNumber != STNumber) {
            temp = temp.next;
        }
        if(temp == null) {
            System.out.printf("学号 %d 不存在,无法修改!\n", STNumber);
            return ;
        }
        temp.name = name;
    }
    //删除结点信息
    public void deleteList(int STNumber) {
        if(head.next == null) {
            System.out.println("链表为空,无法进行删除");
            return ;
        }
        PersonNode temp = head;
        while(temp.next != null && temp.next.STNumber != STNumber) {
            temp = temp.next;
        }
        if(temp.next == null) {
            System.out.printf("学号%d不存在,无法删除该学生\n", STNumber);
            return ;
        }
        temp.next = temp.next.next;
    }
    //按照结点顺序插入
    public void insertListByOrder(PersonNode personNode) {
        PersonNode temp = head;
        while(temp.next != null && temp.next.STNumber != personNode.STNumber && temp.next.STNumber < personNode.STNumber) {
            temp = temp.next;
        }
        if(temp.next == null) {
            temp.next = personNode;
        } else if(temp.next.STNumber == personNode.STNumber) {
            System.out.printf("学号 %d 已经存在无法插入\n", personNode.STNumber);
        } else {
            personNode.next = temp.next;
            temp.next = personNode;
        }
    }
}
//链表中保存的结点信息
class PersonNode{
    int STNumber;
    String name;
    String gender;
    int age;
    PersonNode next;
    public PersonNode(int STNumber, String name, String gender, int age) {
        this.STNumber = STNumber;
        this.name = name;
        this.gender = gender;
        this.age = age;
    }

    @Override
    public String toString() {
        return "PersonNode{" +
                "STNumber='" + STNumber + '\'' +
                ", name='" + name + '\'' +
                ", gender='" + gender + '\'' +
                ", age=" + age +
                '}';
    }
}