[科普中国]-尾指针

尾指针是另外一种链表的技巧是使用尾指针，是相对于头指针而言的，形式与头指针相同，内容指向链表的最后一个节点。

介绍通常，链表的插入语删除操作都是在链表头或者链表尾进行。如果只保存一个头指针的话，要在链表尾操作时必须先遍历整个表，增加了时间复杂度，如果能再保存一个尾指针1，则可以立即找到链表尾，时间复杂度降为O(1)。

在单向循环链表中，时常值保存一个尾指针，因为尾指针的下一个节点即是头结点。这样便可以方便地在首尾进行操作。

代码提供一个带头结点和尾指针的单链表插入实现参考代码。

#include #include #define ElementType intstruct ListNode{ ElementType Element; struct ListNode *Next;};typedef struct{ struct ListNode *Head; struct ListNode *Tail;} List, *pList;int InsertTail( ElementType X, pList L ) //尾部插入元素{ struct ListNode *newP; if ( (newP = malloc(sizeof(struct ListNode))) == NULL ) { perror("OUT OF SPACE!"); return -1; } newP->Element = X; newP->Next = NULL; L->Tail->Next = newP; L->Tail = newP; if ( L->Head->Next == NULL) { L->Head->Next = L->Tail; } return 0;}int InsertHead( ElementType X, pList L ) //头部插入元素{ struct ListNode *newP; if ( (newP = malloc(sizeof(struct ListNode))) == NULL ) { perror("OUT OF SPACE!"); return -1; } newP->Element = X; newP->Next = L->Head->Next; L->Head->Next = newP; return 0;} int main(){ pList L; if ( (L = malloc(sizeof(List))) == NULL ) { perror("OUT OF SPACE!"); return -1; } if ( (L->Head = malloc(sizeof(struct ListNode))) == NULL ) { perror("OUT OF SPACE!"); return -1; } L->Head->Next = NULL; //初始化 L->Tail = L->Head; InsertTail( 10, L ); InsertTail( 11, L ); InsertTail( 12, L ); //三次尾部插入 InsertHead( 13, L ); InsertHead( 14, L ); //两次头部插入 InsertTail( 15, L ); InsertTail( 16, L ); //两次尾部插入 while( L->Head->Next != NULL ) //遍历输出 { printf("%d ", L->Head->Next->Element); L->Head = L->Head->Next; } puts(""); return 0;}运行结果

jimmy@MyPet:~/code/learnc$ makegcc -Wall -g -o test test.c -std=c99jimmy@MyPet:~/code/learnc$ ./test 14 13 10 11 12 15 16本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学