定義鏈表的類的聲明時采用模版機制宙搬，這樣雖然繁瑣一些葫掉，但為將來對鏈表的復用提供了很大的方便裆针。同時在鏈表中增加頭結(jié)點刨摩，統(tǒng)一了空表和非空表操作的實現(xiàn)寺晌，降低了程序結(jié)構(gòu)的復雜性世吨，減少了出錯的概率。

頭文件

#ifndef LINKLIST_H
#define LINKLIST_H
#include <cstddef>
#include <iostream>

/* 單鏈表的結(jié)點定義 */
template<class T>
struct LinkNode
{
    T data;
    LinkNode<T> *next;
    LinkNode(LinkNode<T> *ptr = NULL){next = ptr;}
    LinkNode(const T &item, LinkNode<T> *ptr = NULL)    
    //函數(shù)參數(shù)表中的形參允許有默認值呻征，但是帶默認值的參數(shù)需要放后面
    {
        next = ptr;
        data = item;
    }
};

/* 帶頭結(jié)點的單鏈表定義 */
template<class T>
class LinkList
{
public:
    //無參數(shù)的構(gòu)造函數(shù)
    LinkList(){head = new LinkNode<T>;}
    //帶參數(shù)的構(gòu)造函數(shù)
    LinkList(const T &item){head = new LinkNode<T>(item);}
    //拷貝構(gòu)造函數(shù)
    LinkList(LinkList<T> &List);
    //析構(gòu)函數(shù)
    ~LinkList(){Clear();}
    //重載函數(shù):賦值
    LinkList<T>& operator=(LinkList<T> &List);
    //鏈表清空
    void Clear();
    //獲取鏈表長度
    int Length() const;
    //獲取鏈表頭結(jié)點
    LinkNode<T>* GetHead() const    {return head;}
    //查找數(shù)據(jù)的位置耘婚，返回第一個找到的滿足該數(shù)值的結(jié)點指針
    LinkNode<T>* Find(T &item);
    //定位指定的位置，返回該位置上的結(jié)點指針
    LinkNode<T>* Locate(int pos);
    //在指定位置pos插入值為item的結(jié)點陆赋，失敗返回false
    bool Insert(T &item, int pos);
    //刪除指定位置pos上的結(jié)點沐祷，item就是該結(jié)點的值，失敗返回false
    bool Remove(int pos, T &item);
    //獲取指定位置pos的結(jié)點的值攒岛，失敗返回false
    bool GetData(int pos, T &item);
    //設置指定位置pos的結(jié)點的值赖临，失敗返回false
    bool SetData(int pos, T &item);
    //判斷鏈表是否為空
    bool IsEmpty() const;
    //打印鏈表
    void Print() const;
    //鏈表排序
    void Sort();
    //鏈表逆置
    void Reverse();
private:
    LinkNode<T> *head;
};

#endif

源文件

#include "LinkList.h"

//復制構(gòu)造函數(shù)
template<class T>
LinkList<T>::LinkList(LinkList<T>& L)
{
    T value;
    LinkNode<T>* srcptr = L.GetHead();
    LinkNode<T>* destptr = head = new LinkNode<T>;
    while(srcptr->next != NULL){
        value = srcptr->next->data;
        destptr->next = new LinkNode<T>(value);
        srcptr = srcptr->next;
        destptr = destptr->next;
    }
    destptr->next = NULL;
}

//將鏈表置為空表
template<class T>
void LinkList<T>::Clear()
{
    LinkNode<T>* temp = NULL;
    while(head->next != NULL){
        temp = head->next;
        head->next = temp->next;
        delete temp;
    }
}



//計算待附加頭結(jié)點的單鏈表長度
template<class T>
int LinkList<T>::Length() const
{
    int count = 0;
    LinkNode<T>* temp = head->next;
    while(temp != NULL){
        temp = temp->next;
        ++count;
    }
    return count;
}

//在表中搜索數(shù)據(jù)item的節(jié)點,搜索成功則返回該結(jié)點地址，否則返回NULL
template<class T> 
LinkNode<T>* LinkList<T>::Find(T &item)
{
    LinkNode<T>* temp = head->next;
    while(temp != NULL){
        if(temp->data == item)  break;
        else temp = temp->next;
    }
    return temp;
}

// 返回鏈表中第pos個元素的地址灾锯，如果pos<0或pos超出鏈表最大個數(shù)返回NULL
template<class T>
LinkNode<T>* LinkList<T>::Locate(int pos)
{
    int i = 0;
    LinkNode<T> *p = head;

    if (pos < 0)
        return NULL;

    while (NULL != p && i < pos)
    {
        p = p->next;
        i++;
    }
    
    return p;
}

//取出鏈表中第i個元素的值
template<class T>
bool LinkList<T>::GetData(int pos,T &item)
{
    if(pos<=0)  return false;
    LinkNode<T>* temp = Locate(pos);
    if(temp == NULL)    return false;
    else{
        item = temp->data;
        return true;
    }
} 

//給鏈表中第i個元素的賦值
template<class T>
bool LinkList<T>::SetData(int pos,T &item)
{
    if(pos<=0)  return false;
    LinkNode<T>* temp = Locate(pos);
    if(temp == NULL)    return false;
    else{
        temp->data = item;
        return true;
    }
}

//判斷鏈表是否為空
template<class T>
bool LinkList<T>::IsEmpty() const
{
    return (head->next == NULL)?true:false;
}

template<class T>
bool LinkList<T>::Insert(T &item, int pos)
{
    LinkNode<T> *p = Locate(pos);
    if (NULL == p)
        return false;

    LinkNode<T> *node = new LinkNode<T>(item);
    if (NULL == node)
    {
        std::cerr << "分配內(nèi)存失敗!" << std::endl;
        exit(1);
    }
    node->next = p->next;
    p->next = node;
    return true;
}

template<class T>
bool LinkList<T>::Remove(int pos, T &item)
{
    LinkNode<T> *p = Locate(pos);
    if (NULL == p || NULL == p->next)
        return false;

    LinkNode<T> *del = p->next;
    p->next = del->next;
    item = del->data;
    delete del;
    return true;
}


template<class T>
void LinkList<T>::Print() const
{
    int count = 0;
    LinkNode<T> *p = head;
    while (NULL != p->next)
    {
        p = p->next;
        std::cout << p->data <<std::endl;
    }
}


template<class T>
void LinkList<T>::Reverse()
{
    LinkNode<T> *pre = head->next;
    LinkNode<T> *curr = pre->next;
    LinkNode<T> *next = NULL;

    head->next->next = NULL;
    while (curr)
    {
        next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    head->next = pre;
}