52.【Java 数据结构——线性表】_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