零、先决条件
要学习链表，您应当懂得如何使用struct和typedef的用法，和 C++ 语言的一定基础。可以参考文章《数据结构简明入门教程》。
链表亦可以使用类进行创造，本文采用 C++ 语言的结构进行创造。
一、链表的创建
在《数据结构简明入门教程》的第三部分，我们已经了解了链表。接下来将直接介绍链表的创建。
我们先构造一个最简单的链表：只有一个头指针和一个节点。
链表示意图1
先决条件下，我们创造一个链表的结构。该链表包含数据部分和指针部分。
struct ListNode
{
int data; //数据
ListNode *link; //下一个地址的指针
};
typedef ListNode* ListNodePtr; //我们设指向节点的指针类型叫 ListNodePtr。
//Ptr是 pointer 的缩写，即指针。我们先创造一个头指针，使之指向一个节点。
ListNodePtr head;
head = new ListNode;使用箭头操作符对该节点进行赋值。由于没有后续节点，link部分我们设为NULL或nullptr。
head -> data = 12;
head -> link = nullptr; //指向“空”这样，我们就造好了一个链表。可以用以下代码验证我们真的把数据存进去了：
cout << head -> data;二、在链表的头部插入节点
链表的头部，通常被称作首元节点。我们现在写一个函数，使得可以插入任意链表的头部。
假设头指针已经定义好为head。
void InsertAfterHead(ListNodePtr &head, int data){
//注意，上方 head 前要有“&”，因为我们需要修改 head 的值。
cin >> data; //传入新节点 data
ListNodePtr temp; //创建一个“指向新节点的指针”
temp = new ListNode; //该指针指向一个新节点
temp -> data = data; //把 data 写入新节点
temp -> link = head; //新节点的指针用原来的头指针
head = temp; //把原来的头指针换做“指向新节点的指针”
}三、查找节点
假设有下图的结构，我们需要查找第一项值为9的节点，并将其改为6。
链表示意图2
我们设计一个函数，返回值类型是指针，以命中符合要求的链表的节点。
LinkNodePtr Search(LinkNodePtr head, int target){
//head 为头指针，target 是要查找的目标值
LinkNodePtr here = head; //设置一个指针，并使之指向头部
bool gotIt = false; //设置一个判断标志，如果标志为真则证明找到了目标
for(; here != nullptr; here = here -> link){
//当指针没有到链表尾部（为空）时进行，并搜索完一个就跳到下一个链表的地址
if(here -> data == target){
gotIt = true;
break;
//如果找到了，就退出循环
}
}
if(gotIt) return here;
else return nullptr;
}LinkNodePtr target = Search(head, 9);
target -> data = 6;对于上述代码中的 for 循环行为，有一个很酷的名字——迭代。指针here叫做迭代器。
for(LinkNodePtr here = head; here != nullptr; here = here -> link){
//需要迭代做的事情
}比如这样就可以逐一打印链表的数据：
for(LinkNodePtr here = head; here != nullptr; here = here -> link){
cout << here -> data << endl;
}四、插入节点
假如我们需要找到第一个值为6的节点，并在其后插入数据9。
我们写一个插入函数，可以在指定的地址after_me后插入一个节点。
void Insert(LinkNodePtr &after_me, int data){
LinkNodePtr temp;
temp = new LinkNode;
temp -> data = data;
temp -> link = after_me -> link;
after_me -> link = temp;
}为了方便，我们沿用上面写好的Search函数。可以得到下面的代码：
LinkNodePtr target = Search(head, 6);
Insert(target, 9);五、删除节点
删除节点，即从把该节点上方的指针直接指向下方节点地址。
假设指向上方节点的指针为before，指向待删除的指针为discard。
before -> link = discard -> link;
delete discard; //如果要永久删除，使用 delete六、后记
关于其他的链表，如双向链表、循环链表，请参考教材。相信你看到这里已经能够学会了。
七、参考资料
Walter Savitch 《 C++入门经典（第九版）》。