链表基本概念：
链表：线性表的链式存储。
数据域：存储数据信息。即数据。
指针域：存放下一节点的位置信息。即该指针指向下一节点。
单链表：每一个节点node：一个数据域 + 一个指针域。
头节点：
1、数据域可以存放线性表长度等公共信息。
2、指针域，指向第一个节点（数据域）的位置。
3、头结点不一定是链表的必须元素。不过有了头结点，对第一个元素节点前插入和删除元素，就和其它节点一致了。
4、头结点是为了操作的同一和方便设立的，其数据域一般无意义，也可存放链表长度。
头指针：指向第一个结点的指针。
最后一个节点：数据域存放数据；指针域为空，即NULL。
若线性表为空，则头节点的指针域为空。
// 循环链表：将单链表中的终端节点的指针由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表简称循环链表。
// 双向链表：是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。
单链表基本操作有：创建、输出、测长、插入、删除、逆置、排序等。
单链表结构定义代码：
typedef struct Node{ int data; struct Node *next; }ListNode;创建单链表操作：
/**创建链表*/ ListNode * Create_list(int n) // 注意这里函数返回值为一个指向Node的指针，n表示几个节点 { int elem,i; i = 1; ListNode *head, *current, *temp; /*current：代表一个当前节点，它的下一节点是你正要创建的；temp：代表你正要创建的节点。*/ head = new ListNode; head->next = NULL; head->data = n; current = head; while(i <= n) /*尾插法：即新节点放在尾部*/ { cout << "please input elem: " << endl; cin >> elem; temp = new ListNode; temp->data = elem; temp->next = NULL; current->next = temp; current = temp; i++; } return head; }输出操作：
/**输出链表*/ int Output_list(ListNode *head) { ListNode *p; p = head->next; if(p == NULL) { cout << "The List is NULL" << endl; return 0; } do{ cout << p->data << ' '; p = p->next; }while(p != NULL); // 这里需要加“；” cout << endl; return 0; }测一个链表的节点数，即长度：
/**测长度*/ int Length_test(ListNode *head) { ListNode *p; int i = 0; p = head->next; while(p != NULL) { i++; p = p->next; } cout << "The length of list is " << i << endl; return 0; }插入节点操作：
/**在第i个节点后插入一个节点，elem：表示你要插入的数据*/ ListNode * Insert_node(ListNode *head,int elem,int i) { int j = 0; ListNode *p,*temp; temp = head->next; /*错误写法 while(NULL != temp) 在找到 j 后没有跳出循环 { j++; if(j <= i) temp = temp->next; } */ while(NULL != temp) { j++; if(j >= i) /**指针停在第i个节点之前*/ break; temp = temp->next; } if(temp == NULL) { cout << "There is no i" << endl; return head; } p = new ListNode; p->data = elem; p->next = temp->next; temp->next = p; head->data = head->data + 1; /**插入一个结点，头结点数据保存的链表长加一*/ return head; }删除操作：
/**删除第i个结点*/ ListNode * Delete_node(ListNode *head,int i) { int j = 0; ListNode *temp,*pre_temp; temp = head->next; while(NULL != temp) { j++; if(j >= i) break; pre_temp = temp; /**保存之前节点*/ temp = temp->next; } if(temp == NULL) { cout << "There is no i" << endl; return head; } pre_temp->next = temp->next; /**这里不能写成temp = temp->next; 因为下面有 delete temp;会将后面的节点删掉*/ delete temp; head->data -= 1; /**删掉一个结点，头结点数据保存的链表长减一*/ return head; }