数据结构与算法学习：单向链表之构造与遍历

嘛。。最近在用C++折腾链表，于是乎开坑，总结下，如有误欢迎指正
本文如无特殊说明，皆为C++代码，DevCPP+MinGW环境编译通过

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（(Pointer）。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。
——维基百科《链表》

简单的说，就是一个结构的两个成员，一个放信息数据，另一个则指向下一个结点，依次遍历即可获得链上的数据，这就是单向链表。还是借用维基的一张图，图片可能更好理解些。

用C/C++来表示即为这样的一个结构，包含两个成员变量，一个是数据（这里使用int，实际可根据需要自行替换类型），一个则为该结构类型的指针。

struct List
{
    int data; //信息域，存放数据
    List *pNext; //指针域，指向下一个链表元素结点
};

下面我们来构造一个链表，数据是0->2->4->6->8->10->12->14->16->18
根据链表特点，需要不断new List生成链表结点，然后使前一个结点指向后一个，整个链表的最后一个结点指向NULL。

List *CreateList()
{
    List *p = NULL; 
    List *q = NULL;
    List *head = NULL; 
    for (int i=0; i<10; i++){
        p = new List; //创建新的结点
        p->data = i * 2; //数据设定为i*2
        if (head == NULL) {
            head = p; //第一次循环，生成第一个结点
        }
        else {
            q->pNext = p; //将q的指针域指向新结点p
        } 
        q = p; //保存新指针到q，以便下次循环设定该结点的指针域
    }
    if (head != NULL){
        q->pNext = NULL; //若至少插入了一个结点，则将最后一个结点的指针域置为NULL，以此作为链表结束标识
    }

    return head;
}

那么接下来将链表打印出来看看吧！这就需要遍历链表了(･~･`)

void displayList(const List *head)
{
    while( head != NULL){
        cout << head->data; //输出数据
        head = head->pNext; //使head指向下一结点
        if ( head != NULL ){
            cout << "->"; //不是最后一结点则输出分隔符
        }
    }
    cout<< endl;
}

运行.成功≧∇≦
输出结果：

0->2->4->6->8->10->12->14->16->18

Donate