Java中链表的深入了解及实现

一、链表

1.链表的概念

1.1链表是⼀种物理存储结构上⾮连续存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的

实际中链表的结构⾮常多样，以下情况组合起来就有8种链表结构：

2.链表的实现

1.⽆头单向⾮循环链表实现

链表中的方法用接口来实现，代码如下：

1.1实现内部类

这处地代码有利于节点的构造和引用

1.2 addFirst方法的逻辑和实现

1.3disPlay方法的实现

注意：循环的结束语不能是cur.next, 如果是cur.next那么一开始add进去的val不会被打印出来

1.4addLast方法的实现

1.5contains方法的实现

这里的cur起到复制head使头节点不变动，不过要注意的是这个循环语不能是cur.next，如果是这个的话，最后的尾节点的val就不会判断出来，查找时会是false，要注意的是：在链表的循环中cur是要重新赋予地址的，这样才能保证在循环的时候不会出现空间报错和访问异常

1.6 size方法的实现

计入链表的大小我们需要定义一个count来计入它的大小，并通过循环来给count++来实现链表的真实大小，不过要注意的是循环语还是之前的那个，这里就不多讲来，最后返回链表的大小

1.7claer方法的实现

这里我们可以直接把头节点置为空就可以达到清除的效果，但是不建议，这里我们需要用到循环，同时在这个循环内部要定义一个新的节点来接收cur.next,这样有助于循环的继续，以防报错

1.8addIndex方法的实现

第二个框起来的方法是检查下标是否合法，这里也可以自定义报错的方法来实现

1.9remove方法的实现

1.10removeAllKey方法的实现

cur = cur.next 起到链表往下循环的作用，prev起到复制当cur.val = key时 next 的地址同时这也会往下进行循环，最后再判断一次头节点