JAVA数据结构之单链表

定义

1. 链表是以节点的方式来存储,是链式存储

2. 每个节点包含 data 域， next 域：指向下一个节点.

3. 如图：发现链表的各个节点不一定是连续存储.

4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

 单链表(带头结点) 逻辑结构示意图如下

应用场景

使用带head头的单向链表实现 –学生信息管理

• 完成对学生信息的增删改查操作

  第一种方法在添加学生时，直接添加到链表的尾部

  第二种方式在添加学生时，根据学号将学生插入到指定位置

先创建并定义学生类

/**
 * Node 是一个学生类
 * no 学号
 * name 姓名
 * next 指向链表下一个数据
 */
class Node {
    public int no;
    public String name;
    public Node next;

    /**
     * 这是一个公有构造器
     * @param no 定义学号
     * @param name 定义姓名
     */
    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    /**
     * 重写toString 方便打印
     * @return
     */
    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

创建单链表类

这是一个带有头节点的单链表

class SingleLinkedList {
    private Node head = new Node(0, "");
}

增加学生

每添加一个节点，就直接加入到链表的最后，定义一个临时变量temp来遍历链表，获取链表的末尾。

    public void add(Node stuNode) {
        Node temp = head;
        while (temp.next!=null) {
            temp = temp.next;
        }
        temp.next = stuNode;
    }

按照学号顺序添加学生

1. 首先找到新添加的节点的位置, 是通过辅助变量, 通过遍历来搞定

2. 新的节点.next = temp.next

3. 将temp.next = 新的节点

    public void addByOrder(Node stuNode) {
        Node temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > stuNode.no) {
                break;
            } else if (temp.next.no == stuNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == true) {
            System.out.printf("该学号——%d，已经存在，已存在无法加入。\n", stuNode.no);
        } else {
            stuNode.next = temp.next;
            temp.next = stuNode;
        }
    }

修改学生信息

通过学号修改学生信息

思路：

1.通过遍历，先找到对应学号的节点

2.修改信息

    public void update(Node stuNode) {
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }

        Node temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == stuNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag = true) {
            temp.name = stuNode.name;
        } else {
            System.out.printf("没有找到编号%d的节点，无法修改！\n", stuNode.no);
        }
    }

删除学生信息

从单链表中删除一个节点的思路

1. 我们先找到 需要删除的这个节点的前一个节点 temp

2. temp.next = temp.next.next

3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

    public void remove(int no) {
        Node temp = head;
        boolean flag = false;
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        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.printf("要删除的%d节点不存在\n", no);
        }
    }