1. 单向链表

1.1 单向链表的结构

单向链表中的节点由两部分组成：

• 节点储存的数据 data

• 指向下一个节点的地址 next　　

1.2 单向链表的特点

1.2.1 单向链表的优点：

相比于数组，链表的增删操作不会影响过多数据的位置，易于进行增删操作

1.2.2 单向链表的缺点

链表的各个节点在内存中的位置是无序的，每次进行查找时只能从头节点开始依次搜寻，检索效率慢

1.3 单向链表节点的插入

插入新节点时，使要插入位置的前一个节点指向新节点，使新节点指向后一个节点

代码实现：

/**
 * @author TSCCG
 * @date 2021/5/16
 * 在指定节点后面插入新节点
 */
/*
 * 节点类：
 */
private class Node{
    Object data;//每个节点的数据
    Node next;//每个节点指向下一个节点的连接

    public Node(Object data){
        this.data = data;
    }
}
/*
 * 插入方法：
 */
public void addExactly(Object value,Object newObj){
    if(size == 0){
        return;
    }
    //定义一前一后两个搜索节点
    Node previous = head;
    Node current = head;
    //判断previous是否是目标节点
    while(previous.data != value){
        /**
        * 既然能进入while循环，说明此时previous不是目标节点，
        * 当previous的next指向为null时，说明链表已经检索完毕，此链表没有找到目标节点
        */
        if(previous.next == null){
            return;
        }else{
            //使previous位于current前面一位
            previous = current;
            current = current.next;
        }
        size++;
    }
    /**
    * 程序运行到此步，说明已经找到目标节点，此时previous就是目标节点，current是previous后一位节点
    * 创建一个新节点，使previous指向新节点，使新节点指向current。如此，就实现了在目标节点后添加新的节点
    */
    Node newNode = new Node(newObj);
    previous.next = newNode;
    newNode.next = current;
}

1.4 单向链表节点的删除

删除节点时，仅需要把目标节点的前一个节点指向目标节点后的一个节点即可，未被指向的节点会被自动处理（head节点除外).

代码实现：

/**
 * @author TSCCG
 * @date 2021/5/16
 * 删除指定节点
 */
/*
 * 节点类：
 */
private class Node{
    //节点的数据
    Object data;
    //下一个节点的地址
    Node next;
    public Node(Object data){
        this.data = data;
    }
}
/**
 * 删除方法
 */
public void delete(Object value){
    //判断链表是否为空
    if(size == 0){
        System.out.println("没有此节点！");
        return;
    }
    //跟前面的插入一样，定义一前一后两个搜索节点，previous在前，current在后
    Node current = head;
    Node previous = head;
    //判断current是否为目标节点
    while(current.data != value){
        //若current.next==null,说明程序已经检索完毕，仍没有找到目标节点，说明没有目标节点
        if(current.next == null){
            System.out.println("没有此节点！");
            return;
        }else{
            //current将当前位置赋给previous,自身向后移动
            previous = current;
            current = current.next;
        }
    }
    //此时current就是目标节点，previous位于目标节点的前一位
    //如果删除的节点是第一个节点,直接使head的后一位节点成为新的头节点即可
    if(current == head){
        head = current.next;
    }else{
        //如果目标节点不是头节点，那么就将previous指向current的后一位即可
        previous.next = current.next;
    }
    size--;
}

1.5 实现一个可进行增删查改的单向链表

Node节点类：

/**
 * @author: TSCCG
 * @date: 2021/5/16
 */
public class Node {
    //为了不让外部类使用Node类，使用private修饰data和next
    /**
     * 节点储存的数据
     */
    private Object data;
    /**
     * 节点存储的指向下一个节点的地址
     */
    private Node next;

