[数据结构与算法]单链表的 头插法 尾插法

一.单链表的头插法

1. 从一个空表开始，重复读入数据
2. 生成新结点，将读入数据存放到新结点的数据域中
3. 从最后一个结点开始，依次将各个结点插入到链表的前端

?头插法倒位序输入元素 如:L{1,2,3} 输入顺序为 3，2，1

void CreatList_H(LinkList &L, int n){      //n为插入结点数
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	for(i=n; i>0; i--;){
		p = (LNode*)malloc(sizeof(LNode));
		scanf(&p->data);
		
		p->next = L->next;
		L->next = p;
	}
}

?时间效率：T(n) = O(n)

二.单链表的尾插法

1. ?从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
2. 初始时，r同L指向头结点
3. 每读入一个数据元素，则申请一个新结点，将新结点插入到尾结点后，r指向新的尾结点

?

?尾插法正位序输入元素

void CraetList_R(LinkList &L, int n){
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;                       
	r = L;                                    //尾指针指向头结点 
	
	for(i=0; i<n; i++){
		p = (LNode*)malloc(sizeof(LNode));
		scanf(&p->data);                      //生成新结点，输入元素 
		p->next = NULL;
		r->next = p;                          //新结点插入到表尾 
		r = p;                                //r指向新结点 
	}    
} 

时间效率：T(n) = O(n)