1.2.3 链表的基本操作

链表的基本操作包括向链表中插入节点和从链表中删除节点，另外根据实际需要可以定义获取链表长度、销毁链表等操作。

向链表中插入节点

向链表中插入节点函数的定义如下。

这个函数表示在链表的第index个位置上插入一个整型变量data节点。在实现该函数之前，有两点需要特别注意。

（1）参数data指链表节点中的元素值而不是节点对象。因为我们定义的链表节点Node中的数据域是int类型，所以参数data也是int类型。

（2）参数index表示要将节点插入链表中的位置。与数组元素的位置相似，我们规定index只能是从1（包含）到length+1（包含）之间的值，其他的值都是非法的。

如图1-17所示，在链表的第1个位置上插入节点指将新节点插入链表中并使其位于链表的第1个位置；同理，在链表的第6个位置上插入节点指将新节点插入链表中并使其位于链表的第6个位置。不难理解，当一个链表的长度为length时，插入一个节点后其长度将变为length+1，所以新插入的节点只可能位于该链表的第1～length+1个位置上，在其他的位置上必然是非法的。

如何在链表的第index个位置上插入一个节点呢？可以依照下面的步骤进行。

（1）首先通过一个循环操作找到要插入位置的前一个节点，并用指针p指向该节点。如图1-18所示。

如图1-18所示，假设要在链表的第3个位置上插入一个新节点，首先要找到链表中的第2个节点，并用指针p指向该节点。

（2）创建一个新的节点，将节点元素赋值为6（data），同时用指针node指向该节点，如图1-19所示。

（3）将p所指节点的next域的值（即p的后继节点指针）赋给node节点的next域。

（4）再将node赋值给p节点的next域，如图1-20所示。

如图1-20所示，通过步骤（3）和步骤（4），节点插入p节点和p节点的后继节点之间。

注意，如果要在链表的第1个位置上（index=1）插入节点，那么因为第1个位置上之前并没有节点而只有一个头指针head，所以步骤（3）、步骤（4）不再适用。这里需要考虑两种情况。

（1）如果head==null，则说明链表是一个空链表，没有任何节点，此时将步骤（2）生成的新节点node赋值给head即可，这样head就指向了链表的第1个节点。

（2）如果head！=null，则说明链表中已存在节点，此时将head（即原链表中的第1个节点的引用）的值赋给node节点的next域，再将node赋值给head即可，如图1-21所示。

下面给出向链表中插入节点的Java代码描述。

相信大家注意到了，在插入节点成功后，成员变量length的值会加1，这样每次需要得到链表的长度时直接读取length值就可以了。当然也可以通过遍历链表的方法获取链表的长度，但是效率较低，其时间复杂度为O（n）。

链表是一种动态的数据结构，可以随时在其中插入节点或删除节点，所以链表的长度是不断变化的。如果我们在插入、删除的过程中随时修改length值，让length始终记录链表当前的长度，那么在获取链表的长度时就不需要重新遍历整个链表了，直接返回length值即可，效率就会高很多，其时间复杂度为O（1）。所以在设计算法时，应根据数据结构自身的特性选择性能最佳的方法。

从链表中删除节点

下面介绍如何从一个非空链表中删除指定位置的节点。前面已经给出了删除链表中index位置上的节点的函数定义。

这个函数表示将链表中第index个位置上的节点删除。在实现该函数之前，首先需要明确什么叫将链表中第index个位置上的节点删除。

如图1-22所示，删除链表中index=3的节点就是将链表中的第3个节点移除，使其前驱节点与后继节点直接连接。删除成功后，链表的长度减1。很显然，index的取值范围是从1（包含）到length（包含），其他的值都是非法的。

删除步骤如下。

（1）首先通过一个循环操作找到要删除节点的前一个节点（前驱节点），并用指针p指向该节点，如图1-23所示。

（2）执行“p.next=p.next.next；”语句完成删除节点的操作，如图1-24所示。

另外，如果要删除的节点是链表中的第1个节点，即index=1，则需要特殊处理。因为index=1的节点前面没有其他节点，所以不能按照步骤（1）、步骤（2）执行。这时只需要将head.next赋值给head即可，这样head就会指向原链表第1个节点的后继节点，也就是删除了原链表中的第1个节点，如图1-25所示。

下面给出从链表中删除节点的Java代码描述。

向链表中插入节点和从链表中删除节点是链表的最基本操作，除此之外，我们还可以根据需要定义其他操作。在后面的实战演练中会有更多关于链表的操作方法，大家可以参考学习。