链表| 第2课（链表的插入）

发表于

在先前的文章里，我们已经简单介绍了链表。我们也创建了一个带有3个结点的简单链表，然后讨论了一下如何遍历它们。

这篇文章涉及到的所有程序均使用下面的结点表示链表。

1
2
3
4
5
6
// 链表结点
struct Node
{
  int data;
  struct Node *next;
};

这篇文章里, 会讨论如何在链表里插入结点。一般来说，有3个方法来添加结点。

  1. 在链表的首部。
  2. 在一个给定的结点之后。
  3. 在链表的尾部。

在首部添加一个结点: (4步)

新结点要添加在给定链表的首部。新添加的结点成为新的头结点。例如, 如果给定的链表是10->15->20->25 我们要再首部添加一个5, 然后链表就会变成5->10->15->20->25. 我们使用一个函数push()来表示。 这个函数必须接收一个指向头指针的指针, 因为需要修改它指向新加的结点。

下面是在首部添加结点的4个步骤。

/* 引用链表的头结点，指定一个整数, 然后在链表首部添加一个新的结点。*/
void push(struct Node** head_ref, int new_data)
{
    /* 1. 分配结点 */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    /* 2. 指定数据  */
    new_node->data  = new_data;

    /* 3. 指定新结点的后继为 head_ref */
    new_node->next = (*head_ref);

    /* 4. 头部指向新结点 */
    (*head_ref)    = new_node;
}

这个函数的时间复杂度为 O(1)，因为它做的是连续数量的工作。

在指定的结点后面添加结点: (5 个步骤)

指定一个结点的指针, 然后新结点添加在它的后面。

/* 指定一个 prev_node, 然后在它后面添加一个新的结点 */
void insertAfter(struct Node* prev_node, int new_data)
{
    /*1. 判断所给的结点是否为 NULL */
    if (prev_node == NULL) 
    { 
       printf("the given previous node cannot be NULL");       
       return;  
    }  

    /* 2. 分配新的结点 */
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));

    /* 3. 指定数据  */
    new_node->data  = new_data;

    /* 4. 新结点的后继指定为 prev_node 的后继*/
    new_node->next = prev_node->next; 

    /* 5. 指定 prev_node 后继为新结点 */
    prev_node->next = new_node;
}

这个函数的时间复杂度为 O(1)，因为它做的是连续数量的工作。

在链表尾部添加结点: (6 步)

新结点要求添加在链表的最后。例如，如果给定的链表是5->10->15->20->25然后在最后添加一个30, 然后链表就变成了5->10->15->20->25->30.

因为链表是用头结点表示的, 所以我们必须整个遍历它, 然后修改最后一个结点的后继为新的结点。

/* 引用链表的头结点, 指定一个整数, 在尾部添加一个新结点 */
void append(struct Node** head_ref, int new_data)
{
    /* 1. 分配结点 */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref;  /* used in step 5*/

    /* 2. 指定数据  */
    new_node->data  = new_data;

    /* 3. 新结点是最后一个结点，所以它的后继为 NULL*/
    new_node->next = NULL;

    /* 4. 如果链表为空, 那么新结点就是头结点 */
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }  

    /* 5. 遍历到最后一个结点 */
    while (last->next != NULL)
        last = last->next;

    /* 6. 修改最后一个结点的后继为新结点 */
    last->next = new_node;
    return;    
}

这个函数的时间复杂度为 O(n) n 是链表的结点数。因为这里有一个循环。

这个函数可以优化到时间复杂度为 O(1)，方法是使用一个尾部指针。

下面是一个完整的程序，使用上面所有的函数创建一个链表

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

// 链表结点
struct Node
{
  int data;
  struct Node *next;
};

/* 指向头结点的指针和一个整数, 在链表前面插入一个新的结点. */
void push(struct Node** head_ref, int new_data)
{
    /* 1. 分配结点 */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    /* 2. 指定数据  */
    new_node->data  = new_data;

    /* 3. 新结点的后继作为头部 */
    new_node->next = (*head_ref);

    /* 4. 头部指向新结点 */
    (*head_ref)    = new_node;
}

/* 指定一个 prev_node, 在给定的结点后面插入一个新结点 */
void insertAfter(struct Node* prev_node, int new_data)
{
    /*1. 判断所给的结点是否为 NULL */
    if (prev_node == NULL)
    {
      printf("the given previous node cannot be NULL");
      return;
    }

    /* 2. 分配结点 */
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));

    /* 3. 指定数据  */
    new_node->data  = new_data;

    /* 4. 指定新结点的后继为 prev_node 的后继 */
    new_node->next = prev_node->next;

    /* 5. 指定 prev_node 后继为新结点 */
    prev_node->next = new_node;
}

/* 指向头结点的指针和一个整数, 在链表的尾部添加一个新结点  */
void append(struct Node** head_ref, int new_data)
{
    /* 1. 分配结点 */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref;  /* used in step 5*/

    /* 2. 指定数据  */
    new_node->data  = new_data;

    /* 3. 新结点会成为最后一个结点, 所以它的后继为 NULL*/
    new_node->next = NULL;

    /* 4. 如果链表为空, 新结点就是头结点 */
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }

    /* 5. 遍历到最后一个结点 */
    while (last->next != NULL)
        last = last->next;

    /* 6. 修改最后一个结点的后继为新结点 */
    last->next = new_node;
    return;
}

// 这个函数从头打印链表的内容
void printList(struct Node *node)
{
  while (node != NULL)
  {
     printf(" %d ", node->data);
     node = node->next;
  }
}

/* 测试函数*/
int main()
{
  /* 空链表开始 */
  struct Node* head = NULL;

  // 插入 6.  链表变成 6->NULL
  append(&head, 6);

  // 在首部插入 7 . 链表变成 7->6->NULL
  push(&head, 7);

  // 在首部插入 1. 链表变成 1->7->6->NULL
  push(&head, 1);

  // 在尾部插入4. 链表变成 1->7->6->4->NULL
  append(&head, 4);

  // 在 7 后面插入 8, 链表变成 1->7->8->6->4->NULL
  insertAfter(head->next, 8);

  printf("\n Created Linked list is: ");
  printList(head);

  return 0;
}

输出:
 Created Linked list is:  1  7  8  6  4