数据结构01:链表

数据结构

链表

链表和数组的区别

1. 存储方式

• 数组：
  • 元素在内存中连续存储，占用一块连续的内存空间
  • 元素的地址可以通过索引计算（基地址 + 索引 × 元素大小）
  • 大小固定，在创建时需要指定容量
• 链表：
  • 元素（节点）在内存中分散存储，不要求连续
  • 每个节点包含数据和指向下一个（或上一个）节点的指针
  • 大小动态变化，可根据需要随时增减节点

2. 访问效率

• 数组：
  • 支持随机访问，通过索引可以直接访问任意元素，时间复杂度为 O (1)
  • 访问效率高，适合需要频繁随机访问的场景
• 链表：
  • 不支持随机访问，必须从表头（或表尾）开始依次遍历，时间复杂度为 O (n)
  • 访问效率低，不适合需要频繁随机访问的场景

3. 插入和删除操作

• 数组：
  • 插入 / 删除元素时，需要移动该位置后的所有元素，时间复杂度为 O (n)
  • 尤其在数组头部操作时效率极低
  • 动态扩容时需要重新分配内存并复制元素
• 链表：
  • 插入 / 删除元素时，只需修改相关节点的指针，时间复杂度为 O (1)（已知前驱节点时）
  • 不需要移动其他元素，操作效率高
  • 没有扩容问题，内存利用率更高

4. 内存占用

• 数组：
  • 可能存在内存浪费（预分配的容量可能大于实际需要）
  • 内存利用率较低
• 链表：
  • 每个节点需要额外存储指针信息，有一定内存开销
  • 但整体内存利用率更高，不会浪费空间

5. 适用场景

• 数组：
  • 适合需要频繁随机访问元素的场景（如查找操作多）
  • 元素数量固定或变化不大的情况
  • 例如：数据库索引、矩阵存储、缓存实现等
• 链表：
  • 适合需要频繁插入和删除元素的场景
  • 元素数量动态变化较大的情况
  • 例如：链表式队列 / 栈、哈希表链地址法冲突解决、邻接表等

总结对比表

• 数组中的数据我们称之为元素

• 链表中的数据我们称之为节点

  每一个节点都是一个结构体,当前结构体包含两种信息

  1. 数据(每个节点中所存储的信息)
  2. 节点指针(保存下一个节点的信息)

  将节点插入链表:头插法/尾插法/中间插入
    
      
      
      
      
                                                                                  
  

  eg:

                                                
										   节点对应结构体
typedef struct Node 
{
    int num;		   /每个节点中存储的数据,可以有多个
    struct Node* pNext;   /用于保存下一个节点(结构体)的指针
} Node;








	 									函数功能:      创建一个节点
								         int n --------当前节点的数据
									NODE*  head---------当前链表首节点地址
								  返回类型:成功返回当前节点首地址,失败返回NULL
   
NODE* createNode(int n,NODE* head)
{
    //创建一个新节点
	NODE* pNew = (NODE*)malloc(sizeof(NODE));
    if(pNew == NULL)
    {
        printf("createNode %d fail:%s!\n",n,strerror(errno));
            return NULL;
    }
    
    //初始化新节点中的成员变量
    pNew -> num = n;
    pNew -> pNext = NULL;
    
    //返回当前节点的首地址
         return pNew;
                                  }








                                          函数功能:      删除整个链表
                                    NODE*  head---------当前链表首节点地址

 void distroyList(NODE* head)
 {
    if(head == NULL)
    {
        return;
    }
     
     NODE* P = head;
     while(p != NULL)
     {
         head = p -> pNext;
         free(p);
         p = head;
     }
 }









                                     
  										函数功能:    输出整个链表
									NODE*  head---------当前链表首节点地址
								  返回类型:成功返回当前节点首地址,失败返回NULL
                                       
                                                                         
void displayList(NODE* head)
                                                                                                     
{
     while(p != NULL)
     {
         printf("%d",p->num);
         p = p->pNext;
     }
                                                                  
}                                  
                                                                    



void insert_head1(int n,NODE** head)
{
    //创建新节点
    NODE*  pNew = createNode(n);
    //如果是空链表
    if(*head == NULL)
    {
        *head = pNew;
        return
    }
    //新节点指向原链表的首节点
    pNew -> pNext = *head;
    
    //将新节点的起始地址给*head
    *head = pNew;
    
}


NODE*	 insert_head2(int n,NODE* head)
{
     NODE*  pNew = createNode(n);
    
      //如果是空链表
    if(head == NULL)
    {
   		return pNew;
    }
        pNew -> pNext = *head;
    
    //将新节点的起始地址给*head
   return  pNew;
    
}




//插入到结尾

NODE* insert_tail(int n, NODE* head)
{
    //创建节点
    NODE* pNew == createNode(n);
    if(pNew == NULL)
    {
        return pNew;
    }
    //获取原链表尾节点的指针
    NODE* pTail = getTaiilNode(head);
    if(pTail) = getTaiilNode(head);
    {
        return pNew;
        
    }
    pTail ->P=pNext = pNew;
    return head;
    
    
    
    
}

NODE* insertNode(int n,NODE* head,int pos)
{
    
}


int main()
{
  
    // 用于记录当前链表中首节点的地址
    NODE* pHead = NULL;

    // 将节点插入链表中：头插法
    //insert_head1(5, &pHead);
    //insert_head1(4, &pHead);
    //insert_head1(3, &pHead);
    //insert_head1(2, &pHead);
    //insert_head1(1, &pHead);

    //pHead = insert_head2(-5, pHead);
    //pHead = insert_head2(-4, pHead);
    //pHead = insert_head2(-3, pHead);
    //pHead = insert_head2(-2, pHead);
    //pHead = insert_head2(-1, pHead);

    // 将节点插入链表中：尾插法
    //pHead = insert_tail(1, pHead);
    //pHead = insert_tail(2, pHead);
    //pHead = insert_tail(3, pHead);
    //pHead = insert_tail(4, pHead);


    // 将节点插入链表中：任意位置插入
    // 假设位置 0 代表头插
    pHead = insertNode(1, pHead, 3);

    displayList(pHead);

    distroyList(pHead);

    return 0;
}