    public Node(Object data) {
        this.data = data;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

主类：

/**
 * @author: TSCCG
 * @date: 2021/5/16
 */
public class LinkedListPractice{
    /**
     * 定义头节点
     */
    private Node head;
    /**
     * 定义链表长度，默认为0
     */
    private int size;

    /**
     * 从链表头部添加节点
     */
    public void addHead(Object data) {
        //创建新节点
        Node tempNode = new Node(data);
        //当链表为空时，使新节点成为头节点
        if (size == 0) {
            head = tempNode;
        } else {
            //使新创建的节点指向旧的头节点
            tempNode.setNext(head);
            //使新创建的节点成为新的头节点
            head = tempNode;
        }
        //链表长度加1
        size++;
    }

    /**
     * 从链表尾部添加节点
     */
    public void addEnd(Object data) {
        //创建新节点
        Node newNode = new Node(data);
        if (size == 0) {
            //当链表为空时，使新节点成为头节点
            head = newNode;
        } else {
            //当链表不为空时，找到当前链表的末节点，使其指向新节点，新节点成为新的末节点
            findEnd(head).setNext(newNode);
        }
        //链表长度加1
        size++;
    }

    /**
     * 在指定位置后面插入新节点,
     */
    public void addExactly(Object value,Object data){
        if(size == 0){
            return;
        }
        //定义一前一后两个搜索节点
        Node previous = head;
        Node current = head;
        //判断previous是否是目标节点
        while(previous.getData() != value){
            /*
             * 既然能进入while循环，说明此时previous不是目标节点，
             * 当previous的next指向为null时，说明链表已经检索完毕，此链表没有找到目标节点
             */
            if(previous.getNext() == null){
                return;
            }else{
                //使previous在current位于前面一位
                previous = current;
                current = current.getNext();
            }
        }
       /*
        * 程序运行到此步，说明已经找到目标节点，
        * 此时previous就是目标节点，current是previous后一位节点
        * 创建一个新节点，使previous指向新节点，使新节点指向current。
        */
        Node newNode = new Node(data);
        previous.setNext(newNode);
        newNode.setNext(current);
        size++;
    }

    /**
     * 删除指定节点
     */
    public void deleteNode(Object value) {
        //判断链表是否为空
        if (size == 0) {
            System.out.println("没有此节点！");
            return;
        }
        //跟前面的插入一样，定义一前一后两个搜索节点，previous在前，current在后
        Node current = head;
        Node previous = head;
        //判断current是否为目标节点
        while (current.getData() != value) {
            //若current.next==null,说明程序已经检索完毕，仍没有找到目标节点，说明没有目标节点
            if (current.getNext() == null) {
                System.out.println("没有此节点！");
                return;
            } else {
                //current将当前位置赋给previous,自身向后移动
                previous = current;
                current = current.getNext();
            }
        }
        //此时current就是目标节点，previous位于目标节点的前一位
        //如果删除的节点是第一个节点,直接使head的后一位节点成为新的头节点即可
        if (current == head) {
            head = current.getNext();
        } else {
            //如果目标节点不是头节点，那么就将previous指向current的后一位即可
            previous.setNext(current.getNext());
        }
        size--;
    }
    /**
     * 找到尾节点
     */
    public Node findEnd(Node node) {
        if (node.getNext() == null) {
            return node;
        }
        //使用递归
        return findEnd(node.getNext());
    }

    /**
     * 显示节点信息
     */
    public void showList() {
        if (size > 0) {
            //为不改变链表真实长度，定义一个变量储存目前的链表长度，同理，定义一个临时头节点
            int tempSize = size;
            Node tempNode = head;
            //当链表只有一个节点时，打印数据后直接返回
            if (tempSize == 1) {
                System.out.println("[" + tempNode.getData() + "]");
                return;
            }
            while (tempSize > 0) {
                if (tempNode.equals(head)) {
                    //打印头节点
                    System.out.print("[" + tempNode.getData() + "->");
                } else if (tempNode.getNext() == null){
                    //打印尾节点
                    System.out.println(tempNode.getData() + "]");
                } else {
                    //打印中间节点
                    System.out.print(tempNode.getData() + "->");
                }
                tempNode = tempNode.getNext();
                tempSize--;
            }
        } else {
            //空链表
            System.out.println("[]");
        }
    }

}

测试类：

/**
 * @author: TSCCG
 * @date: 2021/5/16
 */
public class LinkedListPracticeTest {
    public static void main(String[] args) {
        LinkedListPractice link = new LinkedListPractice();
        link.addEnd("AA");
        link.addEnd("bb");
        link.addEnd("CC");
        link.addEnd("DD");
        link.addExactly("CC","FFF");
        link.showList();
        link.deleteNode("bb");
        link.showList();
    }

}

结果：

[AA->bb->CC->FFF->DD]
[AA->CC->FFF->DD]