1. 鏈表結構介紹

在前面章節已經學習了數組的使用，數組的空間是連續空間，數組的大小恒定的，在很多動態數據存儲的應用場景下，使用不方便；而這篇文章介紹的鏈表結構，支持動態增加節點，釋放節點，比較適合存儲動態數據的應用場景，而且鏈表的空間是存儲在堆上面的，可以動態分配，釋放。從效率上來講，數組的空間是連續的，查詢、讀取數據數組占優勢；鏈表的優勢在于節點可以動態增加、動態刪除，刪除支持任意位置的節點刪除。

特點:

數組的空間是連續的，可以直接通過[]下標訪問。

鏈表的節點是不連續的，需要通過每個節點的指針，來找到上一個節點或者下一個節點的地址。

鏈表的每個節點就是一個結構體變量，節點里有一個或者兩個指針，可以保存上一個節點和下一個節點的地址，方便遍歷鏈表，刪除、插入節點時定位位置。

2. 案例: 單向鏈表的創建與使用

下面例子采用函數封裝的形式編寫，每個功能都使用子函數實現。

實現的功能如下:

1. 初始化鏈表頭
2. 插入節點的函數(鏈表任意位置插入，鏈表尾插入)
3. 刪除節點的函數（鏈表任意位置刪除、鏈表尾刪除）
4. 遍歷鏈表，輸出鏈表里的所有信息

#include 
#include 
?
//定義鏈表節點的結構體
struct app
{
  int a;
  struct app *next; //能保存結構體的地址
};
?
struct app *list_head=NULL; //鏈表的頭指針
?
void list_print(struct app *head);
struct app *list_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_del(int a,struct app *head);
?
int main()
{
  //1. 初始化鏈表頭
  list_head=list_HeadInit(list_head);
  //2. 在鏈表尾插入數據
  list_add(10,list_head);
  list_add(11,list_head);
  list_add(12,list_head);
  list_add(13,list_head);
  //3. 刪除節點
  list_del(11,list_head);
  //4. 輸出鏈接節點里的數據
  list_print(list_head);
  return 0;
}
?
/*
函數功能: 初始化鏈表頭--給鏈表頭申請空間
*/
struct app *list_HeadInit(struct app *head)
{
  if(head==NULL) //沒有空間
   {
    //1. 申請鏈表頭空間
    head=malloc(sizeof(struct app));
    //2. 初始化鏈表頭
    head->next=NULL;
   }
  return head;
}
?
/*
函數功能: 在鏈表尾插入數據
int a  插入的數據值
struct app *head  鏈表頭
*/
void list_add(int a,struct app *head)
{
  struct app *new_p=NULL;
  struct app *next_p=head;
  struct app *tmp_p; //保存上一個節點的地址
  //1.申請空間并給空間成員賦值
  new_p=malloc(sizeof(struct app));
  new_p->a=a;
  new_p->next=NULL;
?
  //2. 找到鏈表尾
  while(next_p!=NULL)
   {
    tmp_p=next_p;
    next_p=next_p->next; //指針指向下一個節點
   }
?
  //3. 插入新節點--鏈接結尾
  tmp_p->next=new_p;
}
?
/*
函數功能: 遍歷輸出鏈接里的所有數據
*/
void list_print(struct app *head)
{
  struct app *next_p=head;
  int cnt=0;
  if(head!=NULL)
   {
    while(next_p->next!=NULL)
     {
      next_p=next_p->next;
      printf("鏈表節點[%d]:a=%d\n",cnt++,next_p->a);
     }
   }
}
?
/*
函數功能:鏈表的刪除－－按照指定的數據刪除
*/
void list_del(int a,struct app *head)
{
  struct app *next_p=head;
  struct app *tmp_p; //保存上一個節點的地址
  //1. 找到要刪除的鏈表
  if(next_p!=NULL)
   {
    while(next_p->next!=NULL)
     {
      tmp_p=next_p; //保存上一個節點的地址
      next_p=next_p->next; //獲取有效節點的地址
      if(next_p->a==a) //判斷是否需要刪除
       {
        tmp_p->next=next_p->next;
        free(next_p);
       }
     }
   }
}
復制代碼

3. 案例: 單向循環鏈表

代碼直接在上面的案例2例子上改造的，區別就是尾結點指向了頭結點而不是NULL。

