单链表LinkedList的增删改查

数组作为数据存储结构有一定的缺陷。在无序数组中，搜索性能差，在有序数组中，插入效率又很低（插入位置后面的元素需要集体后移），而且这两种数组的删除效率（集体前移）都很低，并且数组在创建后，其大小是固定了，设置的过大会造成内存的浪费，过小又不能满足数据量的存储。

数组是一种通用的数据结构，能用来实现栈、队列等很多数据结构。而链表也是一种使用广泛的通用数据结构，它也可以用来作为实现栈、队列等数据结构的基础，基本上除非需要频繁的通过下标来随机访问各个数据，否则很多使用数组的地方都可以用链表来代替。

注意：链表是不能解决数据存储的所有问题的，它也有它的优点和缺点。本篇博客我们介绍几种常见的链表，分别是单向链表、双端链表、有序链表、双向链表以及有迭代器的链表。并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述栈和队列，如何用链表代替数组来实现栈和队列。

头指针一定指向链表的第一个结点，有头结点就指向头结点，没有则指向第一个元素结点。

头结点，指向第一个元素结点，data域可为空，也可存放一些链表的信息，作用就是表示单链表的头。

链表通常由一串节点组成，每个节点包含任意的实例数据域(data fields)和一个或两个来指向上一个或下一个节点的位置的指针域(next/prev fields)。链表节点的存储位置可能不连续。

链表分带头结点的链表和不带头结点的链表，根据实际需求来确定。

1.单向链表

单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们提供在链表头插入或链表尾插入，只需要将当前插入的节点设置为头节点指向的节点，next指向原头节点指向的节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。

尾结点的指针域指向null。

举例：

使用带头结点head的单向链表实现--水浒英雄排行榜管理

1）完成对英雄人物的增删改查操作；

2）第一种方式，直接添加到链表的尾部；

3）第二种方式，根据排名将英雄插入到指定位置（如果该排名已有人，则添加失败，并给出提示）

思路：

添加（创建）

1.先创建一个head头结点，作用就是表示单链表的头

2.后面我们每添加一个节点，就直接加入到链表的最后（尾插法）

遍历：

通过一个辅助遍历：帮助遍历整个链表

public class DemoSingleLinkedList {
    public static void main(String[] args) {
        // 测试
        // 先创建节点
        Node hero1 = new Node(1,"宋江","及时雨");
        Node hero2 = new Node(2,"卢俊义","玉麒麟");
        Node hero3 = new Node(3,"吴用","智多星");
        Node hero4 = new Node(4,"公孙胜","入云龙");

        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addRear(hero1);
        singleLinkedList.addRear(hero4); // 尾插法打乱顺序后，影响排列。不符合题目要求
        singleLinkedList.addRear(hero2);
        singleLinkedList.addRear(hero3);

        // 显示
        singleLinkedList.show();
    }
}

// 定义SingleLinkedList 单链表 管理英雄
class SingleLinkedList{
    // 先初始化一个头结点，头结点不要动
    private Node head = new Node(0,"","");
    private Node rear; // 本质是赋值地址

    // 构造器
    public SingleLinkedList() {
        // 初始化
        head.next = null; //指针域问题
        rear = head;
    }

    // 尾插法添加节点到单向链表
    public void addRear(Node node){
        // 尾插法
        node.next = null;
        rear.next = node; // 插入尾结点
        rear = node; // 尾指针后移
    }

    // 头插法添加节点到单向链表
    public void addHead(Node node){
        // 头插法，
        Node temp = head.next; // 暂存地址
        head.next = node;
        node.next = temp;
    }

    // 显示链表（遍历）
    public void show(){
        // 先判断链表是否为空
        if(head.next == null) System.out.println("链表为空");
        // 因为头结点不能动，需要一个辅助变量来遍历
        Node temp = head.next;
        while(temp != null){ // 链表不为空
            System.out.println(temp.toString()); // 输出节点信息
            temp = temp.next; // 指针后移
        }
    }
}
// 定义node节点，每个node对象就是一个节点
class Node{
    public int id; // 编号
    public String name; // 姓名
    public String nickName; // 英雄名
    // 因为一个节点就是这个Node类的实例对象，那么它存储的就是该对象的地址值。
    // 而指针域的作用就是指向下一个节点的地址，所以类型就是Node
    public Node next; // 指向下一个节点

