在单链表中，在偶数位插入新节点？写出算法思想以及相应的代码？

在单链表中插入新节点的算法思想是：

1.创建一个新节点，包含要插入的数据。

2.从链表的头部开始遍历链表，找到要插入位置的前一个节点。

3.将新节点的 next 指针指向前一个节点的 next 指针所指向的节点。

4.将前一个节点的 next 指针指向新节点。

下面是用 Java 实现的代码:

单向链表的插入图示：

---->[NULL]（原链表）

head

---->[1]---->[NULL]（插入后的链表）

head 1->next

图7 空链表插入一个节点

结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：

1、你要明白空链表head指向NULL就是head=NULL；

2、插入后head指向第1个节点，就是让head=1,1->next=NULL,OK这样就行了。

---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）

head 1->next 2->next 3->next n->next

---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的链表）

head 1->next 2->next x->next 3->next n->next

图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）

结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：

1、你要明白原1->next就是节点2，2->next就是节点3；

2、插入后x指向第3个节点,2指向x，就是让x->next=2->next,1->next=x。

*/

struct Node *Insert(struct Node *head, long num, struct Node *node)

{

struct Node *p1 /*p1保存当前需要检查的节点的地址*/

if (head == NULL) /*（结合图示7理解）*/

{

head = node

node->next = NULL

n += 1

return head

}

p1 = head

while (p1->num != num &&p1->next != NULL) /*p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找*/

{

p1 = p1->next/*后移一个节点*/

}

if (num == p1->num) /*找到了（结合图示8理解）*/

{

node->next = p1->next/*显然node的下一节点是原p1的next*/

p1->next = node/*插入后，原p1的下一节点就是要插入的node*/

n += 1/*节点总数增加1个*/

}

else

{

printf(" %ld not been found! ",num)

}

return head

}

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

1链表 *** 作编辑

双向链表

双向链表

线性表的双向链表存储结构：

带头结点的双向循环链表的基本 *** 作：

销毁双向循环链表L：

重置链表为空表：

验证是否为空表：

2元素 *** 作编辑

计算表内元素个数

赋值：

查找元素：

查找元素前驱：

查找元素后继：

查找元素地址：

元素的插入：

元素的删除：

正序查找：

逆序查找：

3循环链表编辑

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的 *** 作和单链表的 *** 作基本一致，差别仅仅在于算法中的循环条件有所不同。

---