Java数据结构总结

忘是亡心i 2022-05-17 09:55 170阅读 0赞

**Java数据结构总结**

1.数组

1.1练习题

模拟生活中数据的存储(存储班上每个同学的信息)(增删改查操作).

1):保存一个同学的信息.

2):删除一个同学的信息.

3):更改某一个同学的信息.

4):查询某一个同学的信息.

5):查询多个同学的信息.

package day17.data;

public class Student \{

//属性

private String name;

private int age;

public String getName() \{

return name;

public void setName(String name) \{

this.name = name;

public int getAge() \{

return age;

public void setAge(int age) \{

this.age = age;

public Student() \{

// TODO 自动生成的构造函数存根

public  Student(String name,int age) \{

this.name=name;

this.age=age;

package day17.data;

import java.util.Arrays;

public class ArrayDemo \{

//保存学员信息

public static void addStudent(Student stu,Student\[\]arr) \{

//保存数据

//1.遍历数组

for (int i = 0; i < arr.length; i++) \{

Student student = arr\[i\];

//判断stu是否为空

if (student==null) \{

arr\[i\]=stu;

break;

//修改学员信息

public static void editStudent(int index,Student\[\]arr,String name) \{

//通过下标取出需要修改的学员对象

Student stu=arr\[index\];

//判断stu是否为空

if (stu!=null) \{

//修改名字

stu.setName(name);

//查询学员信息，通过下标

public static Student searchByIndex(int index,Student \[\]arr) \{

return arr\[index\];

//查询学员信息，通过名字

public static Student searchByName(String name,Student \[\]arr) \{

//遍历数组中所有对象

for (Student student : arr) \{

if (student!=null) \{

if (student.getName().equals(name)) \{

return student;

//没找到

return null;

//查询所有信息

public static void list(Student\[\]arr) \{

for (int i = 0; i < arr.length; i++) \{

Student student = arr\[i\];

if (student!=null) \{

System.out.println(student.getName()+"\\t"+student.getAge());

//通过下标删除指定学员信息

public static Student\[\] deleteByIndex(int index,Student \[\]arr) \{

for (int i = 0; i < arr.length; i++) \{

//判断i>=index

if (i>=index&&i<arr.length-1)\{

arr\[i\]=arr\[i+1\];

return Arrays.copyOf(arr, arr.length-1);

public static void main(String\[\] args) \{

//声明一个数组

Student \[\]arr=new Student\[10\];

addStudent(new Student("葬剑灬尊",21), arr);

addStudent(new Student("一叶知秋",21), arr);

addStudent(new Student("浪子一秋",21), arr);

addStudent(new Student("剑侠情缘",21), arr);

//通过下标查找

System.out.println(searchByIndex(1, arr).getName()+"\\t"+searchByIndex(1, arr).getAge());

//通过名字查找

System.out.println(searchByName("浪子一秋", arr).getName()+"\\t"+searchByName("浪子一秋", arr).getAge());

//修改信息

editStudent(3, arr, "君子好逑");

System.out.println("----------删除前---------");

list(arr);

System.out.println("----------删除后---------");

//删除信息

deleteByIndex(0, arr);

//查找全部

list(arr);

输出结果：

![70][]

1.2练习题

假设我现在是球队的教练,我需要安排上场的球员(安排5个).

模拟数据存储的案例,模拟上场球员的球衣号码的存储:

Integer\[\] players = null;

作为一个教练,要安排上场:

1):初始容量为5的线性列表,准备用来存储场上的5个球衣号码.

2):安排5个球员上场:\[11,22,33,44,55\].

3):查询指定位置的球员的球衣号码是多少.查询索引位置为2的球衣号码是:33.

4):根据球衣号码查询该球员在场上的索引位置. 44球衣号的球员在场上的索引位置是:3.

5):替换场上索引位置为2的球员,替换之后该位置的球衣编号为333. 333把33替换了.

6):替换球衣号码为22的球员,替换之后为222.

7):把场上索引位置为2的球衣罚下场(注意:罚下,没有补位.).

8):按照球员在场上的位置,打印出球衣号码,打印风格:\[11,22,33,44,55\].

package day17.test;

import java.util.Arrays;

public class Coach \{

//属性

private Integer\[\]players=new Integer\[5\];

//添加号码

public void addNumber(int num) \{

//保存数据

for (int i = 0; i < players.length; i++) \{

Integer integer = players\[i\];

if (integer==null) \{

players\[i\]=num;

break;

\}else if (i==players.length-1) \{

//扩容

players=Arrays.copyOf(players, players.length+5);

//通过下标查找

public Integer seachByIndex(int index) \{

return players\[index\];

//通过元素查找

public int seachByNumber(int numbe) \{

//遍历数组

int index=0;

for (Integer integer : players) \{

if (integer!=null) \{

if (integer==numbe) \{

return index;

index++;

return -1;

//替换  通过下标

public void replacePlayerByIndex(int index,Integer number) \{

players\[index\]=number;

//替换 通过元素

public void replacePlayersByNumber(int num,int number) \{

for (int i = 0; i < players.length; i++) \{

Integer integer = players\[i\];

if (integer==num) \{

players\[i\]=number;

//删除

public void deletePlayers(int index) \{

for (int i =index; i < players.length; i++) \{

if(index<=i&&i<players.length-1)\{

//将后边的元素往前边来放

players\[i\]=players\[i+1\];

players =Arrays.copyOf(players, players.length-1);

//转换

public void transformat() \{

System.out.print("\[");

for (int i = 0; i < players.length; i++) \{

Integer integer = players\[i\];

if (integer!=null) \{

System.out.print(integer+" ");

System.out.println("\]");

public static void main(String\[\] args) \{

// 初始化对象

Coach coach=new Coach();

//添加

coach.addNumber(11);

coach.addNumber(22);

coach.addNumber(33);

coach.addNumber(44);

coach.addNumber(55);

coach.transformat();

System.out.println("------查找--------");

System.out.println(coach.seachByIndex(1));

System.out.println(coach.seachByNumber(22));

System.out.println("------替换-------");

coach.replacePlayerByIndex(2, 333);

coach.replacePlayersByNumber(22, 222);

coach.transformat();

System.out.println("------删除后-----");

coach.deletePlayers(2);

coach.transformat();

输出结果：

![70 1][]

1.3总结

1):保存操作:

平均:  (N+1) /2 次.  N表示数组中元素的个数. 如果要扩容,更慢,性能更低.

2):删除操作:

如果删除最后一个元素,操作一次.

如果删除第一个元素,操作N次.

平均: (N+1)/2次.

3):修改操作:

根据索引查询操作1次.

根据元素修改，平均(N+1)/2次.

4):查询操作:

如果根据索引查询元素:  操作1次.

如果根据元素查询索引: 此时使用线性搜索,操作:平均: (N+1)/2次:

\-发现:基于数组的结构做查询是和修改是非常快的,但是做保存和删除操作比较慢了.

2.链表

![70 2][]

2.1单链表

只能从头遍历到尾/只能从尾遍历到头.

package day18.data;

//节点类

class Node\{

//指向下个节点的引用

Node next;

//数据部分

String name;

int age;

//构造方法

public Node() \{

// TODO 自动生成的构造函数存根

public  Node(String name,int age) \{

this.name=name;

this.age=age;

@Override

public String toString() \{

// TODO 自动生成的方法存根

System.out.println("姓名："+name+"\\t\\t年龄："+age);

return super.toString();

public class LinklistDemo \{

//操作链表  增删查改

//声明一个头部节点

Node head=null;

//添加节点

public void addNode(Node node) \{

//1.判断头部节点是否为空

if (head==null) \{

//将头部指向node

head=node;

return;

//2.判断判断节点的下个节点是否为空

Node tmp=head;//把head赋值给一个临时变量

Node pre=null;//记录上个节点

while (tmp!=null) \{

pre=tmp;

//遍历下个节点

tmp=tmp.next;

//如果为空，把最新的节点赋值给当前node的下个节点

pre.next=node;

//删除节点

public void deleteNode(String name) \{

//将头部节点赋值给tmp

Node tmp=head;

//声明上个节点

Node pre=null;

//判断节点是否为空

while (tmp!=null) \{

//当前节点是否是要删除的节点

if (tmp.name.equals(name)) \{

//删除节点

//判断要删除的是否为第一个节点

if (tmp==head) \{

head=head.next;

break;

//不是头部节点

pre.next=tmp.next;

//不是要删除的节点

pre=tmp;

tmp=tmp.next;

//查询  通过内容查询索引

public int queryNodeByName(String name) \{

Node tmp=head;

//遍历节点

int index=0;

while (tmp!=null) \{

index++;

if (tmp.name.equals(name)) \{

return index;

tmp=tmp.next;

return -1;

//修改

public void editNode(String name,int age) \{

Node tmp=head;

while (tmp!=null) \{

if (tmp.name.equals(name)) \{

tmp.age=age;

tmp=tmp.next;

//在指定位置添加node

public void insertNode(String name,Node node) \{

if (head==null) \{

//将头部指向node

head=node;

return;

Node tmp=head;

//遍历数组找到指定元素

while (tmp!=null) \{

if (tmp.name.equals(name)) \{

node.next=tmp.next;

tmp.next=node;

tmp=tmp.next;

//查看所有节点

public void list() \{

//遍历所有节点  从头开始

//把head赋值给一个临时变量

Node tmp=head;

//判断节点是否为空

while (tmp!=null) \{

tmp.toString();//打印数据

tmp=tmp.next;

public static void main(String\[\] args) \{

//初始化对象

LinklistDemo demo=new LinklistDemo();

//添加节点对象

demo.addNode(new Node("葬剑灬尊",21));

demo.addNode(new Node("浪子一秋",21));

demo.addNode(new Node("一叶知秋",21));

demo.addNode(new Node("剑侠情缘",21));

//打印节点

demo.list();

//删除节点

System.out.println("-----------删除-----------");

demo.deleteNode("葬剑灬尊");

demo.list();

//查询

System.out.println("--------查询----------");

int index=demo.queryNodeByName("剑侠情缘");

System.out.println(index);

//修改信息

System.out.println("--------修改------------");

demo.editNode("浪子一秋", 22);

demo.list();

//添加

System.out.println("---------添加----------");

demo.insertNode("浪子一秋",new Node("吠舞罗",21));

demo.list();

输出结果：

![70 3][]

2.2双链表

既可以从头遍历到尾,又可以从尾遍历到头.

package day18.data1;

//节点类

class Node\{

//节点

Node pre;//上个节点

Node next;//下个节点

//数据部分

String name;

int age;

public Node() \{

// TODO 自动生成的构造函数存根

public  Node(String name,int age) \{

this.name=name;

this.age=age;

@Override

public String toString() \{

System.out.println("name:"+name+"\\t\\tage:"+age);

return super.toString();

public class DoubleLinklistDemo \{

//操作双链表

//头部节点

Node head;

//尾部节点

Node foot;

//添加节点  尾部

public void addLast(Node node) \{

//找尾部

if (foot==null) \{

head=node;

foot=node;

return;

//赋值

foot.next=node;

node.pre=foot;

//foot指向最新的节点

foot=node;

//在头部添加

public void addFirst(Node node) \{

//判断head是否为空

if (head==null) \{

head=node;

foot=node;

return;

//赋值

node.next=head;

head.pre=node;

head=node;

//在指定位置添加

public void addNode(Node node,String name) \{

Node tmp=head;

while (tmp!=null) \{

if (tmp.name.equals(name)) \{

node.next=tmp.next;

tmp.next=node;

//node.pre=tmp;

tmp=tmp.next;

//打印所有信息

public void list() \{

//遍历

Node node=head;

while (node!=null) \{

node.toString();

node=node.next;

public static void main(String\[\] args) \{

// 初始化对象

DoubleLinklistDemo demo=new DoubleLinklistDemo();

//在头部添加节点对象

System.out.println("-----在头部添加------");

demo.addFirst(new Node("葬剑灬尊",21));

demo.addFirst(new Node("浪子一秋",21));

demo.addFirst(new Node("一叶知秋",21));

demo.addFirst(new Node("剑侠情缘",21));

//打印节点

demo.list();

//在尾部添加

System.out.println("--------在尾部添加----------");

demo.addLast(new Node("秦时明月",22));

demo.addLast(new Node("天行九歌",22));

demo.addLast(new Node("夜尽天明",22));

demo.list();

System.out.println("-------在指定位置添加-------");

demo.addNode(new Node("诸子百家",12), "天行九歌");

demo.list();

输出结果：

![70 4][]

2.3总结

1):增加操作:

双向链表可以直接获取自己的第一个和最后一个节点,

如果新增的元素在第一个或最后一个位置,那么操作只有1次.

2):删除操作(removeFisrt,removeLast):

如果删除第一个元素: 操作一次.

如果操作最后一个元素:操作一次.

如果删除中间的元素:

找到元素节点平均操作:(1+N)/2次.              找到节点之后做删除操作: 1次.

3):查询操作:

平均:(N+1)/2次

4):修改操作:

平均:(N+1)/2次

3.队列

/\*\*

\* 队列：先进先出  FIFO

\* 对数据增加删除居多

\* 底层的数据存储使用链表最合适

\* \*/

package day18.data2;

//队列

//声明一个节点类

class Node\{

//节点

Node pre;//上

Node next;//下

//数据

String name;

public Node() \{

// TODO 自动生成的构造函数存根

public  Node(String name) \{

this.name=name;

@Override

public String toString() \{

System.out.println("name:"+this.name);

return super.toString();

public class QueueDemo \{

//声明一个头部节点和尾部节点

Node head;

Node foot;

//在队列的头部添加节点

public void pushFirst(Node node) \{

if (head==null) \{

head=node;

foot=node;

return;

node.next=head;

head.pre=node;

head=node;

//在队列的尾部添加节点

public void pushLast(Node node) \{

//判断尾部节点是否为null

if (foot==null) \{

foot=node;

head=node;

return;

//在尾部添加节点

foot.next=node;

node.pre=foot;

//尾部指向最新的

foot=node;

//在队列的首部删除一个节点

public void popFirst() \{

//删除首部节点

head=head.next;

head.pre=null;

//在队列的尾部删除一个节点

public void popLast() \{

Node node=foot.pre;

node.next=null;

foot=node;

//查看队列中所有元素

public void list() \{

//遍历节点  从头到尾

Node node=head;

//判断node是否为null

while (node!=null) \{

node.toString();

node=node.next;

public static void main(String\[\] args) \{

//初始化对象

QueueDemo demo=new QueueDemo();

//添加数据

demo.pushLast(new Node("浪子一秋"));

demo.pushLast(new Node("一叶知秋"));

demo.pushLast(new Node("葬剑灬尊"));

demo.pushLast(new Node("秦时明月"));

demo.pushLast(new Node("天行九歌"));

demo.pushLast(new Node("三生三世"));

demo.pushLast(new Node("生生世世"));

demo.list();

//删除

demo.popFirst();

demo.popLast();

System.out.println("-----------删除------------");

demo.list();

输出结果：

![70 5][]

4.栈

/\*\*

\* 栈的特点  先进先出  FILO

\* 放数据：压栈

\* 取数据：出栈

\* \*/

package day18.data3;

//单链表实现栈

class Node\{

//节点

Node next;

//数据

String name;

public Node() \{

// TODO 自动生成的构造函数存根

public  Node(String name) \{

this.name=name;

@Override

public String toString() \{

System.out.println("name:"+this.name);

return super.toString();

public class StackDemo \{

Node head;//头结点

//压栈

public void push(Node node) \{

//每次将数据设为头结点

//让node的下个节点指向于head

node.next=head;

//把node的引用赋值给head

head=node;

//出栈

public void pop() \{

//删除头结点

//找到头结点的下个节点赋值给node

Node node=head.next;

head=node;

//等价于

//head=head.next;

//查看所有元素

public void list() \{

//从头到尾

Node node=head;

while (node!=null) \{

node.toString();

node=node.next;

//入口方法

public static void main(String\[\] args) \{

//初始化对象

StackDemo demo=new StackDemo();

//压栈

demo.push(new Node("阿里"));

demo.push(new Node("腾讯"));

demo.push(new Node("京东"));

demo.push(new Node("百度"));

demo.list();

//出栈

System.out.println("--------出栈-------");

demo.pop();

demo.list();

输出结果：

![70 6][]

5.知识框架

![70 7][]

[70]: /images/20220517/baecc76b3bb349fe8f64661396ccab2f.png
[70 1]: /images/20220517/5b527005a6a842b3b24dff482cf416a9.png
[70 2]: /images/20220517/e448688c0153406897cedf91d53217a3.png
[70 3]: /images/20220517/b576444059f543b3bd318993b11510e0.png
[70 4]: /images/20220517/65b13756263b4cfb830ab9d4811a98c1.png
[70 5]: /images/20220517/7eaa43c1022f4463b2b9b478de098938.png
[70 6]: /images/20220517/a8d14e54841d4a1d9dfdaf78234eb54f.png
[70 7]: /images/20220517/97076780198746dfb496976b8e9f7926.png