插入和删除的灵活度，你有他强么?

【威哥说】威哥在此和小伙伴们道歉，本来计划昨天早上给大家分享的视频，因为疏忽出现了遗漏，导致大家没有及时学习，今天不但要给大家补齐视频，同时我还和磨砺营的另外一个小伙伴甘愿自罚，以表示对大家的歉意。希望相信我以及磨砺营的小伙伴们，能够学习到更多的知识。（惩罚内容，每人罚100个俯卧撑，如图）

【正文】

链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

这是百度上的回答，那么通俗点来说，就是链表是一个不连续，没有顺序的存储结构。他们之间的连接是通过本节点中记录下一个节点的地址来保持关系的。就像铁链，每一环扣着每一环，所以名称也是由此而来。

那么解释看懂了，我们如何去实实在在的将这个存储结构在我们的代码中体现出来呢。接下来，跟着文章的思路走。

首先我们要搞清楚，我们此处的存值是通过节点进行存储，所以我们需要一个节点对象，那么通过在一个节点中保存下一个节点对象，所以我们要在一个节点中封装下一个节点的引用，并且我们是通过节点中封装属性的方法对数据进行存储的，所以此处的节点对象我们可以命名为：

private class Node{

private int data; //节点要存储的数据

private Node next; //节点内部的节点（下一个节点）

//构造方法完成初始化工作

public Node(int data){

this.data = data;

}

//定义getter 和 setter 方法

public void setData(int data){

this.data = data;

}

public int getData(){

return data;

}

}

此处我们使用内部类的方式来讲节点存储在节点管理类中，也就是说将节点类封装到我们的NodeManager中，这样对外就不直接暴露根本的节点类：

class NodeManager{

//此处保存一个根节点

private Node root;

private class Node{

private int data; //节点要存储的数据

private Node next; //节点内部的节点（下一个节点）

//构造方法完成初始化工作

public Node(int data){

this.data = data;

}

//定义getter 和 setter 方法

public void setData(int data){

this.data = data;

}

public int getData(){

return data;

}

}

}

添加方法：

首先，我们需要添加方法，此时这个方法是管理类中的，

//添加节点

public void add(int data){

//判断如果根节点为空，就存储在根节点中

if(root==null){

//新建一个节点（将要存储的数据存入进去）

root = new Node(data);

}else{

//此时我交给内部类去完成添加

root.addNode(data);

}

}

现在进入我们的节点内部的添加方法：

//Node内部的添加节点

public void addNode(int data){

//此处的this，表示当前对象，注意，谁调用此方法，this就表示谁，如果这里的下一个节点为空，就将数据通过构造方法存储起来

if(this.next==null){

this.next = new Node(data);

}else{

//此处使用了递归算法，如果检测到下一个节点有数据，就是用下一个节点的addNode方法，这时候，就可以继续我们的处理逻辑

this.next.addNode(data);

}

}

删除方法：

首先，外部管理类中的删除方法，注意此处删除有开发者可能也不太理解，这里要注意的是，这里我们可以直接指定本节点中指定的下一个节点的引用，这样遍历时就会直接略过这个没有记录的这个数据：

//删除节点

public void del(int data){

if(root.getData()==data){

root = root.next;

}else{

//进入到节点内部类的删除方法

root.delNode(data);

}

}

我们看看节点内部的删除方法，同样的我们需要使用递归来进行判断，判断到符合的节点，直接执行删除操作：

//Node内部的删除节点

public void delNode(int data){

if(this.next!=null){

if(this.next.data==data){

this.next = this.next.next;

}else{

//此处使用递归

this.next.delNode(data);

}

}

}

查询方法：

外部管理类的查询方法：

//输出所有节点

public void print(){

if(root!=null){//如果根节点不为空，就输出然后继续向下一个节点判断输出

System.out.print(root.getData()+"->");

root.printNode();

System.out.println();

}

}

节点内部中的查询方法：

//Node输出所有节点

public void printNode(){

if(this.next!=null){

System.out.print(this.next.data+"->");

this.next.printNode();

}

}

这里面涉及到一个递归算法的问题，自己调用自己，此处我们使用this关键字来表示谁调用本方法，然后来依次对数据进行灵活的判断。由于此处我们在链表中存储的是数字，所以无法对对象数据进行修改，如果你保存的是一个对象，我们可以记录一个唯一标识对象的标记，并通过此标记来对对象进行查询单个和修改操作。

此处我们也看出来了，使用链表比较利于插入和删除，因为我直接改变一下节点的引用地址即可，所以频繁做数据的插入和删除操作时，我们可以优先考虑链表