    // 构造器
    public Node(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    // 显示方便，重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                // ", next=" + next +
                '}';
    }
}

可以注意到，尾插法需要输入节点有序，如果输入节点无序，那么链表就也不会按排位来，接下来介绍一种中插法：按排名来添加，（如果该排名节点已存在，则添加失败，给出提示）

思路：

1.首先找到新添加节点的位置；

2.新的节点的next域指向下一个，上一个节点的next域指向新节点。

public class DemoSingleLinkedList {
    public static void main(String[] args) {
        // 测试
        // 先创建节点
        Node hero1 = new Node(1,"宋江","及时雨");
        Node hero2 = new Node(2,"卢俊义","玉麒麟");
        Node hero3 = new Node(3,"吴用","智多星");
        Node hero4 = new Node(4,"公孙胜","入云龙");

        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4); // 尾插法打乱顺序后，影响排列。不符合题目要求
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);


        // 显示
        singleLinkedList.show();
    }
}

// 定义SingleLinkedList 单链表 管理英雄
class SingleLinkedList{
    // 先初始化一个头结点，头结点不要动
    private Node head = new Node(0,"","");
    private Node rear; // 本质是赋值地址

    // 构造器
    public SingleLinkedList() {
        // 初始化
        head.next = null;
        rear = head;
    }

    // 尾插法添加节点到单向链表
    public void addRear(Node node){
        // 尾插法
        node.next = null;
        rear.next = node; // 插入尾结点
        rear = node; // 尾指针后移
    }

    // 头插法添加节点到单向链表
    public void addHead(Node node){
        // 头插法，
        Node temp = head.next; // 暂存地址
        head.next = node;
        node.next = temp;
    }

    // 有序中插法
    public void addByOrder(Node node){
        // 遍历找到该位置，所以需要辅助指针
        Node temp = head;
        while(true){
            if(temp.id == node.id) { // 已存在排名 // 注意这个if要写在三个if的最前面，否则陷入死循环
                System.out.println("该排名英雄已存在！");
                break;
            }
            if(temp.next == null){
                // 链表为空或遍历到最后了，插在尾部
                addRear(node);
                break;
            }
            if(temp.id < node.id && temp.next.id > node.id){
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    // 显示链表（遍历）
    public void show(){
        // 先判断链表是否为空
        if(head.next == null) System.out.println("链表为空");
        // 因为头结点不能动，需要一个辅助变量来遍历
        Node temp = head.next;
        while(temp != null){ // 链表不为空
            System.out.println(temp.toString()); // 输出节点信息
            temp = temp.next; // 指针后移
        }
    }
}
// 定义node节点，每个node对象就是一个节点
class Node{
    public int id; // 编号
    public String name; // 姓名
    public String nickName; // 英雄名
    // 因为一个节点就是这个Node类的实例对象，那么它存储的就是该对象的地址值。
    // 而指针域的作用就是指向下一个节点的地址，所以类型就是Node
    public Node next; // 指向下一个节点

    // 构造器
    public Node(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    // 显示方便，重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                // ", next=" + next +
                '}';
    }
}

运行截图：

可以看到，虽然重复插入的节点是最后插入的，但提示该英雄存在的信息是最先打印的，是因为，节点类本身就是递归嵌套定义的的，所以打印第一个是需要先找到最后一个的，而找到最后一个就会打印这句话。

单线链表的修改：

仍旧以这个例子，修改是指修改名字和昵称，编号不可修改（会打乱顺序)

    public static void main(String[] args) {
        // 测试
        // 先创建节点
        Node hero1 = new Node(1,"宋江","及时雨");
        Node hero2 = new Node(2,"卢俊义","玉麒麟");
        Node hero3 = new Node(3,"吴用","智多星");
        Node hero4 = new Node(4,"公孙胜","入云龙");

        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4); // 尾插法打乱顺序后，影响排列。不符合题目要求
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);

        // 显示
        System.out.println("原链表：");
        singleLinkedList.show();
        System.out.println("---------------");

