目录
链表
为什么会有链表？
目的是为了解决碎片化空间的利用。
数组本质上是一块连续的空间，链表是不连续的。
碎片化：
内存碎片是指已经分配的内存块之间出现未被利用的空间，这种空间会导致内存利用率降低，从而影响系统的性能和稳定性。
内存碎片产生的原因
主要有以下几种：
- 频繁的内存分配和释放：由于内存分配和释放不均衡，容易导致一些小的碎片
- 不同大小的内存分配：当系统中分配的内存大小不一致时，也会导致碎片
- 内存对齐的问题：当内存分配时没有对齐，也会导致碎片
如何避免内存碎片？
可以采用以下策略：
- 内存池：使用内存池可以减少频繁的内存分配和释放，从而避免碎片的产生。
- 统一内存分配方式：使用相同的内存分配方式可以避免不同大小的内存分配。
- 对齐内存分配：通过对齐内存分配，可以减少内存碎片的产生。
- 使用内存压缩算法：内存压缩算法可以将内存中的碎片进行整理，从而减少碎片。
- 避免内存泄漏：内存泄漏会导致一些内存无法释放，也会导致碎片的产生。
链表类型
单链表
双链表
单循环链表
双循环链表
java是如何创建链表的？
以单链表为例：
节点：
那么首先我们面对着一个问题，- - Java是怎么创建节点的。
java是有原生的数组结构。
int[] arr=new int[5]; //内存就会开辟相应的内存空间。这就是所说的原生的数组结构。
但是java没有原生的链表结构。
java能采用对象的形式来创建节点。
类与对象
类是什么？
- 对象：对象是类的一个实例（对象不是找个女朋友），有数据和方法。例如，一条狗是一个对象，它的状态有：颜色、名字、品种；行为有：摇尾巴、叫、吃等。
- 类：类是一个模板，它描述一类对象的数据和方法。
创建java程序第一步必须创建一个类 class
编译：把 .java 文件编译成 .class 文件
运行：
源代码 二进制字节码文件
运行任何一个程序，在CPU（数据处理器）运行。
CPU 处理数据需要 0.2ns
在 磁盘 当中，查找数据需要 3-5ms.
1ms=1x10^6 ns
CPU就有大量的空闲。
磁盘中的文件想运行，优先进入内存，内存 查找数据 20 ns
磁盘会把数据扔到内存当中，
内存里的是程序，
内存会给正在运行的程序--进程开辟内存空间目的是存储数据，给CPU进行交互。
内存会给java运行的程序开辟空间：
方法区 存储 类信息。
堆 存储 对象。
虚拟机栈 控制 程序的执行。
.class文件 被加载到方法区，之后 main方法 入栈。
什么是对象？
对象是 堆 里的一块内存空间--->存储数据和方法。
Student s1=new Student();new 本身是java的一个关键字，功能就是要求在堆里开辟内存空间。
Student() ; 构造器，创建对象的时候给对象当中的数据赋初始值。
s1 对象的名称
Student 对象的类型---->决定在内存当中的存储形式。
默认任何一个类当中都有一个不显示的无参数构造器。
但是一旦你显示的创建出构造，那么那个不显示的构造器就会被覆盖！！！
构建链表
public class Node{
public int data;
public Node next;
public Node(int value){
data=value;
}
}Node: 数据类型---> 数据类型来定义数据在内存当中的形式。
int a=10; int: 1bit (符号位) 31bit (数值位)
byte a=10; byte: 1bit (符号位） 7bit数值位
float a=10.0; float:1 bit(符号位) 8bit 阶位 23bit数值位
Node node=new Node(5);
Node node=new Node();
在内存中形式一样。
类的实例，有属性和方法
java当中，等号是赋值操作，将等号后边的值（引用数据类型指向的是地址） 赋给 前边的变量。
node1.next=node2;内存图解释：
这种方法创建链表难。
一般建一个类构建链表。
public class LinkedList{
public void EndInsert(int val){
}
}头指针
--节点一定是对象
传参只需要传head就行，因为head指向下一个节点，下一个节点指向下一个节点。
public class LinkedList{
Node head=null;
public void EndInsert(int val){
//创建新节点
Node newNode=new Node(val);
//判断头指针指向为空，那么头指针指向第一个节点
if(head==null){
head=newNode;
return ; //必须写，不然得陷入死循环
}
Node preNode=head;
while(preNode.next!=null){
preNode=preNode.next;
}
preNode.next=newNode;
}
}public class Test{
public static void main(String[] args){
LinkedList linkedlist=new Linkedlist();
linkedList.EndInsert(1);
linkedList.EndInsert(2);
linkedList.EndInsert(3);
linkedList.EndInsert(4);
}
}简画内存图：
尾插法
将当前节点插入到链表的尾部。
游标，指针。
读代码就是读内存图示
代码见上。
public class LinkedList{
Node head=null;
public void EndInsert(int val){
//创建新节点
Node newNode=new Node(val);
//判断头指针指向为空，那么头指针指向第一个节点
if(head==null){
head=newNode;
return ; //必须写，不然得陷入死循环
}
Node preNode=head;
while(preNode.next!=null){
preNode=preNode.next;
}
preNode.next=newNode;
}
}头插法
public class LinkedList{
Node head=null;
public void HeadInsert(int val){
//创建新节点
Node newNode=new Node(val);
//判断头指针指向为空，那么头指针指向第一个节点
if(head==null){
head=newNode;
return ; //必须写，不然得陷入死循环
}
newNode.next=head;
head=newNode;
}
}输出链表的长度
//输出链表的长度
public int Length() {
Node flag=head;
int count=0;
while(flag!=null) {
count++;
flag=flag.next;
}
return count;
}输出链表的值
//输出链表值
public void Value() {
Node flag=head;
System.out.print("[");
while(flag!=null) {
System.out.print(flag.data);
if(flag.next!=null) {
System.out.print(",");
}else
System.out.println("]");
flag=flag.next;
}
}