#include 
#include 
?
//定義鏈表節點的結構體
struct app
{
  int a;
  struct app *next; //能保存結構體的地址
};
?
struct app *list_head=NULL; //鏈表的頭指針
?
void list_print(struct app *head);
struct app *list_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_del(int a,struct app *head);
?
int main()
{
  //1. 初始化鏈表頭
  list_head=list_HeadInit(list_head);
  //2. 在鏈表尾插入數據
  list_add(10,list_head);
  list_add(11,list_head);
  list_add(12,list_head);
  list_add(13,list_head);
  //3. 刪除節點
  list_del(11,list_head);
  //4. 輸出鏈接節點里的數據
  list_print(list_head);
  return 0;
}
?
/*
函數功能: 初始化鏈表頭--給鏈表頭申請空間
*/
struct app *list_HeadInit(struct app *head)
{
  if(head==NULL) //沒有空間
   {
    //1. 申請鏈表頭空間
    head=malloc(sizeof(struct app));
    //2. 初始化鏈表頭
    head->next=head;
   }
  return head;
}
?
/*
函數功能: 在鏈表尾插入數據
int a  插入的數據值
struct app *head  鏈表頭
*/
void list_add(int a,struct app *head)
{
  struct app *new_p=NULL;
  struct app *next_p=head;
  struct app *tmp_p; //保存上一個節點的地址
  //1.申請空間并給空間成員賦值
  new_p=malloc(sizeof(struct app));
  new_p->a=a;
  new_p->next=head;
?
  //2. 找到鏈表尾
  if(head!=NULL)
   {
    if(next_p->next==head) //表示第一次插入節點
     {
      next_p->next=new_p;
      //head ----<節點1>---head
     }
    else
     {
      while(next_p->next!=head)
       {
        next_p=next_p->next; //指針指向下一個節點
       }
      //3. 插入新節點--鏈接結尾
      next_p->next=new_p;
     }  
   } 
}
?
/*
函數功能: 遍歷輸出鏈接里的所有數據
*/
void list_print(struct app *head)
{
  struct app *next_p=head;
  int cnt=0;
  if(head!=NULL)
   {
    printf("頭地址: %#x\n",next_p); //頭
    printf("第一個節點地址:%#x\n",next_p->next); //下一個節點地址
    printf("第二個節點地址:%#x\n",next_p->next->next); //下下一個節點地址
    printf("第三個節點地址:%#x\n",next_p->next->next->next);
    printf("第四個節點地址:%#x\n",next_p->next->next->next->next);
  
    while(next_p->next!=head)
     {
      next_p=next_p->next;
      printf("鏈表節點[%d]:a=%d\n",cnt++,next_p->a);
     }
   }
}
?
/*
函數功能:鏈表的刪除－－按照指定的數據刪除
*/
void list_del(int a,struct app *head)
{
  struct app *next_p=head;
  struct app *tmp_p; //保存上一個節點的地址
  //1. 找到要刪除的鏈表
  if(next_p!=NULL)
   {
    while(next_p->next!=head)
     {
      tmp_p=next_p; //保存上一個節點的地址
      next_p=next_p->next; //獲取有效節點的地址
      if(next_p->a==a) //判斷是否需要刪除
       {
        tmp_p->next=next_p->next;
        free(next_p);
       }
     }
   }
}
復制代碼

4. 案例: 創建雙向鏈表循環，實現插入、刪除、遍歷

雙向鏈表在每個節點里新增加了一個指針，用于保存上一個節點的地址，現在的節點里一個用兩個指針，一個保存上一個節點的地址，一個保存下一個節點的地址。

#include 
#include 
?
//定義鏈表節點的結構體
struct app
{
  int a;
  struct app *next; //下一個節點地址
  struct app *prev; //前一個節點地址
};
?
//全局變量聲明區域
struct app *list_head=NULL; //鏈表的頭指針
?
//函數聲明
struct app *List_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_print(struct app *head);
void list_del(int a,struct app *head);
?
int main()
{
  /*1. 初始化鏈表*/
  list_head=List_HeadInit(list_head);
  /*2. 添加鏈表節點*/
  list_add(10,list_head);
  list_add(11,list_head);
  list_add(12,list_head);
  list_add(13,list_head);
  list_add(14,list_head);
  /*3.刪除指定節點*/
  list_del(12,list_head);
  /*4. 遍歷輸出所有節點信息*/
  list_print(list_head);
  return 0;
}
?
/*
函數功能: 創建鏈表頭
*/
struct app *List_HeadInit(struct app *head)
{
  if(head==NULL)
   {
    head=malloc(sizeof(struct app));
    head->a=0;
    head->next=head;
    head->prev=head;
   }
  return head;
}
?
/*
函數功能: 添加數據-鏈表尾添加數據
*/
void list_add(int a,struct app *head)
{
  struct app *next_p=head;
  struct app *new_p=NULL;
  /*1. 申請新的節點*/
  new_p=malloc(sizeof(struct app));
  new_p->a=a;
  new_p->next=head;
  /*2. 完成新節點的添加*/
  //遍歷鏈表
  while(next_p->next!=head)
   {
    next_p=next_p->next;
   }
  //添加新節點
  new_p->prev=next_p;
  next_p->next=new_p;
  //修改鏈表頭的上一個節點地址
  head->prev=new_p;
}
?
/*
函數功能:輸出鏈表里的所有數據
*/
void list_print(struct app *head)
{
  struct app *next_p=head;
  int cnt=0;
  /*1. 順向遍歷*/
  while(next_p->next!=head)
   {
    next_p=next_p->next;
    printf("節點[%d]:%d\n",cnt++,next_p->a);
   }
  /*2. 反向遍歷*/
  next_p=head;
  while(next_p->prev!=head)
   {
    next_p=next_p->prev;
    printf("節點[%d]:%d\n",cnt--,next_p->a);
   }
}
?
/*
函數功能:刪除鏈表里的指定節點
*/
void list_del(int a,struct app *head)
{
  struct app *next_p=head;
  struct app *tmp_p=NULL;
  while(next_p->next!=head)
   {
    tmp_p=next_p; //保存上一個節點的地址
    next_p=next_p->next;
    if(next_p->a==a)
     {
      //方式1
      tmp_p->next=tmp_p->next->next;
      tmp_p->next->prev=tmp_p;
?
      //方式2
      //tmp_p->next=next_p->next;
      //next_p->next->prev=tmp_p;
      
      //printf("%d\n",tmp_p->a); //11
      //printf("%d\n",tmp_p->next->a); //13
      //printf("%d\n",next_p->next->prev->a); //11
      free(next_p);
      break;
     }
   }
}

審核編輯 黃昊宇