有的时候，处于内存中的数据并非连续的。那么这时候。我们就须要在数据结构中加入一个属性。这个属性会记录以下一个数据的地址。有了这个地址之后。全部的数据就像一条链子一样串起来了，那么这个地址属性就起到了穿线连结的作用。
链表有：单链表。双链表，单循环链表。双循环链表。
理解单链表，其它几种也就大同小异。
相比較普通的线性结构，链表结构的优势是什么呢？我们能够总结一下：（1）单个节点创建很方便。普通的线性内存通常在创建的时候就须要设定数据的大小
（2）节点的删除很方便，不须要像线性结构那样移动剩下的数据
（3）节点的訪问方便，能够通过循环或者递归的方法訪问到随意数据，可是平均的訪问效率低于线性表
那么在实际应用中，链表是怎么设计的呢？我们能够以int数据类型作为基础，设计一个简单的int链表：
#include <iostream>
#include <cstdlib>
using namespace std;
struct list_node{
int data;
list_node *next;
};
class list{
public:
list():head(NULL){};
~list();
void print();
void insert(int value);
/*you had better insert from the front list,that costs O(1),
*here i just insert into the taile, costing O(n)
*/
void insert_back(int pos, int value);//inisert a node with value equals to value after the node with value equals to pos
void delete_back(int pos);//delete the node after the node with value equals to pos
protected:
list_node* find(int pos); //find the node with the value equals to pos
private:
list_node* head; //point to the first node
};
list::~list()
{
}
list_node* list::find(int pos)
{
if(NULL==head)
return NULL;
list_node* tmp=head;
while((NULL!=tmp)&&(tmp->data!=pos))
tmp=tmp->next;
return tmp;
}
void list::insert(int value)
{
if(head==NULL)
{
head = new list_node();
head->data=value;
head->next=NULL;
}
else
{
list_node *tmp= head;
while(tmp->next!=NULL)
tmp=tmp->next;
list_node *node = new list_node();
node->data=value;
node->next=NULL;
tmp->next=node;
}
}
void list::insert_back(int pos, int value)
{
list_node *tmp = find(pos);
if(NULL==tmp)
return;
else
{
list_node *node = new list_node();
node->data=value;
node->next=tmp->next;
tmp->next=node;
}
}
void list::delete_back(int pos)
{
list_node *tmp = find(pos);
if(NULL==tmp)
{
cout<<"the value of pos isnot exist"<<endl;
return;
}
else
{
if(tmp->next==NULL)
{
cout<<"pos is the last node"<<endl;
return;
}
else
{
tmp->next=tmp->next->next;
}
}
}
void list::print()
{
list_node *tmp = head;
while(tmp!=NULL)
{
cout<<tmp->data<<" ";
tmp=tmp->next;
}
cout<<endl;
}
int main()
{
list myList;
for(int i=1;i<10;++i)
{
myList.insert(i);
}
myList.print();
myList.insert(11);
myList.print();
myList.insert_back(5, 555);
myList.print();
myList.delete_back(6);
myList.print();
}
执行结果：
