单聊表

每个节点包含两个域：数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。每个指针都指向下一个节点，都是朝一个方向的，这样的链表称为单向链表或单链表。
链表 - 图1

  1. bool InitList_L(LinkList &L){
  2.     L = new LNode;
  3.     if(!L)     
  4.         return false;            //    生成节点失败
  5.     L->next = NULL;                //    头部指针域置空
  6.     return true;
  7. }
  1. void CreateList_H(LinkList &L){
  2.     int n;
  3.     LinkList s;
  4.     L = new LNode;
  5.     L->next = NULL;                //    建立空链表
  6.     cout<<"输入元素个数n"<<end;
  7.     cin>>n;
  8.     cout<<"输入n个元素"<<end;
  9.     while(n--){
  10.         s = new LNode;
  11.         cin>>s->data;
  12.         s->next = L->next;
  13.         L->next = s;
  14.     }
  15. }
  1. void CreateList_R(LinkList &L){
  2.     int n;
  3.     LinkList s, r;
  4.     L = new LNode;
  5.     L->next = NULL;                    //    建立空链表
  6.     r = L;                            //    尾指针指向头节点
  7.     cout<<"输入元素个数n"<<end;
  8.     cin>>n;
  9.     cout<<"输入n个元素"<<end;
  10.     while(n--){
  11.         s = new LNode;                //    生成新节点
  12.         cin>>s->data;                //    输入元素赋值给新节点数据域
  13.         s->next = NULL;
  14.         r->next = s;                //    新节点插入尾节点之后
  15.         r = s;                        //    r 指向新尾节点 s
  16.     }
  17. }

修改指针顺序为：先修改没有指针标记的那一端。若两端都有标记则可随意

  1. bool getElement(LinkList L,int i,int &e){
  2.     int j;
  3.     LinkList p;
  4.     p = L->next;
  5.     j = 1;
  6.     while(j < i && p){
  7.         p = p->next;        //    指针向后移
  8.         j++;                //    计数器 +1
  9.     }
  10.     if(!p || j>i)            //    检测是否超出范围
  11.         return false;
  12.     e = p->data;            //    取第 i 个节点的数据域
  13.     return true;
  14. }
  1. bool LocateElement(LinkList l,int e){
  2.     LinkList p;
  3.     p = L->next;
  4.     while(p && p->data != e){
  5.         p = p->next;
  6.     }
  7.     if(!p)
  8.           return false;
  9.     return true;
  10. }
  1. bool ListInsert_L(LinkList &L,int i,int e){
  2.     int j;
  3.     LinkList p , s;
  4.     p = L;
  5.     j = 0;
  6.     while(p && j < i - 1){
  7.         p = p -> next;
  8.         j++;
  9.     }
  10.     if(!p || j > i - 1)
  11.         return false;
  12.     s = new LNode;                //    生成新节点
  13.     s->data = e;                //    将数据元素e 插入新节点的数据域
  14.     s->next = p->next;            //    将新节点的指针域 指向 第 i 个节点
  15.     p->next = s;                //    节点 p  指向 节点 s
  16.     return true;
  17. }
  1. bool ListDelete_L(LinkList &L,int i){
  2.     LinkList q , p;
  3.     int j;
  4.     p = L;
  5.     j = 0;
  6.     while((p->next)&&(j < i - 1)){
  7.         p = p -> next;
  8.         j++;
  9.     }
  10.     if(!(p-> next) && (j > i - 1))
  11.         return false;
  12.     q = p->next;            //    临时保存要被删除的节点地址
  13.     p->next = q->next;        //    将 q 节点的下一个节点的地址赋给 p 的指针域
  14.     delete q;                //    删除节点，释放空间
  15.     return true;
  16. }

双向链表

单链表只能向后操作，不可以向前操作。为了向前、向后操作方便，可以给每个元素附加两个指针域，一个存储前一个元素的地址，另一个存储下一个元素的地址。
链表 - 图2

  1. bool InitList_L(DuLinkList &L){
  2.     L = new DuLNode;            //    生成新节点
  3.     if(!L)
  4.         return false;
  5.     L->prior = L->next = NULL;    //    头节点的两个指针域置空
  6.     return true;
  7. }
  1. void CreateDuList_H(DuLinkList &L){
  2.     int n;
  3.     DuLinkList s;
  4.     L = new DuLNode;
  5.     L->prior = L->next = NULL;
  6.     cout<<"请输入元素个数n:"<<endl;
  7.     cin>>n;
  8.     cout<<"输入n 个 元素"<<endl;
  9.     while(n--){
  10.         s = new DuLNode;    //    生成新节点 s
  11.         cin>>s->data;        //    输入元素值赋值给 新节点的 数据域
  12.         if(L->next)            
  13.             L->next->prior = s;
  14.         //    将 s 插入 头节点之后
  15.         s->next = L->next;
  16.         s->prior = L;
  17.         L->next = s;
  18.     }
  19. }
  1. bool ListInsert_L(DuLinkList &L, int i ,int &e){
  2.     int j;
  3.     DuLinkList p , s;
  4.     p = L;
  5.     j = 0;
  6.     while(p && j < i){
  7.         p = p->next;
  8.         j++;       
  9.     }
  10.     if(!p || j > i)
  11.         return false;
  12.     s = new DUlNode;
  13.     s->data = e;
  14.     p->prior->next = s;
  15.     s->prior = p->prior;
  16.     s->next = p;
  17.     p->prior = s;
  18.     return true;
  19. }
  1. bool ListDelete_L(DuLinkList &L,int i){
  2.     DuLinkList p;
  3.     int j;
  4.     p = L;
  5.     j = 0;
  6.     while(p && (j < i)){
  7.         p = p -> next;
  8.         j++;
  9.     }
  10.     if(!p || (j > i))
  11.         return false;
  12.     if(p->next)                            //    如果有后续节点
  13.         p->next->prior = p ->prior;    //将 p 节点的后续节点的前驱指针域，指向 p 节点的前一个节点
  14.     p->prior->next = p ->next;    // 将 p 节点的前一个节点的后继指针域，指向 p 的节点的下一个节点
  15.     delete p;
  16.     return true;
  17. }

循环链表

单链表中，只能向后，不能向前。如果从当前节点开始，无法访问该节点前面的节点，而最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问所有的节点，这就是循环链表。循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。