Java初级数据结构链表的实现(单向链表)（工程文件后续会上传至博客）_链表java实现

1.链表简介

1.1顺序表的优缺点

（1）顺序表中插入和删除元素都需要移动元素，不好插入和删除。如果元素太多要再加一个那么就会扩容，会产生空间的浪费。（扩容要拷贝数据要消耗时间）

（2）比较好的是可以快速查找到对应的元素，时间复杂度是O（1）

1.2链表的引出

（1）为了解决顺序表插入和删除的麻烦，可以让我们随意插入删除，不挪动元素呢？

（2）这时候就产生了链表这个数据结构来对这个问题进行解决

（3）链表可以理解为一个火车。

（4）链表是由节点组成的，每个节点都有几个相对应的地址，每一个节点都由两个域组成，数值域VAL和next区域（数值域就是用来存数据） 

（5）节点相当于一个对象

（6）next域是用来存储下一个指向节点的地址的。这时候就像一个火车一样将节点连接起来了。

（7）链表物理（真实的内存）上不一定连续，逻辑（数学逻辑）上连续的结构。

(8)头节点是链表的第一个节点，它是用来存指向下一个的next域的地址的。(位置是不会进行变化的）

1.2.2链表的分类

带头的节点，头节点标志的是永远是一个头不会变

不带头的节点，头结点的地址会变化（在头结点的位置插入元素头节点会发生变化）

（1）单项 带头 循环

（2）单项 带头 非循环

（3）单项 不带头 循环

（4）单项 不带头 非循环（主要讲解）

（1）双项 带头 循环

（2）双项 带头 非循环

（3）双项 不带头 循环

（4）双项 不带头 非循环（主要讲解）（LinkList底层就是这个）

2.用代码实现链表

2.1链表实现前的准备工作

1.创建三个类，一个接口，两个类，Frank是测试类，Ilist是一个接口，MySingList是对链表进行实现

2.链表是由若干的节点组成的，可以将链表定义成一个内部类别。

3. 定义一个内部类ListNode

4.其中链表是由两个部分组成的，一个是next域，一个是val域，所以在内部类中定义两个变量

int类型的val来存储数据

next存的是节点的地址所以它的类型是节点类型，所以他就是一个ListNode类型

5.提供一个构造方法来对类中的val进行初初始化。

不用对next来进行初始化,因为插入进来的时候要对这个节点进行实例化，在new这个对象的时候我们并不知道这个地方的地址，所以我们不需要对next来进行赋值。所以它就是一个Null。

示例化的时候并没有给next值（图解）

6.定义一个头其中头接节点节点的类型是IlistNode类型，因为头节点的类型就是链表类

2.2链表接口中方法的具体实现

1.定义接口要实现方法

2.实现接口重写方法

3. 如何将节点串联起来？

创建可以实例化四个对象的方法

这几个对象之间是要有联系的为了能够让它们之间有联系怎么用代码实现？

（1） 要先访问node1的内存

          用node1.next = node2

          node2存储的引用变量是0x987

          这样就将他连起来了

         这时候就将一个最基本的链表完成了

（2）代码实现

 最后头节点指向node1

图解

当方法结束的时候局部变量就会被回收，所以head就记录下来了列表的头，这个过程就将这些全部遍历了（next不断的进行遍历）

具体实现

 

2.2.1.输出链表实现display方法

（1）怎么从第一个节点走到第二个节点？

    head = head.next

（2）什么时候算是把节点都遍历完成了？

     当head等于空的时候就证明把列表全部遍历完成了（链表的最后一个元素的next一定是null）

（3）代码实现

** 这样写的最后head变为空了，这样是不对的为了能够遍历完成却不影响head节点的位置、

（4）定义一个cur来等于head让cur走（这样才是对的），如果要遍历所有节点就要用这个条件cur！=null。

 2.2.2实现size方法（求当前链表多少节点）

 2.2.3实现contaibs方法（求当前列表是否存在k）

2.2.4实现头插法addFirst

  (1)头插法就是将元素插入链表的头部相当于将head指向的位置变成了这个元素的地址。

（2）不带头和带头的链表就会发现区别

（3）所以我们的目的是修改当前插入元素下一个的next以及头结点的next。

（4）代码的实现（node是我们要插入的元素）

       1) node.next = head;      2) head = node

           head = node;                  node.next = head

