目录

链表

碎片化：

内存碎片产生的原因

如何避免内存碎片？

链表类型

单链表

双链表

单循环链表

双循环链表

java是如何创建链表的？

类与对象

类是什么？

什么是对象？

构建链表

头指针

简画内存图：

 ​编辑

尾插法 

头插法

输出链表的长度

输出链表的值

---

链表

为什么会有链表？

        目的是为了解决碎片化空间的利用。

数组本质上是一块连续的空间，链表是不连续的。

---

碎片化：

        内存碎片是指已经分配的内存块之间出现未被利用的空间，这种空间会导致内存利用率降低，从而影响系统的性能和稳定性。

---

内存碎片产生的原因

主要有以下几种：

• 频繁的内存分配和释放：由于内存分配和释放不均衡，容易导致一些小的碎片
• 不同大小的内存分配：当系统中分配的内存大小不一致时，也会导致碎片
• 内存对齐的问题：当内存分配时没有对齐，也会导致碎片

---

如何避免内存碎片？

可以采用以下策略：

1. 内存池：使用内存池可以减少频繁的内存分配和释放，从而避免碎片的产生。
2. 统一内存分配方式：使用相同的内存分配方式可以避免不同大小的内存分配。
3. 对齐内存分配：通过对齐内存分配，可以减少内存碎片的产生。
4. 使用内存压缩算法：内存压缩算法可以将内存中的碎片进行整理，从而减少碎片。
5. 避免内存泄漏：内存泄漏会导致一些内存无法释放，也会导致碎片的产生。

---

链表类型

单链表

双链表

单循环链表

双循环链表

---

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(",");}elseSystem.out.println("]");flag=flag.next;}}