C/C++中创建(带头结点、不带头结点的)单链表

1、带头结点的单链表（推荐使用带头结点的单链表）（采用尾插法）

• 了解单链表中节点的构成
  
  
  
  从上图可知，节点包含数据域和指针域，因此，在对节点进行定义时，我们可以如下简单形式地定义：

/* 定义链表 */

typedef struct Node{

    int data;    // 数据域

    struct Node *next;    // 指针域(后节点)

    //  struct Node *next;    // 指针域(前节点)，这里暂时不考虑双链表表

}Node, *LinkedList;

• 尾插法思想
  
  尾插法的思想其实很简单，通俗来讲就是每创建一个新节点都插到原来链表的后面。
  
  
  
  !
  
  

Node *Head, *L, *LNew;

/* 申请节点 */

Head = (Node *)malloc(sizeof(Node));

/* 带头结点 */

L = Head;

L->next = NULL;

 /* 初始赋值 */

for(int i = 0; i < 3; ++i){

     /* 申请节点 */

     LNew = (Node *)malloc(sizeof(Node));

     LNew->data = i;

     L->next = LNew;

     LNew->next = NULL;

     L = LNew;

}

• 简单的代码

#include <iostream>

using namespace std;

/* 定义链表 */

typedef struct Node{

    int data;

    struct Node *next;

}Node, *LinkedList;

/* 链表初始化 */

LinkedList LinkedListInit(){

    Node *Head, *L, *LNew;

    /* 申请节点 */

    Head = (Node *)malloc(sizeof(Node));

    /* 带头结点 */

    L = Head;

    L->next = NULL;

    /* 初始赋值 */

    for(int i = 0; i < 10; ++i){

        /* 申请节点 */

        LNew = (Node *)malloc(sizeof(Node));

        LNew->data = i;

        L->next = LNew;

        LNew->next = NULL;

        L = LNew;

    }

    /* 返回头结点指针 */

    return Head;

}

int main()

{

    Node *p;

    p = LinkedListInit();

    p = p->next;

    while(p != NULL){

        cout << p->data << ' ';

        p = p->next;

    }

    cout << endl;

    return 0;

}

2、不带头结点的单链表（原理与带头结点类似）

• 不带头结点与带头结点的区别
  
  由于不带头结点的单链表第一个节点需要有效，因此，在处理第一个节点时，需要做节点迁移。
  
  
  
  
  
  

Node *Head, *L, *LNew;

/* 申请节点 */

Head = (Node *)malloc(sizeof(Node));

/* 不带头结点 */

L = Head = NULL;

 /* 初始赋值 */

for(int i = 0; i < 4; ++i){

     /* 申请节点 */

     LNew = (Node *)malloc(sizeof(Node));

     LNew->data = i;

     LNew->next = NULL;

     if(L == NULL){

         L = Head = LNew;

     }else{

         L->next = LNew;

     }

     L = LNew;

}

• 简单的代码

#include <iostream>

using namespace std;

/* 定义链表 */

typedef struct Node{

    int data;

    struct Node *next;

}Node, *LinkedList;

/* 链表初始化 */

LinkedList LinkedListInit(){

    Node *Head, *L, *LNew;

    /* 申请节点 */

    Head = (Node *)malloc(sizeof(Node));

    /* 不带头结点 */

    L = Head = NULL;

    /* 初始赋值 */

    for(int i = 0; i < 5; ++i){

        /* 申请节点 */

        LNew = (Node *)malloc(sizeof(Node));

        LNew->data = i;

        LNew->next = NULL;

        if(L == NULL){

            L = Head = LNew;

        }else{

            L->next = LNew;

        }

        L = LNew;

    }

    /* 返回头结点指针 */

    return Head;

}

int main()

{

    Node *p;

    p = LinkedListInit();

    while(p != NULL){

        cout << p->data << ' ';

        p = p->next;

    }

    cout << endl;

    return 0;

}