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{  public:     List();      int size();     bool empty();     bool full();     ...  protected:     int count;     Node
      
        *head;             //当声明一个linked时，只会拥有一个头指针}template
       
        struct Node{  List_entry entry;                            // data  Node
        
          *next;               // point to the next node     Node();  Node(List_entry, Node
         
          *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
     
      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
     
      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
     
      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"<

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;

 

　C++style code

//C++style构建链表，有头结点//operations/*LenList(L)链长GetElem(i, e)换值SearchElem(e, i)按值查找InertElem(i, e)插值DeleteElem(i) 删值*/template
     
      struct Node{	Type data;	Node
      
       *next;};template
       
        class LinkList{public:	LinkList()	{		head = new Node
        
         ;		head->next = NULL;		len = 0;		Type ch;		Node
         
          *p;		while (cin >> ch)		{			p = new Node
          
           ; p->data = ch; p->next = head->next; head->next = p; len++; } } ~LinkList() { Node
           
            *p = head; while (p->next) { DeleteElem(); } delete head; } //LenList(L)链长 int LenList() { return len; } //InertElem(e)从尾插值 void InsertElem(Type e) { Node
            
             *p = head; while (p->next) { p = p->next; } Node
             
              *q = new Node
              
               ; q->data = e; q->next = p->next; p->next = q; len++; } //InertElem(i, e)从第i位插值 void InsertElem(int i, Type e) { Node
               
                *p = head; int j = 0; while (p->next && j
                next; } Node
                 
                  *q = new Node
                  
                   ; q->data = e; q->next = p->next; p->next = q; len++; } //GetElem(i, e)换值 void GetElem(int i, Type e) { int j = 0; Node
                   
                    *p = head; while (p->next && j
                    next; } p->next->data = e; } //DeleteElem(i) 第i位删值 void DeleteElem(int i) { int j = 0; Node
                     
                      *p = new Node; while (p->next && j
                      next; } Node
                       
                        *q = p->next; p->next = q->next; delete q; len--; } //DeleteElem() 尾删值 void DeleteElem() { Node
                        
                         *p = head; while (p->next->next) { p = p->next; } Node
                         
                          *q = p->next; p->next = q->next; delete q; len--; } //SearchElem(e)按值查找 int SearchElem(Type e) { Node
                          
                           *p = head; int i = 0; while (p->next && p->data != e) { i++; p = p->next; } if (i == 0) return -1; else return i; } //SearchElem(i)按位查找 Type SearchElem(int i) { Node
                           
                            *p = head; int j = 0; while (p->next && j
                            
                             next; } return p->data; }private: Node
                             
                              *head; int len;};