如何构建一个简单链表

一、含构造函数和默认实参的结构体

    typedef struct node {int data;struct node* next;node(int data = 0, struct node* next = NULL): data(data), next(next) {}} node;

二、创建一个一定长度的链表

(一) 错误样例：

    int n = 3;node* head = NULL;node* p = head;while (n--){p = new node(n);p = p->next;}

在这个样例中，不管是head也好，head->next 也好，更别说head->next->next, 都没有分配到空间，全都给了变量p。也就是说，不能通过另一个指向同一块内存区域的指针来为这块内存分配空间, 因为一开始head = NULL，你node* p = head 实际上就是 node* p = NULL；所以实际上错误样例是创建了一个与head无关的链表

(二) 正确样例：

1.  样例一：使用普通指针

    int n = 3;node* head = NULL;head = new node(n);node* p = head;while (--n){p->next = new node(n);p = p->next;}2.  样例二：使用指针的指针int n = 3;node* head = NULL;node* *p = &head;while (n--){*p = new node(n);p = &((*p)->next);  //*p 完全等效于他说指向的指针，所以易知，这里并不/能写作*p = (*p)->next;}

三、单个数据的插入

(一) 首先是插入位置的选择：

插入的位置从0开始算，小于size+1（这里的size为4）（注意！是不能插入到再大的位置上的）

(二) 如果位置合理，就先给要加入的值申请空间

   node* a = new node;

(三) 插入的位置为0

    if( position == 0 ){a->next = head;head = a;size++;return;}

(四) 插入位置不为0的情况

    node* p = head;node* q = head;while(position--){p = q;q = q->next;}p->next = a;a->next = q;size++;return;

四、单个数据的删除

(在链表操作中比较重要的环节，非常容易产生失误导致崩溃或者内存泄漏)

(一) 首先是删除位置的选择：

删除的位置从0开始算，且小于size，（这里size为4，其实这样也就避免了size为0或者说head为NULL的情况）

(二) 删除的位置为0的情况：

    if(position == 0){node*k = head->next;delete head;head = k;size--;return;}

(三) 删除的位置不为0的情况：

    node*p = head;node*q = head;while(position--){q = p;p = p->next;}p->next = q->next;delete p;size--;

五、链表数据的排序

这里采用了选择排序法，同理其他的排序方法也行

    if(head == NULL || head->next == NULL)return;          //首先判断能不能排序或者有没有必要排序：for(p = head; p->next != NULL; p=p->next)for(q = p->next; q != NULL; q=q->next){if(p->data > q->data){a = p->data;p->data = q->data;q->data = a;}}

六、完全删除一个链表的方法：

        if(head != NULL) {node* p = head;while(p != NULL){node* temp = p;p = p->next;delete temp;} head = NULL;} size = 0

七、需要注意的地方

(一) 初始化
1. 要记得初始化，尤其是将head指针指向NULL（一般是不会帮你指向NULL的，要自己显示地打出来）
2. 给指针初始化的时候，比方说：node* p = q; 这时一定要判断q是不是NULL，如果是的话，这样的初始化就等价于： node* p = NULL, 这样一来p就和q没有任何关系
(二) Delete
要注意不能delete没有申请空间的变量，而且重复delete一个变量会造成崩溃