尾指針

尾指針是相對於頭指針而言的，形式與頭指針相同，內容指向鍊表的最後一個節點。

基本介紹

• 中文名：尾指針
• 套用：數據結構

介紹

通常，鍊表的插入與刪除操作都是在鍊表頭或者鍊表尾進行。如果只保存一個頭指針的話，要在鍊表尾操作時必須先遍歷整個表，增加了時間複雜度，如果能再保存一個尾指針，則可以立即找到鍊表尾，時間複雜度降為O(1)。

在單向循環鍊表中，時常只保存一個尾指針，因為尾指針的下一個節點即是頭結點。這樣便可以方便地在首尾進行操作。

代碼

提供一個帶頭結點和尾指針的單鍊表插入實現參考代碼。

#include <stdio.h>
#include <stdlib.h>
#define ElementType int
struct 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$ make
gcc -Wall -g -o test test.c -std=c99
jimmy@MyPet:~/code/learnc$ ./test 
14 13 10 11 12 15 16