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;
    }
}

主函数:

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]);
        }
    }

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;
    }
}

主函数:

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]);
        }
    }

*切记哈，删除和插入的是线性表=====并不是数组*

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

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

判断是否清空

 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;
    }

数组的扩容

  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 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;
    }
}

主方法:

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());
    }
}

7.单链表的全部用法

创建链表结点

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

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

对链表进行初始化

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

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

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;

    }

类文件:

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;
       }
   }//调用节点类

}

主文件:

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));
        }
    }
}

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++;
    }
    }

主方法:

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)+" ");
        }
    }
}

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;
    }

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

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

全部代码:

主方法:

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;
       }
   }//调用节点类

}

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;
    }

8.3指定点循环链表的建立

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

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;

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);
    }

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;
       }
   }//调用节点类

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++;
    }

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;
           }
    }

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++;
    }
    }

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--;
}

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;
       }
   }//调用节点类
}

主方法:

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));
        }
    }
}

文章来源地址https://www.toymoban.com/news/detail-828460.html

到了这里，关于52.【Java 数据结构——线性表】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！