对于单向链表常见的操作有链表结点数据的查找、插入和删除。
在单向链表中,查找目标数据,只需从head指向的表头结点出发,沿着链表顺序遍历整个链表,并一一比较各个结点数值域中的数据即可。例如,从head为头指针的单向链表中查找数值域中成员data为x的结点,可以编写成以下函数fin():
在数组的某个元素后面插入一个新的元素时,需要将该元素后面的所有元素都向后移动位置。而在链表的结点p后面插入一个新的结点,不必像数组那样移动后面的结点,只要将p的后继指针指向新的结点,并将新结点的后继指针指向p原来的后继结点即可(见图(a))。例如,在单向链表的p结点后面插入一个数值域成员data的值为x的新结点,可以编写成以下函数ins():
在单向链表中,要删除指针p指向的结点,只要将其前面一个结点(前驱结点)的后继指针指向p后面的结点(后继结点),并释放p所占用的内存即可(见图(b))。例如,从head为头指针的单向链表中删除p指向结点,可以编写成以下函数del():
图 单向链表的插入和删除操作