链表

概述

链表（Linked list）是一种线性的数据结构，其中的每一个元素都是一个节点对象。其中各个节点通过“指针”相互连接。指针记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表分布在内存空间各处，不需要连续的内存

内存空间

内存空间是所有程序的公共资源，在一个复杂的系统运行下，空闲的内存空间可能散落在内存各处。

数组的内存空间必须是连续的，当数组非常大时，内存有可能无法提供大量的连续空间，此时就会体现出链表分散在存储空间各处的优势，它不需要一个连续的内存空间。

定义链表

通过创建一个新的类型名为node的结构体用来作为链表的节点。（链表节点的结构体不能是匿名的，因为在创建结构体时，需要创建结构体类型的指针用来作为指向节点，如果是匿名结构体，创建结构体后才能知道结构体的别名，此时就会造成逻辑冲突）

链表的节点有两个作用，一个是用来存储数据（val），另一个需要指向链表的下一个节点（结构体类型的指针变量next）（单向链表）。

typedef struct node{
  int val;             // 用来存放数据
  struct node *next;   // 用来存放结构体指针
} Node;

创建链表结构体（非必须）

在制作链表时，可以选择创建一个链表结构体用来加强数据之间的联系，当然这不是必须的，但是可以方便我们更好的管理链表结构体，提高代码的可读性

创建一个名为LinkList的链表结构体，其中存放链表的头节点和一个整形数据size，用来存放链表的大小。这个结构体可以是匿名的。

头节点的作用

在链表中使用头节点可以很方便的对链表进行数据的更替，因为头节点的固定（也不存放任何数据），删改数据时不需要去判断每个不同链接节点的指向性问题，也提高了代码的阅读方便性。

typedef struct{
  int size;
  Node *head;  //一个Node结构体类型的指针head 作为头节点
} LinkList;

创建一个新节点

Node *create_new_node(int val)    // 创建一个Node类型的指针函数 传入节点数据val
{
  Node *n = malloc(sizeof(Node)); // 创建一个Node结构体类型的指针n ，并且创建一个大小为一个Node结构体大小的堆内存被n所指向
  if(n == NULL) // 如果堆空间创建失败 打印错误信息并且结束函数
  {
     perror("Create new node failed ! \n");
     return NULL;
  }

  n->val = val;    // 写入传入的节点数据
  n->next = NULL;  // 使n的下一个指向为NULL，防止越界访问或随机指向

 return n;         // 返回指针n 表示成功创建了一个新节点，其中的数据为val
}

链表的初始化

以创建一个带有头节点的空链表为例

LinkList *initial_link_list()                 // 创建一个LinkList类型的指针函数
{
  Node *head = create_new_node(-1);           // 创建一个Node结构体类型的指针并为其创建一个新节点，其中的数据val对其没有任何影响，因为实际使用中，头节点是固定的
  if(head == NULL){                           // 如果head创建失败 结束函数返回NULL
    return NULL;
  }
  LinkList *list = malloc(sizeof(LinkList));  // 创建一个LinkList结构体类型的变量list，并为其开辟一个堆内存空间，大小为一个LinkList结构体所占用的大小
  if(list == NULL){
    perror("Create LinkList failed! \n");
    free(head);
    return NULL;
  }
  list->size = 0;                              // 解引用结构体类型指针list内的size变量赋值为0
  list->head = head;                           /// 解引用结构体类型指针list内的指针变量head赋值为head  表示指向一个头节点，至此，带头节点的空链表创建成功
  return list;                                 // 返回list指针
}

链表的插入（增）

带头节点的链表的头插法

int add_list(LinkList *list, int val)
{ 
  Node *new_node = create_new_node(val);   // 创建一个Node结构体类型的指针指向一个新节点
  if(new_node == NULL){
    perror("add_head failed! \n");
    return 0;
  }
  new_node->next = list->head->next;      // 新节点的下一个节点应该指向头节点的下一个节点 //如果头节点后没有节点，那么指向NULL，如果有节点，那么就会指向那个节点
  list->head->next = new_node;            // 头节点的下一个节点应该指向新创建的节点，完成新节点的插入操作
  list->size++;                           // 链表长度+1
  return 1;
}

带头节点的链表的尾插法

int add_tail(LinkList *list, int val)
{
  Node *new_node = create_new_node(val);
  if(new_node == NULL){
    perror("add_tail failed! \n");
    return 0;
   }
  Node *tail = list->head;               // 创建一个Node结构体类型的指针tail指向链表的头节点
  while(tail->next != NULL){             // 循环遍历链表直到tail的下一个节点为空节点
    tail = tail->next;
  }
  tail->next = new_node;                 // 使tail的下一个节点指向新创建的节点
  list->size++;                          // 链表大小+1
  return 1;
}

链表节点的删除

链表的异常判断

int is_empty(LinkList *list)
{
  if(list->head->next == NULL)       //如果头节点的下一个节点是空 返回1
  {
    return 1;
  }
  return 0;
}

带头节点的链表的头删法

