[数据结构与算法]2021-07-23Java链表单链表

链表和数组在数据结构中属于同级结构
链表是一种非连续非顺序的存储结构
链表是有多个结点组成的，结点由数据和指针组成，单链表暴露的只有一个头结点，对单链表的增删查改都通过头结点来进行
单链表结构如下图所示

通过Java来实现单链表

1. 创建一个结点勒，结点类有两个属相，一个是用于存放数据的data，一个是用于指向下一个结点的指针next

public class Node {

    public int data;//存取数据的变量
    public Node next;//存放指针

    public Node(int data) {//通过构造方法给数据进行赋值
        this.data = data;
    }
}

2. 判断链表的长度

/**
     *计算单链表的长度，也就是结点的个数
     * @return
     */
    private int length() {
        int length =0;
        Node temp = head;
        while (temp.next != null){
            length++;
            temp = temp.next;

        }
        return length;
    }

3. 创建链表，通过在头结点后方加入结点来创建

public class SingleLink {
    Node head = null;//设置头结点为努力了

    /**
     * 创建链表，向链表中加入数据
     * 如果链表中没有结点，则直接插入结点
     * 如果链表中已存在结点，则需要遍历至最后一个结点，在进行插入
     */

    public void addnode(Node node){
        Node temp  = head;//把头结点看作一个指向结点的指针
        while (temp.next !=null){//循环遍历所有结点，直到最后一个跳出循环
            temp=temp.next;//没遍历一次，就向后指向下一个结点
        }
        temp.next = node;//temp作为最后一个结点或者头结点，指向下一个结点
    }
}

4. 在指定的位置插入结点

 /**
     * 在指定位置插入结点
     * 首先判断指定位置是否合法
     * index所需要插入的位置
     *
     * node；插入的结点
     */

    public void insertNodeindex(int index, Node node){
        //判断指定位置是否合法
        if (index<1||index>length()+1){
            System.out.println("此位置不合法或缺失，无法插入");
            return;
        }
        int length =1;//记录链表的长度，也就是结点的位置
        Node temp = head; //node表示可移动的指证，先设为头结点
        while (head.next != null){//遍历单链表
            /**
             * 判断结点是否到达指定位置
             * temp代表当前指定位置的前一个结点，
             * 前一个结点       当前位置         后一个结点
             * temp             temp.next       temp.next,next
             * 将结点插入指定位置
             */
            if (index == length){
                node.next = temp.next;
                temp.next = node;
                return;
            }
            temp = temp.next;
        }
    }

5.删除结点

   /**
     * 删除指定位置的结点
     * index表示指定位置
     */

    public void deletenode(int index){
        //判断指定位置是否合法
        if (index<1 || index>length()){
            System.out.println("指定的位置不合法");
        }
        int length =1;//length表示单链表的长度，也可以作为结点的位置
        Node temp = head;//temp 表示一个可以移动的结点
        while (temp.next != null){
            if (index == length++){//确认结点位置
                temp.next = temp.next.next;//删除结点
                return;
            }
            temp = temp.next;
        }
    }

6. 查找链表中间的结点

/**
     * 查找链表中间的结点
     *通过快慢指针的方式查找中间结点，设置一个慢指针一次走一步，一个快指针一次走两步，
     * 当快指针走完时，慢指针所在的位置就是中间结点所在的位置
     */

    public Node SearchMidNode(Node node) {
        Node fastnode = this.head, slownode = this.head;//将快指针和慢指针同时指向头结点
        //判断快指针的下一个结点和下下一个结点是否为空，当为空时则停止
        while (fastnode != null && slownode != null &&fastnode.next != null && fastnode.next.next != null) {
            fastnode = fastnode.next.next;
            slownode = slownode.next;
        }
        
        System.out.println("链表中中间结点的值为"+slownode.data);
        return slownode;
    }

7. 单链表排序
   7.1单链表选择排序