单链表和双链表

介绍

​ 任何数据结构从内存结构来分只有两种：紧密结构，比如数组，要么是跳转结构

跳转结构就是，有一个数据是Node里面记了一个value值还有记载下一个的地址的指针。

单链表就是记录了下一个节点的地址，双链表就是记录了上一个节点的地址和下一个节点的地址。

image-20230509103310037

经典问题1：单链表反转

什么是反转？

image-20230517210436690

首先这是一个正常的链表，有a节点，b节点，c节点，c节点指向空，空是一个特定的地址，虚拟机JVM里面特定的一个值（后面再更新JVM）。

然后在内存里我给你一个头节点Head指向a节点的内存区域，反转时是把链表逆序

变成这样。image-20230517210823593

那么怎么实现呢？

单链表反转原理：

首先理清一件事情：Head如果在反转之后，还是指向a，JVM在这时候会将B,C节点释放，因为没有任何方法找到B,C了，JVM会认为是垃圾空间会将其释放。

image-20230517211058254

所以要怎么做呢？

利用Head=f(Head)，f()函数的作用就是将其逆序然后返回最后一个节点的地址传给Head，也就是将链表逆序，然后返回C的地址给Head.

详细流程