int remove_head(LinkList *list)
{
  if(is_empty(list)){              // 如果返回1 表示为空 结束删除程序
    printf("链表已经为空");
    return 0；
  }
  Node *c_node = list->head->next; // 创建一个中间节点c_node令其指向头节点的下一个节点
  list->head->next = c_node->next; // 令头节点的下一个节点指向中间节点的下一个节点
                                   // 等同于孤立了原头节点的下一个节点
  free(c_node);                    // 释放中间节点，解放指向的节点的内存
  return 0;
}

带头节点的链表的尾删法

int remove_tail(LinkList *list)
{
  if(is_empty(list)){
    printf("链表已经为空");
    return 0；
  }
  Node *c_node = list->head;          // 创建了一个中间节点指向头节点
  while(c_node->next->next != NULL){  // 循环直到中间节点的下个节点后指向NULL
    c_node = c_node->next;   
  }
  Node *tail = c_node->next;          // 创建一个尾节点指向中间节点的下一个节点，也就是指向空节点的前一个节点
  c_node->next = NULL;                // 令中间节点的下一个节点指向NULL
                                      // 等同于孤立了原尾节点
  free(tail);                         // 释放尾节点
  return 1;
}

链表的销毁

如果想要销毁一个链表，应该先销毁链表中的每一个节点，防止内存占用，然后再销毁链表本身

int destroy_list(LinkList *list)
{
  if(list == NULL){               // 如果节点为空，返回0结束程序
    return 0;
  }
  Node *current = list->head;     // 创建一个中间节点令其指向头节点
  Node *node;                     // 创建一个空节点
  while(current != NULL){         // 循环释放每一个节点直到头节点指向NULL
    node = current->next;         // 空指向中间节点的下一个节点，等待下一个节点的释放
    free(current);                // 释放中间节点指向的节点
    current = node;               // 令中间节点指向之前的下一个节点
  }
  free(list);                     // 所有节点释放后再释放链表本身
  return 1;
}

链表的打印

通过循环每次使结构体类型的指针p不断指向下一个节点，直到NULL，每次打印解引用p结构体指针内部的val的值

void for_each_link_list(LinkList *list)
{
  Node *p = list->head->next;
  while(p){
    printf("%d ", p->val);         // 打印Node结构体指针的解引用p结构体内的val的值
    p = p->next;                   // 令p指向下一个节点
  }
}

不带头节点的单链表的操作

#include <stdio.h>
#include <stdlib.h>

//定义一个链表节点
typedef struct node
{
  int val;
  struct node *next;
} Node;

//创建一个新节点
Node *create_new_node(int val){
  Node *n = malloc(sizeof(Node));
  if(n == NULL){
    perror("create new node failed");
    return NULL;
  }

  n->val = val;
  n->next = NULL;
  return n;
}

//初始化链表
Node *intial_link_list(){
  Node *node = create_new_node(0);
  if(node == NULL){
    return NULL;
  }

  //创建链表结构体
  Node *list = malloc(sizeof(Node));
  if(list == NULL){
    perror("create LinkList failed!\n");
    free(node);
    return NULL;
 }
    list->next = NULL;

    return list;
}

//不带头节点的链表的头插法
int add_head(Node *list, int val){
  Node *new_node = create_new_node(val);
  if(new_node == NULL){
    perror("new node is failed\n");
    return 0;
  }
  // 让新的节点的next指向链表首节点的next
  new_node->next = list->next;
  // 让链表的next节点指向新节点
  list->next = new_node;
  return 1;
}

//不带头节点的链表的尾插法
int add_tail(Node *list, int val){
  Node *new_node = create_new_node(val);
  if(new_node == NULL){
    perror("new node is failed\n");
    return 0;
  }
  Node *p = list->next;
  while(p->next != NULL){
    p = p->next;
  }
  p->next = new_node;
  new_node->next = NULL;
  return 1;
  //让新的节点的next指向链表尾节点
}

int is_empty(Node *list)
{
    if (list->next == NULL){
        return 1;
    }
    return 0;
}

//不带头节点的链表的头删法
int remove_head(Node *list){
  Node *p = list->next;
  if (is_empty(list)){ 
    printf("链表已经为空!\n");
    return 0;
  }

  list->next = list->next->next;
  free(p);
  return 1;
}

//不带头节点的链表的尾删

int remove_tail(Node *list){
  Node *p = list->next;

  while(p->next->next != NULL){
    p = p->next;
  }

  Node *tail = p->next;
  p->next = NULL;
  free(tail);

  return 1;
}

//不带头节点的链表的销毁
int destory_list(Node *list){
  if(list == NULL){
    return 0;
  }

  Node *curred = list->next;
  Node *next_node;

  while(curred != NULL){
    next_node = curred->next;
    free(curred);
    curred = next_node;
  }
  free(list);
  return 1;
}

//循环打印链表
void for_each_link_list(Node *list){
  Node *p = list->next;
  while(p){
    printf("%d ", p->val);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char const *argv[])
{
  Node *list = intial_link_list();
  if(list == NULL){
    return -1;
  }

  add_head(list, 1);
  add_head(list, 2);
  add_head(list, 3);
  add_head(list, 4);

  add_tail(list, 1);
  add_tail(list, 2);
  add_tail(list, 3);
  add_tail(list, 4);

  remove_head(list);
  remove_tail(list);

  destory_list(list);
  
  for_each_link_list(list);

  return 0;
}