第一种写法：相当于先将node指向下一个元素的next，然后头节点的next指向node的next（对的）

第二种写法：相当于先让head的next指向node，这时候node的next再指向head（错误不行自己指向自己了）

所以先绑后面再绑前面

所以正确的代码写法是：

2.2.5实现尾插入法

（1）把要插入的节点放入最后节点的位置

（2）只需要在链表中找到next为空的节点然后让这个空的节点指向我们要插入的节点。

（3）如果这个链表中啥都没有，那么就让我的head等于node

头插法和尾插法都可以互相一起使用

2.2.6addindex方法（在指定的位置进行插入数值）

在1和二之间插入数据

首先我们一想到插入就可以联想成，cur往后走两步，然后形成右图的情况但是由于我们定义的是单向链表所以没有办法回退，所以这种方法也就不行了

(1) 正确的做法是：当cur走到1位置的时候，将node.next指向2位置，所以可以写出一个代码

（node.next = cur.next）

(2)这时候要将一位置的代码代码再指向node的next这时候就完美的连接在一起。所以可以写出一个代码就是

（cur.next = node）

(3)整体实现（所有的插入都是先绑后面再绑前面）

（1）这时候引出一个问题？

    如何实现这段代码？

1）找到cur的位置

     cur走index-1的步

2）如果是0位置就是头插法

3）如果是末尾就是尾插法

4）判断index是否合法如果不合法要输出异常，所以要定义一个异常

自定义异常判断index是否合法

这是一些特殊情况的插入

中间插入的情况

首先定义一个私有方法，这个方法中包含计数器count，while循环中我们首先要先获取index-1的一个的节点

获取以后就可以进行交换

这样完整的addindex方法就完成了。 

2.2.7remove方法删除给定的元素

首先要找到要删除的元素就要想如图的效果

由于是单向链表所以我们需要走到前一个位置 

将要删除的节点起名为del，我们只需要将cur。next指向del。next就可以让这个del的节点被删除

疑问？

while循环中的条件为什么不能为cur == null

答案是这样会空指针异常，在if语句中，要指向下一个，如果是这个条件的化，就会指向一个不存在的东西就会发生空指针异常。

代码实现 

这段代码是针对两种特殊情况，一种是头结点为空，另一种是只有一个元素元素就是Key

前者如果为空的化就之间终止方法

后者如果头结点是需要删除的，那么就可以将头结点指向下一个节点就会使得这个节点被删除

接下来就是正常情况来对删除操作进行处理。  

定义一个私有方法来去找key的前驱

如果cur的后驱的val的值是key那么他的前驱就是cur，要不然就让cur往后走

方法的正式实现 （return可以终止方法的继续往下）

定义了一个del作为要删除的节点

2.2.8remove方法遍历一遍将全部的相同的数字删除 

其中prev是不能动的，原因是为了防止prev的下个节点 是删除的元素

那么要全部删除这个元素就要全部将节点遍历。所以条件是cur!=null

代码的意思是如果cur的值是等于要删除的值，那么就会通过prev.next=cur.next进行删除

然后cur再往后走一格

如果没有要删除的元素的化，prev就会往后移动一格，然后cur也会往后移动一格

代码实现

如果为空就直接结束

如果是头节点是要删除的要这样做（if不能在开头，要不然会出问题，那也prev和cur就不行，万一下面一个元素也要删除就会出问题）

这道题是力扣在数据结构的经典题目

2.2.9clear方法清除所有节点

当一个节点没有被引用的时候就会被jvm进行回收

代码如下（参考多米诺骨牌）

第二种用法就是这样一个一个删除