单链表：
一.单链表与顺序表相比：
1.顺序表可以方便的随机存取表中的任一节点，速度快；但是在表中插入删除一个数据时，为了保持其他元素的相对次序不变，平均需要移动一半的元素，效率很低；还有若事先对表长估计不足，过小会形成内存浪费，过大则需要拷贝到一个更大的数组，时间开销很大。相反，链表则适用于插入删除频繁，表长估计不定的情形。
2.顺序表逻辑位置和物理位置都连续，而单链表中的逻辑位置连续，物理位置非连续。
二.为什么要带附加表头？
因为不带附加表头在插入删除时要分两种情况：操作节点在表头和不在表头；而带了附加表头便可以对所有节点一视同仁。
template<class T>
struct LinkNode{//链表节点
T data;
LinkNode *link;
LinkNode(const T& args,LinkNode<T> *ptr=NULL){
data=args;
link=ptr;
}
}; template<class T>
class List{//带附加头节点的单链表
protected:
LinkNode<T> *first;//链表头指针
public:
List(){
first=new LinkNode<T>;
}
List(const T& x){
first=new LinkNode<T>(x);
}
List(List<T>& L){
T value;
LinkNode<T> *L_head=L.getHead();
LinkNode<T> *temp=first=new LinkNode<T>;
while(L_head->link!=NULL){
value=L_head->link->data;
temp->link=new LinkNode<T>(value);
L_head=L_head->link;
temp=temp->link;
}
temp->link=NULL;
}
~List(){
makeEmpty();
}
void makeEmpty(){//将链表置空
LinkNode<T> *temp;
while(first->link!=NULL){
temp=first->link;
first->link=temp->link;
delete temp;
}
}
int length()const{
LinkNode<T> *temp=first->link;
int count=;
while(temp!=NULL){
temp=temp->link;
count++;
}
return count;
}
LinkNode<T> *getHead()const{//返回附加头节点地址
return first;
}
LinkNode<T> *search(T x,int& i){//搜索数据x的地址和序列号
LinkNode<T> *current=first->link;
int index=;
while(current!=NULL){
if(current->data==x)
break;
current=current->link;
index++;
}
i=index;
return current;
}
LinkNode<T> *locate(int i){//搜索第i个节点的地址
if(i<)
return NULL;
LinkNode<T> *current=first;
int temp=;
while(current!=NULL&&temp<i){
current=current->link;
temp++;
}
return current;
}
bool getData(int i,T& x){//取出第i个元素的值
if(i<=)
return false;
LinkNode<T> *current=locate(i);
if(current==NULL) return false;
x=current->data;
return true;
}
void setData(int i,T& x){//修改第i个元素的值
if(i<=)
return;
LinkNode<T> *current=locate(i);
if(current==NULL) return;
current->data=x;
}
bool insert(int i,T& x){//在第i个元素后插入x
LinkNode<T> *current=locate(i);
if(current==NULL) return false;
LinkNode<T> *newNode=new LinkNode<T>(x);
newNode->link=current->link;
current->link=newNode;
return true;
}
bool remove(int i,T& x){//删除第i个元素的值
LinkNode<T> *current=locate(i-);
if(current==NULL||current->link==NULL) return false;
LinkNode<T> *del=current->link;
current->link=del->link;
x=del->data;
delete del;
return true;
}
bool isEmpty()const{
return (first->link==NULL)?true:false;
}
void inputFront(){//向前插入链表法
makeEmpty();
LinkNode<T> *newNode;
T value;
cin>>value;
while(value!=-){
newNode=new LinkNode<T>(value);
newNode->link=first->link;
first->link=newNode;
cin>>value;
}
}
void inputRear(){//向后插入链表法
makeEmpty();
LinkNode<T> *newNode,*last=first;
T value;
cin>>value;
while(value!=-){
newNode=new LinkNode<T>(value);
last->link=newNode;
last=newNode;
cin>>value;
}
}
void output(){//输出整个链表
LinkNode<T> *current=first->link;
while(current!=NULL){
cout<<current->data<<" ";
current=current->link;
}
cout<<endl;
}
};
测试代码如下：
void menu(){
cout<<"1.向前插入建表（-1结束）"<<endl;
cout<<"2.向后插入建表（-1结束）"<<endl;
cout<<"3.输出链表"<<endl;
cout<<"4.搜索元素x所在节点的序号"<<endl;
cout<<"5.取出第i个元素的值"<<endl;
cout<<"6.用x的值修改第i个元素的值"<<endl;
cout<<"7.删除第i个元素"<<endl;
cout<<"8.在第i个元素后面插入x"<<endl;
cout<<"9.退出"<<endl;
}
template<class T>
void function(int num,List<T> *list){
switch(num){
int x,i;
case :
list->inputFront();
break;
case :
list->inputRear();
break;
case :
list->output();
break;
case :
cin>>x;
list->search(x,i);
cout<<i<<endl;
break;
case :
cin>>i;
list->getData(i,x);
cout<<x<<endl;
break;
case :
cin>>x>>i;
list->setData(i,x);
break;
case :
cin>>i;
list->remove(i,x);
break;
case :
cin>>i>>x;
list->insert(i,x);
break;
default:
exit();
}
}
int main(int argc, char** argv) {
int num;
List<int> *list=new List<int>(-);
while(true){
menu();
cin>>num;
function(num,list);
}
return ;
}
其次是循环链表：
代码我就不放了，就讲讲要修改的地方：
1.构造函数。first=new LinkNode<T>;后面接上:first->link=first;目的是让自身首尾相连。如图：
2.在判断循环指针是否到达表尾的条件要从NULL换成first。
小结：
循环链表的目的是只要知道表中任一一个节点的地址，就能遍历表中其他任一节点。
最后是双向链表：
修改：
1.节点的构造函数。需要增加一个前驱指针。
2.搜索、插入删除算法。首先是方向，确定方向后算法和单链表差不多，区别在于通过前驱指针还是后续指针访问节点。其次是插入删除，讲起来比较啰嗦，直接看图：
这是插入（中间是插入元素），虚线是原来的情况，实线是插入后的情况，可见一共涉及到4个指针。
这是删除（中间是删除元素）。看上去也是涉及4个指针，实际只动了1和4。
小结：
双向链表的目的是为了解决在链表中不同方向（前/后）访问元素的问题。