本次介绍的是无头结点的链表

1 创建结构体和节点

1.1 创建结构体

 结构体中要包含节点的数据域的指针域

struct node
{
	int data;      //数据域
	struct node *next;  //指针域
};

1.2 创建节点

使用malloc为节点申请空间

struct node* create_node()
{
	struct node *pnew = NULL;
	pnew = (struct  node*)malloc(sizeof(struct node));
	if(NULL == pnew)
	{
		printf("malloc error, %s, %d\n", __FILE__, __LINE__);
		exit(-1);
	}
	pnew->next = NULL;
	return pnew;
}

2 创建链表

2.1 尾插法创建链表

pnew为新节点 

①若链表为空，则头尾都指向pnew

②若不为空，则最后一个节点（tail）的next指向pnew，再将pnew设为最后一个节点（即将tail指向pnew）

if(head == NULL)
		{
			head = pnew;
			tail = pnew;
		}
		else
		{
			tail->next = pnew;
			tail = pnew;
		}

2.2 头插法创建链表

 将pnew的next指点第一个节点（head），再将pnew设为第一个节点（即将head指向pnew）

pnew->next = head;
head = pnew;

3 在链表中插入一个新的节点

 ① 查找插入位置的前一个节点

struct node* list_search_by_index(struct node *head, int index)
{
	struct node *p = head;
	for(int i=1; i<index; i++ )
	{
		p = p->next;
	}
	return p;
}

②将pnew插入，若插在第一位则用头插法；若插在中间，先将插入位置的前一个节点找出（psearch），pnew指向前一个节点的下一个节点（psearch->next），再将前一个节点的next指向pnew（即pnew变为前一个节点的下一个节点）；若插在结尾，则用尾插法。

struct node *list_insert_by_index(struct node *head, int index, int data)
{    
    struct node * pnew=NULL;
	pnew = create_node();
	pnew->data = data;

	if(1 == index)//  头插
	{
		pnew->next = head;
		head = pnew;
	}
	else //中间或者尾部插入
	{
		struct node *psearch = NULL;
		psearch = list_search_by_index(head, index-1);
		pnew->next = psearch->next;
		psearch->next = pnew;
	}
	return head;
}

4 删除链表中任意节点

① 查找插入位置的前一个节点

②用pdel保存要删除的节点。

若删除第一位，则先将第一位用pdel保存，再将head指向第一位的下一位，此时pdel就被从链表上取下来了，最后再将pdel释放。

若删除中间或结尾，先将删除位置的前一个节点找出（psearch），pdel保存的是psearch的下一个节点（psearch->next），将psearch指向pdel的下一个节点（psearch->next = pdel->next），此时pdel就被从链表上取下来了，最后再将pdel释放掉。

struct node*list_del_by_index(struct node *head, int  index)
{
    struct node *pdel = NULL ; 
	if(1 == index) //头删
	{
		pdel = head;
		head = head->next;
	}
	else  
	{
		struct node *psearch = NULL;
		psearch = list_search_by_index(head, index-1);

		pdel = psearch->next;
		psearch->next = pdel->next;
	}
	free(pdel);
	return head;
}