目录

1.前言

2.了解单链表

3.单链表代码实现

      3.1 单链表结构体实现

      3.2 创建节点

      3.3  打印单链表

      3.4 尾插 

      3.5  头插 

      3. 6 头删

      3.7  尾删

      3.8  查找

      3.9  插入

           3.9.1 在pos位置之前插入 

           3.9.2  在pos位置之后插入（主要使用这种功能）---不需要找pos前一个

      3.10 删除

             3.10.1 删除pos位置的值

             3.10.2  删除pos后一个（主要使用这种功能）---不需要找pos前一个

      3.11 单链表总结

---

1.前言

          学习了顺序表发现有以下缺点：

---

        1.1 空间不够，需要扩容（扩容有一定的空间浪费）。

        1.2 头插、头删（需要移动数据）时间复杂度是O(N)，效率低。

         所以我们学习单链表来按需申请释放空间，不需要移动数据，提高效率。

---

2.了解单链表

  概念：单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。

  特点：每个结点除了存放数据元素外，还要存储指向下一个节点的指针

  优点：不要求大片连续空间，改变容量方便。。

  缺点：不可随机存取，要耗费一定空间存放指针。

  单链表逻辑及重要性：

---

3.单链表代码实现

      3.1 单链表结构体实现

typedef int SLTDataType; 
typedef struct SListNode
{
	SLTDataType data;//存放数据
	struct SListNode* next;//指向下一个结构体的指针
}SLTNode;

---

       3.2 创建节点

void TestSList1()
{
	//struct SListNode* 
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n1);
	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n2);
	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n3);
	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n4);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
}

---

      3.3  打印单链表

cur = cur->next理解:

第一次进来cur指向的是链表的头，cur=cur—>next说明把下一个节点的地址赋给cur，现在的cur指向的是第二个结构体，是第二个结构体的地址.......

循环下去就可以打印出节点里的data数据，直到cur=NULL。

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

---

       3.4 尾插 

 注意点:

当链表为空的时候，newnode给phead时，由于phead是一个形参，函数中形参的改变不会改变实参。

这时要改变指针变量（plist）就要传指针变量的地址——就要传二级指针。

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

---

         3.5  头插 

单链表头插不需要和尾插一样要特殊处理

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

---

          3. 6 头删

void SListPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);//暴力检查
	//if (*pphead == NULL)  //温柔检查
	//	return;

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

---

         3.7  尾删

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);

	// 1、只有一个节点
	// 2、多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{  
        //两种方法   
		/*SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;*/
//
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}	
}

---

      3.8  查找

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}

---

       3.9  插入

              3.9.1 在pos位置之前插入 

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{  
  assert(pos);
  assert(ppheart);
  
  //头插
  if (pos= *pphead)
  {
    
      SListPushFront(pphead.x)；
  }
  
  else
   {
         SLTNNode* prev= *ppheart;
         while(prev->next !=pos)

           {
                 prev=prev->next;
           }
         
           SLTNode* newnode=BuySListNode(x);
           prev->next=newnode;
           newnode->next=pos;  

   }

           3.9.2  在pos位置之后插入（主要使用这种功能）---不需要找pos前一个

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	/*SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;*/

	// 不在乎链接顺序
	SLTNode* newnode = BuySListNode(x);
	SLTNode* next = pos->next;
	// pos newnode next
	pos->next = newnode;
	newnode->next = next;
}

---

      3.10 删除

             3.10.1 删除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   assert(pos);
  assert(ppheart);
    
   //头删    
   if (pos= *pphead)
   {
    
       SListPopFront(pphead);
   }
   
    else
    { 
       SLTNode* prev= *pphesd;
       while(prev->next !=pos)
        {
            prev=prev->next;
        }
    
      prev->next= pos->next;
       free(pos);
     }

            3.10.2  删除pos后一个（主要使用这种功能）---不需要找pos前一个

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
		return;

	SLTNode* del = pos->next;
	//pos->next = pos->next->next;//这样就释放不了节点
	pos->next = del->next;

	free(del);
	del = NULL;
}

          3.11 单链表总结

        由单链表的在pos位置之后插入和删除pos位置之后的值可知，单链表没有完全解决顺序表的缺陷，所以我们后面学习双向的链表来提高效率。