链表：
- 基本单位是节点。节点至少两部分：数据，下一个数据的地址。
- 头指针head，始终指向链表的第一个节点。若没有节点，则head=NULL。
- 链表在内存中是非连续的。不能使用索引（下标）查找元素。只能从头遍历。
- 链表有单链表、循环单链表、双链表、循环双链表。本文以单链表举例。
添加节点：（注意指向顺序，避免数据丢失）
- 在链表头部添加：先新节点指向第一个节点，再头指针指向新节点。
- 在链表尾部添加：最后一个节点指向新节点。
- 在链表指定位置添加：找到指定位置，先新节点指向下一个节点，再上一个节点指向新节点。
删除节点：
- 删除链表头部节点：头指针指向第二个节点。
- 删除链表尾部节点：倒数第二个节点指向NULL。
- 删除链表指定位置节点：找到指定位置，上一个节点指向该节点的下一个节点。
C语言代码：
创建节点（结构体数据类型），并创建具体节点实例的函数：
// 节点(结构体数据类型)
typedef struct Node
{
int data; // 数据为整数
struct Node *next; // 指针指向下一个节点
} LinkNode; // 别名LinkNode// 创建具体节点实例的函数
LinkNode * createNode(int data)
{
LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode)); // 给节点分配内存空间
if(node == NULL)
{
perror("Memory allocation failed");
exit(-1);
}
node->data = data;
node->next = NULL;
return node;
}
本文将头指针和链表长度作为全局变量：
LinkNode *header = NULL; // 头指针，初始化指向NULL
int length = 0; // 统计链表元素个数添加节点：
// 添加节点(链表头部添加)
void addtop(int data)
{
LinkNode *node = createNode(data); // 调用createNode函数,创建具体节点
node->next = header; // 先新节点指向头指针指向的节点
header = node; // 再头指针指向新节点
length++; // 每添加一个数据,length+1
}// 添加节点(链表尾部添加)
void append(int data)
{
if(length == 0) // 若空链表,在链表头部添加
{
addtop(data);
return ;
}
LinkNode *node = createNode(data);
LinkNode *cur = header; // 从头遍历元素，找到最后
while(cur->next != NULL)
{
cur = cur->next;
}
cur->next = node;
length++;
}// 添加节点(在指定位置,位置从0开始)
void insert(int location, int data)
{
if(length == 0) // 若空链表,在链表头部添加
{
addtop(data);
return ;
}
if(length <= location) // 若链表长度<=指定位置,在链表尾部添加
{
append(data);
return ;
}
LinkNode *node = createNode(data);
LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,找到指定位置
while(location > 0)
{
prev = cur;
cur = cur->next;
location--;
}
node->next = cur;
prev->next = node;
length++;
}删除节点：
// 删除节点（删除链表头部节点）
void deltop(void)
{
if(length == 0) return ; // 空链表,直接退出程序
header = header->next;
length--; // 每删除一个元素,length-1
}// 删除节点（删除链表尾部节点）
void pop(void)
{
if(length == 0) return ; // 空链表,直接退出程序
if(length == 1) // 一个元素,头指针直接指向NULL
{
header = NULL;
return ;
}
LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,直到最后的位置
while(cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
length--;
}// 删除节点（删除链表指定位置的节点,位置从0开始）
void delat(int location)
{
if(length == 0) return ; // 空链表,直接退出程序
if(length - 1 <= location) // 链表长度-1<=指定位置,删除链表尾部节点
{
pop();
return ;
}
LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,直到指定位置
while(location > 0)
{
prev = cur;
cur = cur->next;
location--;
}
prev->next = cur->next;
length--;
}// 删除节点(删除指定数据)
void del(int data)
{
LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,比对数据内容
while(cur != NULL)
{
if(cur->data == data)
{
if(header == cur) // 若是第一个节点,头指针直接跳过该节点指向下一个节点
{
header = cur->next;
}
else // 否则 该节点上一个节点,直接跳过该节点指向下一个节点
{
prev->next = cur->next;
}
length--;
return ;
}
prev = cur;
cur = cur->next;
}
return ;
}遍历节点：
void travel(void)
{
if(length == 0) return ; // 空链表,直接退出程序
printf("linklist elements: ");
LinkNode *cur = header;
while(cur != NULL)
{
printf("%d \t", cur->data);
cur = cur->next;
}
printf("\n");
}完整代码：（linklist.c）
#include <stdio.h>
#include <stdlib.h>
/* structure */
typedef struct Node // node structure
{
int data;
struct Node *next;
} LinkNode;
/* global variables */
LinkNode *header = NULL; // header pointer
int length = 0; // the number of linklist elements
/* function prototype */
void addtop(int data); // add element to the top of the linklist
void append(int data); // add element to the end of the linklist
void insert(int location, int data); // add element to the specify location (start with 0)
void travel(void); // show element one by one
void deltop(void); // delete element from the top of the linklist
void pop(void); // delete element from the end of the linklist
void delat(int location); // delete element from the specify location (start with 0)
void del(int data); // delete the specify data
/* main function */
int main(void)
{
addtop(5);
printf("length is %d \n", length);
travel();
append(9);
printf("length is %d \n", length);
travel();
insert(1,8);
printf("length is %d \n", length);
travel();
addtop(3);
printf("length is %d \n", length);
travel();
deltop();
printf("length is %d \n", length);
travel();
pop();
printf("length is %d \n", length);
travel();
delat(1);
printf("length is %d \n", length);
travel();
del(7);
printf("length is %d \n", length);
travel();
del(5);
printf("length is %d \n", length);
travel();
}
/* subfunction */
LinkNode * createNode(int data) // create a node
{
LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
if(node == NULL)
{
perror("Memory allocation failed");
exit(-1);
}
node->data = data;
node->next = NULL;
return node;
}
void addtop(int data) // add element to the top of the linklist
{
LinkNode *node = createNode(data);
node->next = header;
header = node;
length++;
}
void append(int data) // add element to the end of the linklist
{
if(length == 0)
{
addtop(data);
return ;
}
LinkNode *node = createNode(data);
LinkNode *cur = header;
while(cur->next != NULL)
{
cur = cur->next;
}
cur->next = node;
length++;
}
void insert(int location, int data) // add element to the specify location (start with 0)
{
if(length == 0)
{
addtop(data);
return ;
}
if(length <= location)
{
append(data);
return ;
}
LinkNode *node = createNode(data);
LinkNode *prev, *cur = header;
while(location > 0)
{
prev = cur;
cur = cur->next;
location--;
}
node->next = cur;
prev->next = node;
length++;
}
void travel(void) // show element one by one
{
if(length == 0) return ;
printf("linklist elements: ");
LinkNode *cur = header;
while(cur != NULL)
{
printf("%d \t", cur->data);
cur = cur->next;
}
printf("\n");
}
void deltop(void) // delete element from the top of the linklist
{
if(length == 0) return ;
header = header->next;
length--;
}
void pop(void) // delete element from the end of the linklist
{
if(length == 0) return ;
if(length == 1)
{
header = NULL;
return ;
}
LinkNode *prev, *cur = header;
while(cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
length--;
}
void delat(int location) // delete element from the specify location (start with 0)
{
if(length == 0) return ;
if(length - 1 <= location)
{
pop();
return ;
}
LinkNode *prev, *cur = header;
while(location > 0)
{
prev = cur;
cur = cur->next;
location--;
}
prev->next = cur->next;
length--;
}
void del(int data) // delete the specify data
{
LinkNode *prev, *cur = header;
while(cur != NULL)
{
if(cur->data == data)
{
if(header == cur)
{
header = cur->next;
}
else
{
prev->next = cur->next;
}
length--;
return ;
}
prev = cur;
cur = cur->next;
}
return ;
}
编译链接： gcc -o linklist linklist.c
执行可执行文件： ./linklist
