链表的概念

链表是常用的基本数据结构之一，属于线性表。同属于线性表的还有顺序表，我们常说的数组就是顺序表。

带表头链表

链表的实现有带表头和不带表头两种方式。最原始的方式，也就是不带表头的实现方式，是用一个指向头结点的指针变量来记录链表的起始位置，当我们要进行插入或删除结点的操作时，必须要针对第一个结点和其它结点做出不同判断，然后用不同的代码来分别处理这两种情况。

所谓带表头的实现方式，就是用一个空的结点来作为头结点，其data域不放数据，其next指针指向第一个存有数据的结点。这样的好处是：每一个数据结点都有相同类型的前驱结点，不管在哪个位置实现操作，都能用统一的形式来表述，即可以用同样的代码来实现，而无需判断是在链表的起始位置、中间位置或者尾部位置。

实现思路

我们将实现链表类的几个基本方法：

• 添加结点（至链表末尾）
• 插入结点（至任意位置）
• 删除结点
• 查找结点
• 获取链表长度
• 获取结点数据
• 排序

链表类Linklist的定义部分

template <typename ElemType>
class Linklist {
    private:
        struct Node{
            ElemType data;
            Node* next;
            Node():next(nullptr){};
            Node(ElemType data, Node* next = nullptr):
                data(data), next(next){};
        };
        Node Head;

    public:
        Linklist() {};
        ~Linklist();

        void append(ElemType data);
        void insert(ElemType data, int pos = 0);
        bool del(int pos);
        int  search(ElemType data);
        int  getLength();
        ElemType getData(int pos);
        void sort(int(*compare)(ElemType& a, ElemType& b));
};

Linklist的实现部分

template <typename ElemType>
Linklist<ElemType>::~Linklist() {
    Node *ptr = &Head;
    Node *t = nullptr;

    while(ptr->next != nullptr) {
        t = ptr->next;
        ptr->next = t->next;
        delete t;
    }
}

template <typename ElemType>
void Linklist<ElemType>::append(ElemType data) {
    Node *ptr = &Head;

    while(ptr->next != nullptr) {
        ptr = ptr->next;
    }
    ptr->next = new Node(data);
}

/* 当插入位置大于链表长度时，将元素插到链表末尾 */
template <typename ElemType>
void Linklist<ElemType>::insert(ElemType data, int pos) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr)
    {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }
    ptr->next = new Node(data, ptr->next);
}

template <typename ElemType>
bool Linklist<ElemType>::del(int pos) {
    Node *ptr = &Head;
    Node *t = nullptr;
    int p = 0;

    while(ptr->next != nullptr) {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }

    if(p == pos) {
        t = ptr->next;
        ptr->next = t->next;
        delete t;
        return true;
    } else {
        return false;
    }

}

/* 成功找到元素则返回索引，否则返回-1 */
template <typename ElemType>
int Linklist<ElemType>::search(ElemType data) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        if(ptr->next->data == data) {
            return p;
        }
        p++;
        ptr = ptr->next;
    }
    return -1;
}

template <typename ElemType>
int Linklist<ElemType>::getLength() {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        p++;
        ptr = ptr->next;
    }

    return p;
}

template <typename ElemType>
ElemType Linklist<ElemType>::getData(int pos) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }

    return ptr->next->data;
}

/* 排序函数需要一个返回值为int型的比较函数作为参数
*  升序排列：当a>b时，令compare(a, b)的返回值大于0
*  降序排列：当a<b时，令compare(a, b)的返回值大于0
*  注意：当a=b时，compare(a, b)的返回值必须小于或等于0。
*/
template <typename ElemType>
void Linklist<ElemType>::sort(int(*compare)(ElemType& a, ElemType& b)) {
    Node *ptr;
    Node *t;
    int tmp;
    bool sorted = false;

    while(!sorted) {
        sorted = true;
        ptr = &Head;
        t = ptr->next;
        while(ptr->next != nullptr && t->next != nullptr) {
            tmp = compare(t->data, t->next->data);
            if(tmp > 0) {
                ptr->next = t->next;
                t->next = ptr->next->next;
                ptr->next->next = t;
                sorted = false;
            }
            ptr = t;
            t = t->next;
        }
    }
}

作者：Wray Zheng
原文：http://www.codebelief.com/article/2016/11/linklist-implementation/