单向链表操作总结

1.  有可能会改变链表第一个元素的任何子函数都必须把一个指针传递给头指针。

 

2.  在遍历链表的时候，千万不要忘记检查自己是否已经到达了它的末尾。

 

3.  如果要在单向链表中删除或插入一个元素，就必须知道指向删除点或插入点前面那个元素的指针才行。

 

4.  单向链表的元素删除操作至少要使用两个指针才能正确完成。事实上，单向链表的元素插入操作也需要两个指针才能正确完成，它们一个负责给出插入点在链表中的位置，另一个则指向由内存分配调用返回的新元素；只是人们在进行插入操作时很少会像在进行删除操作时那样忘记需要使用两个指针而已。

 

5.  当遇到长度为0、1、2个元素的链表时，必须采取一些特殊处理才能保证有关操作能够正确地完成。

 

int Delete(element *elem) {
       element *curPos = head;

       if (!elem)
              return 0;
 
       if (elem == head) {
              head = elem->next;
              free(elem);

              /* special case for 1 element list */
              if (!head)
                     tail = NULL;

              return 1;
       }
 
       while (curPos) {
              if (curPos->next == elem) {
                     curPos->next = elem->next;
                     free(elem);

                     if (curPos->next == NULL)
                            tail = curPos;

                     return 1;
              }
              curPos = curPos->next;
       }
       return 0;
}


int InsertAfter(element *elem, int data) {
       element *newElem, *curPos = head;

       newElem = (element *)malloc(sizeof(element));
       if (!newElem)
              return 0;

       newElem->data = data;

       /* Insert at beginning of list */
       if (!elem) {
              newElem->next = head;
              head = newElem;
 
              /* special case for empty list */
              if (!tail)
                     tail = newElem;

              return 1;
       }

       while (curPos) {
              if (curPos == elem) {
                     newElem->next = curPos->next;
                     curPos->next = newElem;    

                     /* special case for inserting at end of list */
                     if (!(newElem->next))
                            tail = newElem;

                     return 1;
              }
              curPos = curPos->next;
       }

       /* Insert position not found; free element and return failure */
       free(newElem);

       return 0;
}