1、Definition
Linked list consists of a series of nodes. Each nodes contains the element and a pointer which points to the next node. The last node‘s next link points to NULL.
Linked=data+pointer
use the pointer to describe the logical relationship
2、Implementation
template<class List_entry>
class List
{
public:
List();
int size();
bool empty();
bool full();
...
protected:
int count;
Node<List_entry> *head; //当声明一个linked时，只会拥有一个头指针
}
template<class List_entry>
struct Node
{
List_entry entry; // data
Node<List_entry> *next; // point to the next node
Node();
Node(List_entry, Node<List_entry>*link=NULL);
}
3、Operations
(1)two types of insert
①在p节点所在位置插入
New(S) S->data=a; q->next=S; S->next=p;
②在p节点之后插入
New(S) S->data=a; S->next=p->next; p->next=S;
(2) create a linked list
In order to create a linked list, we have this algorithm
①To create a head
②To create new node S
③Insert S
void CreateList(Head)
{
new(Head);
Head->next=NULL;
scanf("%c",ch);
while(ch<>‘#‘)do
{
new(S);
S->data=ch;
S->next=Head->next;
Head->next=S;
}
}
上述构造方式为从头构造，在头元素出一个一个地插入
下面一种是从链尾增添
void CreateList(Head)
{
new(Head);
Head->next=NULL;
Last=Head;
scanf("%c",ch);
while(ch<>‘#‘)do
{
new(S);
S->data=ch;
S->next=NULL;
Last->next=S;
Last=S;
}
}
(3)insert an element at location i
Status ListInsert L(LinkList &L, int i, DataType e)
{
LinkList p, s;
p=L;
int j=0;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!p) return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
(4)Delete
Status ListDelete(LinkList &L, int i)
{
LinkList p, q;
p=L;
int j=0;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!p) return ERROR;
q=p->next;
p->next=q->next;
free(q);
}
(5)Search
①按位查找
Status ListSearch(LinkList &L, int i)
{
LinkList p;
int j=0;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!p)return ERROR;
e=p->next;
return OK;
}
③按值查找
Status ListSearch(LinkList &L, DataType e)
{
LinkList p;
p=L;
int j=0;
while(p&&(p->next)!=e)
{
p=p->next;
j++;
}
if(!p)
{
cout<<"Not found"<<endl;
return ERROR;
}
else
{
return (j);
}
}
3、circular linked list
4、Doubly linked list
(1)Insert
p->next=current->next; p->prior=current; current->next->prior=p; current->next=p;
(2)Delete
current->next->prior=current->prior; current->prior->next=current->next;
原文：http://www.cnblogs.com/KennyRom/p/5879716.html