基本分类：
1、单向链表
2、带尾指针的单向链表
3、双向循环链表
以下分类进行说明
1、单向链表
基本元素：*front //头节点
*next //下一节点
声明：node<T>*p;
初始化：p=new node<T>(nodeValue,nextpointer);
简单遍历：
template <typename T>
void writeLinkedList(node<T> *front)
{
node<T> *curr;
curr=front;
while(curr!=NULL)
{
cout<<curr->nodeValue<<" ";
curr=curr->next;
}
}
插入元素
- 插在表头：
node<T> *newnode;
newnode=new node<T>(item,front); //使新节点的next指向头指针
front=newnode; //使新节点成为头指针
- 插在某位置：
node<T> *prev=NULL,*curr=front;
while(curr->nodevalue!=searchItem){
prev=curr;
curr=curr->next;
}
newnode->next=curr;
prev->next=newnode;
删除元素
- 删表头
node<T> *curr=front;
front=front->next;
delete curr;
- 删某元素
node<T> *prev=NULL,*curr=front;
while(curr->nodevalue!=searchItem){
prev=curr;
curr=curr->next;
}
prev->next=curr->next;
delete curr;
具体代码实现：
void eraseValue(node<T> *front,const T &target)
{
node<T>*curr=front,*prev=NULL;
bool FoundItem=false;
while(curr!=NULL && !FoundItem) //未到链表末尾且未找到节点
{
if(curr->nodeValue==target)
{
if(prev==NULL) //所删节点为头节点
front=front->next;
else
prev->next=curr->next;
delete curr;
FoundItem=true;
}
else
{
prev=curr;
curr=curr->next;
}
}
}
2、双指针单向链表
基本元素：单向链表的基础上加上
*back //尾指针
//各种操作与单向链表类似，加上在末尾插入数据和末尾删除，此处不一一列出
3、双向循环链表
表头（header）：
只包含prev指针和next指针 无data
dlinkedlist类
class dnode
{
public:
T nodeValue;
dnode <T> *prev;
dnode <T> *next;
dnode(){
next=this;
prev=this;
//构造表头，不含nodeValue
}
dnode(const T & value):
nodeValue(value)
{
next=this;
prev=this;
}
dnode <T> *insert (dnode <T>*curr,const T&item)
{
dnode<T> *newNode,*prevNode;
newNode=new dnode<T>(item); //调用有参构造函数
prevNode=curr->prev; newNode->prev=prevNode;
newNode->next=curr;
prevNode->next=newNode;
curr->prev=newNode; return newNode;
}
void erase(dnode<T> *curr)
{
if(curr->next==curr)//只有表头 空list
return; curr->prev->next=curr->next;
curr->next->prev=curr->prev; delete curr;
}
void writeDlinkedlist(dnode<T> *header)//遍历
{
dnode<T> *p=header->next;
while(p!=header)
{
cout<<p->nodeValue<<" ";
p=p->next;
}
}
}