数据结构-单链表实现-单链表遍历 单链表遍历时间复杂度

数组在存储的过程中是一段连续的地址空间，遍历数组元素采用下标的方法依次获取数组元素。

链表没有下标的概念，链表的遍历不能使用下标方式，但同样可以通过从首元结点开始，依次访问到最后一个结点，这必然使用到循环，那需要考虑如下两个问题？

（1） 循环的条件

（2） 循环的次数

先来看循环的条件。链表中的一个特点就是链表中最后一个元素的指针域为空，依此就可以在遍历过程中判断每个结点是否为空，不为空就输出数据域，否则就结束循环。因此采用一个指针指向首元结点，依次获取每个结点的指针域，判断是否为空。

再来看循环的次数。链表中结点的个数未知，因此循环的次数不定。比较for和while循环，for循环在循环次数确定时较适用，对于循环次数不确定，适合使用while循环。

到这函数主体的内容其实已经确定，还有一些细节需要确定。因为是一个函数，所以需要确定返回值和函数形参。

遍历链表需要依次输出链表各个结点的数据域，可以直接在函数中将每个元素输出，因此返回值可以为void（空）。

函数的形参，需要指定遍历哪一个链表，因此函数形参为这个链表本身，换句话说就是链表的头指针，因为通过头指针就可以获得整个链表。

函数的声明如下：

void ListTraverse(LinkList L);

返回值为void，形参为链表L

完整的代码如下：

void ListTraverse(LinkList L){
	LinkList p;
	p = L->next;
	printf("当前链表：\n");
	while(p != NULL){
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return;	
}

依次来解释下代码

LinkList p;

声明一个指针，这个指针就是用来指向结点，在循环过程中，依次判断结点是否为空

p = L->next;

L是头指针，存储的是头结点的地址，L->next表示的是首元结点的地址，头结点数据域并不存储数据信息，第一个数据域存储信息的结点是首元结点，所以遍历从首元结点开始。

	while(p != NULL){
		printf("%d ", p->data);
		p = p->next;
	}

循环条件，判定指针p不为空，p初值为首元结点的地址，在循环中使用赋值p = p->next，依次将指针p移动到下一个结点，当p->next为NULL时，说明已指向最后一个结点，循环结束。