• 52.【Java 数据结构——线性表】

    线性表

    1.什么是线性表?

    线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
    线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

    2.线性表的定义:

    线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。(直接前驱和直接后继)

    3.线性表图解:

    在这里插入图片描述
    有限:数据元素是有限个的
    序列:小朋友排队是有顺序的.

    4.线性表的长度:

    线性表的元素个数n就是线性表的长度: 当n=0时,那么就是空表.i称为序列！
    线性表的长度不等于数组的长度，通常数组的长度大于等于线性表的长度:

    5.线性表的顺序储存结构：

    5.1定义:

    顺序储存结构:是指的时一段地址连续的储存单元依次存储线性表的数据元素.

    5.2顺序储存结构的插入元素:

    注意事项:
    在这里插入图片描述
    阐述:

    表长+1并不是说数组的长度+1，而是指的时数据元素+1

    方法:

    public static int[] InsertNumber(int []nums,int idex,int number){
        if(nums.length==5){    //假设数组的最大为5个，假如说表的长度等于5，返回null
            return null;
        }
        if(idex==nums.length-1){  //假如说插入元素的下表在线性表中的最后一个，那么就执行下面这样的循环
            nums[idex]=number;    //插入
            return nums;
        }
        if(idex<nums.length-1){   //假如说插入元素的下表不是线性表的最后一个，那么就执行一下程序
            for(int k=nums.length-1;k>idex;k--){
                nums[k]=nums[k-1];   //插入元素后的所有元素后退
            }
            nums[idex ]=number;   //插入
            return nums;
        }
        return null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    主函数:

    import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
public class hello {
    public static void main(String []avgs) {

        int []nums=new int[4];
        nums[0]=1;  //线性表
        nums[1]=2;  //线性表
        nums[2]=3;  //线性表
        int []arr=InsertNumber(nums,0 ,5);  //数组 插入坐标 插入元素
        for(int i=0;i<arr.length;i++){    //打印输出
            System.out.println(arr[i]);
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在这里插入图片描述

    5.3线性表的顺序结构的删除元素:

    删除算法的思路:
    (1)如果删除位置不合理，抛出异常;(2)取出删除元素;
    (3)从删除元素位置开始遍历至到最后一个元素位置，分别将它们都向前移动一个位置;
    (4)表长减1。

    方法:

      public static int[] InsertNumber(int []nums,int idex){
        if(nums.length==0){    //假设线性表为0
            return null;
        }
        if(idex>nums.length){  //假如说删除的数据大于线性表长度
            return null;
        }
        if(idex<nums.length){
            for(int k=idex;k<nums.length-1;k++)  //中间条件目的是为了防止线性表超限
            {
                nums[k]=nums[k+1];
            }
            return nums;
        }
        return null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    主函数:

    import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
public class hello {
    public static void main(String []avgs) {

        int []nums=new int[4];
        nums[0]=1;  //线性表
        nums[1]=2;  //线性表
        nums[2]=3;  //线性表
        int []arr=InsertNumber(nums,1 );  //数组 插入坐标 插入元素
        for(int i=0;i<arr.length;i++){    //打印输出
            System.out.println(arr[i]);
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在这里插入图片描述
    *切记哈，删除和插入的是线性表=====并不是数组*

    5.4线性表顺序储存结构的优缺点

    在这里插入图片描述

    6.顺序存储结构的全部用法:(ArrayList)

    判断是否清空

     public boolean isEmpty(){
        return N==0;
    }

    • 1
    • 2
    • 3

    线性表的长度`

     public int getLength(){
        return N;
    }

    • 1
    • 2
    • 3

    索引所在的值

     public T getNumber(int i){
        return elem[i];
    }

    • 1
    • 2
    • 3

    在线性表中插入元素

     public void Insert(T t){
        elem[N++]=t;
    }

    • 1
    • 2
    • 3

    在指定索引i处增加t

     public void add(int idex,T t){
            for(int i=N;i>idex;i--){
                elem[i]=elem[i-1];
            }
            N++;
            elem[idex]=t;
        }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    删除指定索引i的值，并返回删除索引的值

       public T remove(int i){
        T count=elem[i];
        for(int idex=i;idex<N-1;idex++){
            elem[idex]=elem[idex+1];
        }
        //元素个数-1
        N--;
        return count;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    查找元素T，在链表中出现的第一个位置

      public int Find(T t){
        for(int i=0;i<N;i++){
            if(elem[i].equals(t)){
                return i;
            }
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    数组的扩容

      public void resize(int size){
        T [] newelem=(T[]) new Object[size];
        for(int i=0;i<N;i++){
            newelem[i]=elem[i];  //老数组赋值给新数组
        }
        elem=newelem;   //新数组赋值给老数组
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    `类方法展示:

    public class SquenceList <T>{
    private T[]elem;  //定义一个数据类型为T的数组
   //代表线性表中存放的元素个数
    private int N;
    public SquenceList(int capacity){ //构造方法
        //初始化数组
        this.elem=(T[])new Object[capacity];
        this.N=0;
    }
    //实现对数组的扩容处理
    public void resize(int size){
        T [] newelem=(T[]) new Object[size];
        for(int i=0;i<N;i++){
            newelem[i]=elem[i];  //老数组赋值给新数组
        }
        elem=newelem;   //新数组赋值给老数组
    }
    //清空线性表
    public void clear(){
        N=0;
    }
    //判断线性表是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //求线性表的长度
    public int getLength(){
        return N;
    }
    //获取索引所在的值:
    public T getNumber(int i){
        return elem[i];
    }
    //向线性表中插入元素
    public void Insert(T t){
        elem[N++]=t;
    }
    //在指定索引i处增加t
	 public void add(int idex,T t){
            for(int i=N;i>idex;i--){
                elem[i]=elem[i-1];
            }
            N++;
            elem[idex]=t;
        }
    //删除指定索引i的值，并返回删除索引的值
    public T remove(int i){
        T count=elem[i];
        for(int idex=i;idex<N-1;idex++){
            elem[idex]=elem[idex+1];
        }
        //元素个数-1
        N--;
        return count;
    }
    //查找元素T，在链表中出现的第一个位置
    public int Find(T t){
        for(int i=0;i<N;i++){
            if(elem[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    主方法:

    public class SquenceListTest {
    public static void main(String []avgs){
        //创建顺序表对象
        SquenceList<String> s1=new SquenceList<>(10);
        //测试插入
        s1.Insert("李明");
        s1.Insert("傻子");
        s1.Insert("王二" );
        s1.Insert("张三");
        //测试获取
        String result=s1.getNumber(1);
        System.out.println(result);
        //测试删除
        String remove1=s1.remove(1);
        System.out.println("删除的是:"+remove1);
        //测试清空
        s1.clear();
        System.out.println("清空后的元素个数为:"+s1.getLength());
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    在这里插入图片描述

    7.单链表的全部用法

    创建链表结点

     private class Node1 {   //调用结点类
    T item;    //数据域
    Node1 next;   //指针域

       public Node1(T item, Node1 next) {
           this.item = item;
           this.next = next;
       }
   }//调用节点类

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    对链表进行初始化

    public LinkedList() { //初始化链表
        this.head=new Node1(null,null);
        this.size=0;
    }

    • 1
    • 2
    • 3
    • 4

    //获取指定位置的元素:

    public T get(int idex){
    Node1 target=this.head.next;  //获取0结点的指针，且目前表示的是第一个结点

        for(int i=0;i<idex;i++ ){   //移动指针
            target=target.next;
        }
        return target.item;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    //获取指定位置的结点

    public Node1 getNode(int idex){
    if(idex==-1){   //目的是在指定位置0的时候的作用
        return head;
    }
    Node1 target=this.head.next;
    for(int i=0;i<idex;i++ ){   //移动指针
        target=target.next;
    }
    return target;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    //在尾部添加数据

    public void add(T t){
Node1 node=new Node1(t,null);
if(this.size==0){   //假如说是0结点，那么就添加到零结点
    this.head.next=node;
}else {  //找到最后一个结点
    this.getNode(this.size-1).next=node;
}
//链表长度++
    this.size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    //在指定位置插入数据

    public void add(int idex,T t){
    //获取需要插入点的节点
    Node1 node2 =new Node1(t,null);
    //获取被插入点的结点
    Node1 current=this.getNode(idex);
    //获取被插入点的前一个为止
    Node1 BeforeCurrent=this.getNode(idex-1);
    //把前一个结点的指针指向插入点
    BeforeCurrent.next= node2;
    //把插入点的指针指向被插入点
    node2.next=current;
    this.size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    //删除指定位置的结点

      public T remove(int idex){
        //获取删除点的前一个结点
        Node1 before =this.getNode(idex-1);
        //获取删除点的结点
        Node1 current=this.getNode(idex);
        before.next=current.next;
        this.size--;
        return current.item;

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    类文件:

    

import org.jetbrains.annotations.NotNull;

public class LinkedList<T> {
    Node1 head;  //设置头节点
    int size;   //链表长度

    public LinkedList() { //初始化链表
        this.head=new Node1(null,null);
        this.size=0;
    }
    public void reverse2(){
        reverse1(this.head.next);
    }
    //使用快慢指针寻找中间元素
    public T QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        Node1 quick=this.head.next;
        //设置慢指针计数器:
        int length=0;
        //设置快指针计数器
        int length1=0;
        while(quick!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;
            length++;
            length1++;
        }
        int mid=length1/2;
        quick=this.head.next;  //这边的node要进行重新初始化
        for(int i=0;i<mid;i++){
            quick=quick.next.next;
        }
        return quick.item;
    }
    //利用慢指针进行寻找中间元素
    public T Slowp(){
        //获取第一个结点的指针
        Node1 node=this.head.next;
        //定义一个链表的长度的计数器:
        int length=0;
        while(node!=null){
            node=node.next;
            length++;
        }
        //获取中间元素的长度:
        int mid=length/2;
        node=this.head.next;  //这边的node要进行重新初始化
        for(int i=0;i<mid;i++){
            node=node.next;
        }
        return node.item;
    }
    //通过递归函数完成链表的反转
    public Node1 reverse1(@NotNull Node1 curr){
        if(curr.next!=null){
            //通过反转下一个结点获取，获取prev
            Node1 prev=reverse1(curr.next);
            //将之前的next结点设置成当前的结点
            prev.next=curr;
            //返回curr的结点
            return curr;
        }else{
            //当前结点没有下一个结点
           // 将头部的next结点指向当前结点
            this.head.next=curr;
            return curr.next;
        }
    }
    //链表的反转:
    public void reverseList(){
        //设置反转头
        Node1 reverse = new Node1(null, null);
        //获取正序第一个结点
        Node1 first=this.head.next;
        while(first!=null) {
            //把正序的头节点连接到first的下一个结点
            this.head.next = first.next;
            //将反转的next赋值给first的next
            first.next = reverse.next;
            //将头节点指向first
            reverse.next = first;
            // 从正序链表中获取第一个原始元素
            first = this.head.next;
        }
        //将原始头的next指向反转头结点的next
        this.head.next=reverse.next;
    }
    //获取当前链表的长度:
    public int size(){
        return this.size;
    }
    //获取指定位置的元素:
    public T get(int idex){
        Node1 target=this.head.next;  //获取0结点的指针，且目前表示的是第一个结点

            for(int i=0;i<idex;i++ ){   //移动指针
                target=target.next;
            }
            return target.item;
    }
    //获取指定位置的结点
    public Node1 getNode(int idex){

        if(idex==-1){   //目的是在指定位置0的时候的作用
            return head;
        }
        Node1 target=this.head.next;
        for(int i=0;i<idex;i++ ){   //移动指针
            target=target.next;
        }
        return target;
    }
    //在尾部添加数据
    public void add(T t){
    Node1 node=new Node1(t,null);
    if(this.size==0){   //假如说是0结点，那么就添加到零结点
        this.head.next=node;
    }else {  //找到最后一个结点
        this.getNode(this.size-1).next=node;
    }
    //链表长度++
        this.size++;
    }
    //在指定位置插入数据
    public void add(int idex,T t){
        //获取需要插入点的节点
        Node1 node2 =new Node1(t,null);
        //获取被插入点的结点
        Node1 current=this.getNode(idex);
        //获取被插入点的前一个为止
        Node1 BeforeCurrent=this.getNode(idex-1);
        //把前一个结点的指针指向插入点
        BeforeCurrent.next= node2;
        //把插入点的指针指向被插入点
        node2.next=current;
        this.size++;
    }
    //删除指定位置的结点
    public T remove(int idex){
        //获取删除点的前一个结点
        Node1 before =this.getNode(idex-1);
        //获取删除点的结点
        Node1 current=this.getNode(idex);
        before.next=current.next;
        this.size--;
        return current.item;

    }
    private class Node1 {   //调用结点类
    T item;    //数据域
    Node1 next;   //指针域

       public Node1(T item, Node1 next) {
           this.item = item;
           this.next = next;
       }
   }//调用节点类

}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168

    主文件:

    import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
public class hello {
    public static void main(String []avgs) {
        LinkedList<String> s=new LinkedList<>();
        s.add("aa");
        s.add("bb");
        s.add("cc");
        s.remove(2);
        for(int i=0;i<s.size();i++) {
            System.out.println(s.get(i));
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    7.1练习:

    在这里插入图片描述
    类方法:

    public class test{
   private class Node{
       Node next;  //指针
       int item;  //数据
       public Node(int item,Node next){
           this.next=next;
           this.item=item;
       }
   }//定义节点
    Node head;//定义头节点
    int size; //定义长度
    public test(){
        int size=0; //对长度进行初始化
    }
    public int getSize(){
        return size;
    }
    public Node getNode(int idex){
        Node target=this.head.next;
        for(int i=0;i<idex;i++){
            target=target.next;
        }
        return target;
    }//获得结点
    public int get(int idex){
        return getNode(idex).item;
    }//获得值
    public void add(int t){
        Node node=new Node(t,null);
        if(this.size==0){
            this.head.next=node;
        }else{
            getNode(this.size-1).next=node;
        }
        this.size++;
    }
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    主方法:

    import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
import java.lang.Math;
public class hello {
    public static void main(String []avgs) {

     LinkedList s=new LinkedList<>();
     Scanner sc=new Scanner(System.in);
        System.out.println("请输入您的数据");
        for(int i=0;i<100;i++){
            int m=sc.nextInt();
            s.add(m);
           if(s.get(i).equals(-1)){
               System.out.println("链表创建完毕！");
               break;
           }
        }
        System.out.println("链表的数据为:");
        for (int i=0;i<s.size();i++){
            System.out.print(s.get(i)+" ");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    在这里插入图片描述

    8.循环链表(双指针快慢)

    循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

    8.1判断是否是循环链表

    利用快慢指针判断是否这个链表是否为环形
    基本思路:
    因为快指针比慢指针走的快，慢指针比快指针走的慢。会有多次相遇的机会的
    方法:

      public boolean QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        Node1 quick=this.head.next;
        while(quick!=null&&quick.next!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;
            if(quick!=null&&quick.equals(slow)){
                return true;
            }
        }
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    //创建环形链表:
    只需要把你想要的结点的指针指向你要循环的地方，就可以构成一个循环链表.

       public void Recle(int start,int end){
        Node1 node=getNode(start);
        Node1 node1=getNode(end);
        node1.next=node;
    }

    • 1
    • 2
    • 3
    • 4
    • 5

    全部代码:

    主方法:

import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
import java.lang.Math;
public class hello {
    public static void main(String []avgs) {
   LinkedList<String> s=new LinkedList<>();
   //构造一个单链表
   s.add("aa");
   s.add("cc");
   s.add("ee");
   s.add("zz");
   System.out.println(s.QuickSlowP());
   //构造一个环形链表
      s.Recle(2,s.size()-1);
        System.out.println(s.QuickSlowP());
    }
}

类方法

import org.jetbrains.annotations.NotNull;

public class LinkedList<T> {
    Node1 head;  //设置头节点
    int size;   //链表长度
    public LinkedList() { //初始化链表
        this.head=new Node1(null,null);
        this.size=0;
    }
    public void Recle(int start,int end){
        Node1 node=getNode(start);
        Node1 node1=getNode(end);
        node1.next=node;
    }
    //使用快慢指针寻找中间元素
    public boolean QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        Node1 quick=this.head.next;
        while(quick!=null&&quick.next!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;
            if(quick!=null&&quick.equals(slow)){
                return true;
            }
        }
        return false;
    }
    //获取当前链表的长度:
    public int size(){
        return this.size;
    }
    //获取指定位置的元素:
    public T get(int idex){
        Node1 target=this.head.next;  //获取0结点的指针，且目前表示的是第一个结点

            for(int i=0;i<idex;i++ ){   //移动指针
                target=target.next;
            }
            return target.item;
    }
    //获取指定位置的结点
    public Node1 getNode(int idex){

        if(idex==-1){   //目的是在指定位置0的时候的作用
            return head;
        }
        Node1 target=this.head.next;
        for(int i=0;i<idex;i++ ){   //移动指针
            target=target.next;
        }
        return target;
    }
    //在尾部添加数据
    public void add(T t){
    Node1 node=new Node1(t,null);
    if(this.size==0){   //假如说是0结点，那么就添加到零结点
        this.head.next=node;
    }else {  //找到最后一个结点
        this.getNode(this.size-1).next=node;
    }
    //链表长度++
        this.size++;
    }
    //在指定位置插入数据
    private class Node1 {   //调用结点类
    T item;    //数据域
    Node1 next;   //指针域

       public Node1(T item, Node1 next) {
           this.item = item;
           this.next = next;
       }
   }//调用节点类

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104

    在这里插入图片描述

    8.2求循环链表的入口元素

    基本思路:
    首先我们要判断这个链表是否是一个循环链表，如果是循环链表的话那么我们就继续执行操作，不是循环链表的话返回一个NULL。判断是否是入口的关键就在于慢指针slow，和一个新的指针（从第一个元素开始）往后遍历，如果新的指针和指针slow相交的位置，就是元素的所在位置.

      public T QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        int length=-1;
        int a=0;
        Node1 quick=this.head.next;
        while(quick!=null&&quick.next!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;

            if(quick!=null&&quick.equals(slow)){   //假如环形
                Node1 entry=this.head.next;   //定义一个新的指针
                while(!entry.equals(slow)){
                    entry=entry.next;
                    slow=slow.next;
                }
                return entry.item;
            }
        }
        return null;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    在这里插入图片描述

    8.3指定点循环链表的建立

      public void Recle(int start,int end){
        Node1 node=getNode(start);  //开始点
        Node1 node1=getNode(end);	//结束点
        node1.next=node;          //首尾相连接
    }

    • 1
    • 2
    • 3
    • 4
    • 5

    8.4不指定点循环链表建立

       public void SolveYsf (int m,int n){  //m是元素的个数，n是间隔几个
        //建立一个链表
        for(int i=1;i<=m;i++){   //添加链表的元素
            add((T)(i+""));
        }
        //进行加环处理
        Node1 node=getNode(0);
        Node1 node1=getNode(this.size-1);
        node1.next=this.head.next;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    8.5约瑟夫问题

    进行自杀操作，一共m个人，没间隔n个，那么就第n个人进行自杀操作。

        public void SolveYsf (int m,int n){
        //建立一个链表
        for(int i=1;i<=m;i++){   //添加链表的元素
            add((T)(i+""));
        }
        //进行加环处理
        Node1 node=getNode(0);
        Node1 node1=getNode(this.size-1);
        node1.next=this.head.next;
        //开始处理约瑟夫问题
        Node1 target=this.head.next;
        int cn=1;
        while(target!=target.next){
            //获取前一个元素
            Node1 prev=target;  //获取中间元素的前一个位置
            //游标进行后移
            target=target.next;  //获取中间元素
            //计算
            cn++;
            if(cn==n){  //假如说cn=指定的n，那么就自杀
                System.out.println("需要移除的元素是:"+target.item);
               prev.next=target.next;  //把中间元素的前一个元素指向中间元素后一个元素
                target=target.next;   //把中间元素指向中间元素的后一个元素.
                cn=1;
            }
        }
        System.out.println("保留的元素是:"+target.item);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    在这里插入图片描述

    9.双向链表:

    9.1双向链表结点的定义：

    private class Node1 {   //设置结点
    T item;    //数据域
    Node1 next;   //指针域Node1 prev;
        Node1 prev;
       public Node1(Node1 prev,T item, Node1 next) {
           this.item = item;
           this.next = next;
           this.prev=prev;
       }
   }//调用节点类

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    9.2双向链表添加末尾元素:

    在这里插入图片描述

      public void add(T t){
        //先把插入点的prev指针指向前一个last
        Node1 prev=last;
        //获取插入的元素
       Node1 node1=new Node1(prev,t,null);
       //然后把插入点前的next指针指向插入点的结点
        if(prev==null){   //假如说插入点的前一个点是null
            first=node1;
        }
        else {
            prev.next = node1;
        }
        //将last指向新插入的元素
        last=node1;
        //进行++操作
       this.size++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    9.3获取双向链表的结点:

      public Node1 getNode(int idex){
           int mid=size/2;  //获取中间值
           if(idex<mid){  //如果小于，那么就从第一个节点开始遍历
               Node1 x=first;
               for(int i=0;i<idex;i++){
                   x=x.next;
               }
               return x;
           }else{     //否则，那么就从最后i一个结点遍历
               Node1 x=last;
               for(int i=size-1;i>idex;i--){  //这里可不能少
                   x=x.prev;
               }
               return x;
           }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    9.4向指定位置添加元素

    在这里插入图片描述

       public void add(int idex,T t){
        if(idex==size){//假如说是最后一个位置
            add(t);
        }else{
        //获取需要插入元素的结点
        Node1 node1=new Node1(null,t,null);
        //获取被插入点的结点
        Node1 current=getNode(idex);
        if(current==null){
            first=node1;
        }else {
            //获取被插入点前的结点
            Node1 befor = current.prev;
            //插入点prev指向前结点
            node1.prev=befor;
            //插入点next指向后一个结点
            node1.next=current;
            //后一个结点prev指向插入点
            current.prev=node1;
            //假如说是第一个位置
            if(befor==null){
                first=node1; 
            }
            else {
                befor.next = node1;
            }
        }
            this.size++;
    }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    9.5删除元素

    在这里插入图片描述

       public void remove(int idex) {
        //设置删除点
        Node1 current = getNode(idex);
        //删除点前面
        Node1 before = current.prev;
        //删除点后面
        Node1 after = current.next;
        if(before==null){  //假如说删除头部
            first=after;
        }else{
        before.next = after;}
        if (after == null) {  //假如说删除末尾
            last = before;
        } else {
            after.prev = before;
        }
        this.size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    9.双向链表的全部用法

    类方法:

    import org.jetbrains.annotations.NotNull;

public class LinkedList<T> {
    Node1 first;  //指向第一个结点
    Node1 last; //指向最后一个结点
    int size;   //链表长度

    public LinkedList() { //初始化链表
        this.size = 0;
    }

    //获取指定位置的结点
    public Node1 getNode(int idex) {
        int mid = size / 2;  //获取中间值
        if (idex < mid) {  //如果小于，那么就从第一个节点开始遍历
            Node1 x = first;
            for (int i = 0; i < idex; i++) {
                x = x.next;
            }
            return x;
        } else {     //否则，那么就从最后i一个结点遍历
            Node1 x = last;
            for (int i = size - 1; i > idex; i--) {  //这里可不能少
                x = x.prev;
            }
            return x;
        }
    }

    //在指定位置添加元素
     public void add(int idex,T t){
        if(idex==size){//假如说是最后一个位置
            add(t);
        }else{
        //获取需要插入元素的结点
        Node1 node1=new Node1(null,t,null);
        //获取被插入点的结点
        Node1 current=getNode(idex);
        if(current==null){
            first=node1;
        }else {
            //获取被插入点前的结点
            Node1 befor = current.prev;
            //插入点prev指向前结点
            node1.prev=befor;
            //插入点next指向后一个结点
            node1.next=current;
            //后一个结点prev指向插入点
            current.prev=node1;
            //假如说是第一个位置
            if(befor==null){
                first=node1; 
            }
            else {
                befor.next = node1;
            }
        }
            this.size++;
    }
    }
    //获取指定位置的元素
    public T get(int idex) {
        return getNode(idex).item;
    }

    //在末尾元素进行添加
    public void add(T t) {
        //先把插入点的prev指针指向前一个last
        Node1 prev = last;
        //获取插入的元素
        Node1 node1 = new Node1(prev, t, null);
        //然后把插入点前的next指针指向插入点的结点
        if (prev == null) {   //假如说插入点的前一个点是null
            first = node1;
        } else {
            prev.next = node1;
        }
        //将last指向新插入的元素
        last = node1;
        //进行++操作
        this.size++;
    }

    //在指定位置进行删除
    public void remove(int idex) {
        //设置删除点
        Node1 current = getNode(idex);
        //删除点前面
        Node1 before = current.prev;
        //删除点后面
        Node1 after = current.next;
        if(before==null){  //假如说删除头部
            first=after;
        }else{
        before.next = after;}
        if (after == null) {  //假如说删除末尾
            last = before;
        } else {
            after.prev = before;
        }
        this.size--;
}
    //获取当前链表的长度
    public int size(){
        return size;
    }

    private class Node1 {   //设置结点
    T item;    //数据域
    Node1 next;   //指针域Node1 prev;
        Node1 prev;
       public Node1(Node1 prev,T item, Node1 next) {
           this.item = item;
           this.next = next;
           this.prev=prev;
       }
   }//调用节点类
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118

    主方法:

    import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
import java.lang.Math;
public class hello {
    public static void main(String []avgs) {
     LinkedList<String> s=new LinkedList<>();
        s.add("aa");
        s.add("bb");
        s.add("cc");
        s.add("dd");
       s.add("ee");
       s.remove(4);
        for(int i=0;i<s.size();i++){
            System.out.println(s.get(i));
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    在这里插入图片描述

  • 相关阅读:
    小程序如何设置自取规则
    【C语言】【数据存储】用%u打印char类型？用char存128？
    将视频中的语音转换为文字：使用Python实现自动字幕
    C++学习：动态内存分配new
    【C语言】字符串逆序
    java集合
    「POJ 3666」Making the Grade 题解（两种做法）
    ubuntu 上vscode gdb可视化源码调试live555
    [附源码]计算机毕业设计天狗电子商城系统Springboot程序
    发力“创新宇宙”，酒店集团如何破局商业革新？
  • 原文地址：https://blog.csdn.net/qq_69683957/article/details/126673359