✨hello，进来的小伙伴们，你们好耶！✨
🍊🍊系列专栏：【数据结构与算法】
🌯🌯本篇内容：初始LinkedList与链表，链表的概念，结构，基本实现，详细全面介绍！
🍼🍼作者简介：一名大三在读的科班Java编程小白，我很平凡，学会努力！
🍬🍬码云存放仓库gitee：https://gitee.com/king-zhou-of-java/java-se.git
一、ArrayList的缺陷
通过上篇博客的学习，我们可以通过ArrayList的源码了解到，ArrayList底层使用数组来存储元素。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// ...
// 默认容量是10
private static final int DEFAULT_CAPACITY = 10;
//...
// 数组：用来存储元素
transient Object[] elementData; // non-private to simplify nested class access
// 有效元素个数
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
因为其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低。因此：java集合中又引入了LinkedList，即链表结构。
二、链表
1、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
即我们可以通俗的理解为比如火车的车厢，没有给这些车厢连接起来，他们只是普通的车厢，互相之间没有任何联系，通过任意一节车厢我们无法确定下一节车厢，那么给他们连接起来组成一列火车的车厢，那么就可以是看做一种链表的结构。
那么在实际的应用中，链表的结构也是多样的。
1.带头或者不带头。
2.单向或双向。
3.循环或非循环。
那么这些组合起来就有8种链表结构，那么我们需要重点掌握的就2种：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表 。
2、链表的实现
接下来我将模拟链表的功能实现，借助我们的idea工具来演示！
具体的实现细节都在我的代码注释中标明，大家有不懂的可以评论区或者私信我都可以的！
1.首先我们新建一个包LinkedList。
2.然后我们定义我们的实现类MySingleList，在这个类当中定义一个节点内部类ListNode，当然这个类也可以是静态的都没有什么问题，在这个类当中呢，我们定义成员变量val，和节点next。
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
3、OK那么接下来我们先创建我们的链表。
public ListNode head;//不初始化了 默认就是null
public void createList() {//最简单的方式 穷举
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;//当前节点存储下一个元素的地址
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
看一下结果：说明我们链表创建成功了！
4.接下来我们打印这个单链表。
public void display() {
ListNode cur = this.head;//head不变 让我们的头结点不变 cur去变
while (cur != null) {
/**
为什么是判断cur不等于空 而不是判断cur.next不为空
我们可以打印出最后一个元素 否则提前判断 不能遍历到最后一个元素
*/
System.out.print(cur.val+" ");
cur = cur.next;
}
}
运行结果：
5.计算单链表的长度。
public int size(){
ListNode cur = this.head;
int count =0;
while(cur!=null){//可不敢写成cur.next！=null 如果链表为空的话 那么cur.next就会发生空指针异常 报错
count++;
cur = cur.next;
}
return count;
}
运行结果：
