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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

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

1
2
3
4
5
6
7
8
9
10
11
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