        System.out.println("修改后的链表：");
        singleLinkedList.update(new Node(3,"小鹿","牛年大吉"));
        singleLinkedList.show();
    }
}

// 定义SingleLinkedList 单链表 管理英雄
class SingleLinkedList{
    // 先初始化一个头结点，头结点不要动
    private Node head = new Node(0,"","");
    private Node rear; // 本质是赋值地址

    // 构造器
    public SingleLinkedList() {
        // 初始化
        head.next = null;
        rear = head;
    }

    // 尾插法添加节点到单向链表
    public void addRear(Node node){
        // 尾插法
        node.next = null;
        rear.next = node; // 插入尾结点
        rear = node; // 尾指针后移
    }

    // 头插法添加节点到单向链表
    public void addHead(Node node){
        // 头插法，
        Node temp = head.next; // 暂存地址
        head.next = node;
        node.next = temp;
    }

    // 有序中插法
    public void addByOrder(Node node){
        // 遍历找到该位置，所以需要辅助指针
        Node temp = head;
        while(true){
            if(temp.id == node.id) { // 已存在排名
                System.out.println("该排名英雄已存在！");
                break;
            }
            if(temp.next == null){
                // 链表为空或遍历到最后了，插在尾部
                addRear(node);
                break;
            }
            if(temp.id < node.id && temp.next.id > node.id){
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }


    // 修改节点信息，根据编号修改。
    /*
    说明根据node的id来修改
     */
    public void update(Node node){
        // 判断链表是否为空
        if(head.next == null) System.out.println("链表为空");
        // 找到需要修改的节点
        // 定义一个辅助变量
        Node temp = head;
        boolean flag = false;
        while(true){
            if(temp.next == null) {// 链表为空，或遍历到最后一个节点了
                break;
            }
            if(temp.id == node.id){ // 找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.name = node.name;
            temp.nickName = node.nickName;
        }else System.out.println("没有找到该编号英雄！");
    }
    // 显示链表（遍历）
    public void show(){
        // 先判断链表是否为空
        if(head.next == null) System.out.println("链表为空");
        // 因为头结点不能动，需要一个辅助变量来遍历
        Node temp = head.next;
        while(temp != null){ // 链表不为空
            System.out.println(temp.toString()); // 输出节点信息
            temp = temp.next; // 指针后移
        }
    }
}
// 定义node节点，每个node对象就是一个节点
class Node{
    public int id; // 编号
    public String name; // 姓名
    public String nickName; // 英雄名
    // 因为一个节点就是这个Node类的实例对象，那么它存储的就是该对象的地址值。
    // 而指针域的作用就是指向下一个节点的地址，所以类型就是Node
    public Node next; // 指向下一个节点

    // 构造器
    public Node(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    // 显示方便，重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                // ", next=" + next +
                '}';
    }

运行截图：

删除节点：

// 删除节点
public void deleteNode(Node node){
    Node temp = head; // 遍历指针
    boolean flag = false;
    while(true) {
        if (temp.next == null) { // 链表为空或遍历到最后了
            break;
        }
        if (temp.next.id == node.id) { // 找到该节点的前驱节点
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if(flag){
        temp.next = temp.next.next;
    }else{ // 遍历到最后也没找到
        System.out.println("链表中不存在该节点");
    }
}

System.out.println("删除节点后的链表：");
singleLinkedList.deleteNode(hero4);
singleLinkedList.show();

运行截图：

根据id查找结点：

// 根据id查找结点
public Node get(int id){
    Node temp = head; // 遍历指针
    Node result = null;
    boolean flag = false;
    while(true){
        if(temp.id == id){ // 这个if要放在判空if前面，避免是最后一个节点
            result = temp;
            flag = true;
            break;
        }
        else if(temp.next == null){ // 链表为空，或找到最后一个节点了  
            break;
        }
        temp = temp.next;
    }
    if(flag) return result;
    else throw new NullPointerException("该节点不存在！");
}

System.out.println("根据id查找的链表：");
System.out.println(singleLinkedList.get(1).toString());
System.out.println("---------------");

运行截图：

参考博客：

https://www.cnblogs.com/ysocean/p/7928988.html#_label3