♥注：未经博主同意，。
线性表的链式存储结构的特点是用一组任意的存储单元来存储线性表的数据元素，这些单元可以分散在内存中的任意位置上，其在物理上可以是连续的，也可以是不连续的。具有链式存储结构的线性表称为线性链表。
为了表示出每个数据元素与其后继之间的关系，除了存储数据元素本身的信息之外，还需存储指示其直接后继的信息。这可以用一个结点（node）来完整的表示。
将节点中存储数据元素本身信息的域称为数据域；存储其直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。
一般情况下，链表中每个结点可以包含若干个数据域和若干个指针域。如果每个结点中只包含一个指针域，则称其为单链表。
为了便于实现各种操作，可以在单链表的第一个结点之前增设一个结点，称为头结点，其他结点称为表结点。
带头结点的单链表描述如下：
1 typedef int Data; 2 3 struct Node 4 { 5Data data;//数据 6Node* next; //指针 7 }; 8 9 class LinkList10 {11Node* head;//创建头结点12public:13LinkList() //构造函数14{15 head = new Node;16 head->next = NULL;17}18~LinkList();//析构函数19Data GetElem(int i);//取第i个元素的值20bool IsEmpty(); //判断是否为空链表21void Create(Data* a , int n); //创建长度为n的单链表(头插法)22void Create1(Data* a , int n); //创建长度为n的单链表(尾插法)23Node* Locate(Data e,int* i); //查找值为e的结点，返回指向e的指针24void Insert(Data x,int i); //将数据元素x插入到第i个位置25Data Delete(int i);//删除第i个元素26//int _Delete(Data e);//删除值为e的第一个元素27int Size(); //返回链表的长度28void Clear();//清空29void Print();//显示元素30 };31
下面则是这些操作在单链表上的实现：
1 //计算链表长度 2 int LinkList::Size() 3 { 4Node* p; //创建指针p 5int k; 6p=head->next;////p指向第一个元素结点 7k=0; 8while(p) 9{ 10 p=p->next; 11 ++k; 12} 13return k; 14 } 15 16 //显示所有元素 17 void LinkList::Print() 18 { 19Node* p; //创建指针p 20p=head->next;////p指向第一个元素结点 21while(p)22{ 23 cout<<p->data<<" "; 24 p=p->next; 25} 26cout<<endl; 27 } 28 29 //取元素 30 Data LinkList::GetElem(int i) 31 { 32if(head->next == NULL) //为空链表 33{ 34 cout<<"此链表为空"<<endl; 35 exit(0); 36} 37else 38{ 39 Node* p; //创建指针p 40 int k; 41 p=head;//p指向头结点 42 k=0; 43 while(p&&k<i) //p移到i的位置 44 { 45 p=p->next; 46 k++; 47 } 48 if(!p||k>i) //超出个数范围 49 { 50 cout<<"第"<<i<<"个元素不存在"<<endl; 51 exit(0); 52 } 53 return (p->data); 54} 55 } //此算法的时间复杂度为O(n) 56 57 //插入操作 58 void LinkList::Insert(Data x,int i) 59 { 60Node* p=head; 61int k=0; 62while(p&&k<i-1) // 将p指到第i个位置 63{ 64 p=p->next; 65 ++k; 66} 67if(!p||k>i-1) //判断是否存在第i个元素 68{ 69 cout<<"第"<<i<<"个元素不存在"<<endl; 70 exit(0); 71} 72Node* s = new Node; //创建此结点 73if(!s) 74{ 75 cout<<"空间分配失败"<<endl; 76 exit(0); 77} 78s->data=x;//将元素存入创建的结点 79s->next=p->next; 80p->next=s; 81 } 82 83 //删除操作 84 Data LinkList::Delete(int i) 85 { 86Node* p = head; 87int k=0; 88while(p&&k<i-1)//将p指到要删除的位置 89{ 90 p=p->next; 91 ++k; 92} 93if(!p||p->next==NULL) //判断删除位置是否存在和是否有后继 94{ 95 cout<<"删除位置非法"<<endl; 96 exit(0); 97} 98Node* q = p->next; //暂存删除结点 99p->next = q->next; //将结点隔离出来100Data e=q->data;//将删除的元素储存起来101delete q;//释放将要删除的结点102return e;103 }104 105 bool LinkList::IsEmpty()106 {107if(head->next==NULL)108{109 cout<<"此链表为空"<<endl;110 return true;111}112else113{114 cout<<"此链表非空"<<endl;115 return false;116}117 }118 119 //建立单链表120 //第一种是头插法121 void LinkList::Create(Data* a,int n)122 {123Node* p=NULL;124Node* q=NULL;125for(int i=n-1;i>=0;--i)126{127 p=new Node;//创建新结点128 p->data=a[i];//将元素存入结点129 p->next=head->next; //将新加入结点指向头结点后面130 head->next=p;//将头结点指向新加入的结点131}132 }133 134 //第二种是尾插法135 void LinkList::Create1(Data* a,int n)136 {137Node* p=NULL;138Node* q=head;//创建中间结点指针139for(int i=0;i<n;++i)140{141 p=new Node;//创建储存元素的新结点142 p->data=a[i];//将元素存入创建的结点143 p->next=q->next; //插入到终端结点之后144 q->next=p;//终端结点指向新建结点145 q=p; //q指向新建结点146}147p->next=NULL;148 }149 150 //查找给定值的结点151 Node* LinkList::Locate(Data e,int *i)152 {153*i=1;154Node* p=NULL;155p=head->next;156while(p) //p不为空157{158 if(p->data==e)//找到元素159 return p;160 else161 {162 p=p->next;163 ++(*i);164 }165}166cout<<"当前链表中无此元素"<<endl;167exit(0);168return NULL;169 }170 171 //清空单链表172 //保留表头结点，把单链表中的173 //其余所有结点全部释放。174 void LinkList::Clear()175 {176Node* p=NULL;177Node* q=NULL;178p=head->next;179while(p)180{181 q=p;182 p=p->next;183 delete q;184}185head->next = NULL;186 }187 188 //析构函数189 //释放单链表中的所有元素。190 LinkList::~LinkList()191 {192Node* p;193p=head;194while(p)195{196 p=p->next;197 delete head;198 head=p;199}200 }
需要注意的几点：
1.在创建链表时有两种创建方法，即头插法和尾插法，具体怎么实现请看下图：
2.在创建终结点（即屁股结点）时要注意指向下一个结点的指针要进行处理：p->next=NULL;
3,在用完链表后要记得进行销毁（释放内存），可以在析构函数中完成。
最后则是函数的测试，放在main函数里：
1 int main() 2 { 3int i=0; 4Data e; 5int a[8]={2,4,6,8,5,1,7,9}; 67LinkList list;//创建链表类 8list.IsEmpty();//判断链表是否为空 9list.Create(a,8);//将数据插入10list.Print();//显示11cout<<"链表长度："<<list.Size()<<endl;1213cout<<"输入要插入的元素和位置：";14cin>>e>>i;15list.Insert(e,i);//插入数据16list.Print();17cout<<"当前链表长度为"<<list.Size()<<endl<<endl;1819cout<<"输入要插入的元素和位置：";20cin>>e>>i;21list.Insert(e,i);22list.Print();23cout<<"当前链表长度为"<<list.Size()<<endl<<endl;2425cout<<"输入要插入的元素和位置：";26cin>>e>>i;27list.Insert(e,i);28list.Print();29cout<<"当前链表长度为"<<list.Size()<<endl<<endl;3031cout<<"输入要查找的元素值：";32cin>>e;33list.Locate(e,&i);//查找某元素34cout<<"这是第"<<i<<"个元素"<<endl<<endl;3536cout<<"输入要查找的元素值：";37cin>>e;38list.Locate(e,&i);39cout<<"这是第"<<i<<"个元素"<<endl<<endl;4041list.IsEmpty();//判断链表是否为空4243cout<<"输入要查找的元素位置：";44cin>>i;45e=list.GetElem(i);//查找第i个位置的元素46cout<<"这个元素值为："<<e<<endl<<endl;4748cout<<"输入要查找的元素位置：";49cin>>i;50e=list.GetElem(i);//查找第i个位置的元素51cout<<"这个元素值为："<<e<<endl<<endl;5253list.IsEmpty();//判断链表是否为空5455cout<<"输入要删除的元素位置：";56cin>>i;57e=list.Delete(i);//删除第i个位置的元素58cout<<"这个元素值为："<<e<<endl;59list.Print();60cout<<"当前链表长度为"<<list.Size()<<endl<<endl;6162cout<<"输入要删除的元素位置：";63cin>>i;64e=list.Delete(i);//删除第i个位置的元素65cout<<"这个元素值为："<<e<<endl;66list.Print();67cout<<"当前链表长度为"<<list.Size()<<endl<<endl;6869list.Clear();70list.IsEmpty();//判断链表是否为空7172return 0;73 }
最后则是程序运行后的画面了：
到这里线性表链式存储中的单链表就结束了，下次内容则是双链表的实现。
