单链表，循环链表和双向链表

绝地灬酷狼 2022-05-26 11:27 336阅读 0赞

单链表：  
　　一.单链表与顺序表相比：

1.顺序表可以方便的随机存取表中的任一节点，速度快；但是在表中插入删除一个数据时，为了保持其他元素的相对次序不变，平均需要移动一半的元素，效率很低；还有若事先对表长估计不足，过小会形成内存浪费，过大则需要拷贝到一个更大的数组，时间开销很大。

2.相反，链表则适用于插入删除频繁，表长估计不定的情形。

3.单链表中的逻辑位置连续，物理位置非连续；而顺序表都连续。

二.为什么要带附加表头？

因为不带附加表头在插入删除时要分两种情况：操作节点在表头和不在表头；而带了附加表头便可以对所有节点一视同仁。

![复制代码][copycode.gif]

1 template<class T>
      2 struct LinkNode{
       //链表节点 
      3     T data;
      4     LinkNode *link;
      5     LinkNode(const T& args,LinkNode<T> *ptr=NULL){
      6         data=args;
      7         link=ptr;
      8     }
      9 };
     10 
     11 template<class T>
     12 class List{
       //带附加头节点的单链表 
     13     protected:
     14         LinkNode<T> *first;//链表头指针 
     15     public:
     16         List(){
     17             first=new LinkNode<T>;
     18         }
     19         List(const T& x){
     20             first=new LinkNode<T>(x);
     21         }
     22         List(List<T>& L){
     23             T value;
     24             LinkNode<T> *L_head=L.getHead();
     25             LinkNode<T> *temp=first=new LinkNode<T>;
     26             while(L_head->link!=NULL){
     27                 value=L_head->link->data;
     28                 temp->link=new LinkNode<T>(value);
     29                 L_head=L_head->link;
     30                 temp=temp->link; 
     31             }
     32             temp->link=NULL;
     33         }
     34         ~List(){
     35             makeEmpty();
     36         }
     37         void makeEmpty(){
       //将链表置空 
     38             LinkNode<T> *temp;
     39             while(first->link!=NULL){
     40                 temp=first->link;
     41                 first->link=temp->link;
     42                 delete temp;
     43             }
     44         }
     45         int length()const{
     46             LinkNode<T> *temp=first->link;
     47             int count=0;
     48             while(temp!=NULL){
     49                 temp=temp->link;
     50                 count++;
     51             }
     52             return count;
     53         }
     54         LinkNode<T> *getHead()const{
       //返回附加头节点地址 
     55             return first;
     56         }
     57         LinkNode<T> *search(T x,int& i){
       //搜索数据x的地址和序列号 
     58             LinkNode<T> *current=first->link;
     59             int index=1;
     60             while(current!=NULL){
     61                 if(current->data==x)
     62                     break;
     63                 current=current->link;
     64                 index++;
     65             } 
     66             i=index;
     67             return current;
     68         }
     69         LinkNode<T> *locate(int i){
       //搜索第i个节点的地址 
     70             if(i<0)
     71                 return NULL;
     72             LinkNode<T> *current=first;
     73             int temp=0;
     74             while(current!=NULL&&temp<i){
     75                 current=current->link;
     76                 temp++;
     77             }
     78             return current;
     79         }
     80         bool getData(int i,T& x){
       //取出第i个元素的值 
     81             if(i<=0)
     82                 return false;
     83             LinkNode<T> *current=locate(i);
     84             if(current==NULL) return false;
     85             x=current->data;
     86             return true; 
     87         }
     88         void setData(int i,T& x){
       //修改第i个元素的值 
     89             if(i<=0)
     90                 return;
     91             LinkNode<T> *current=locate(i);
     92             if(current==NULL) return;
     93             current->data=x;
     94         }
     95         bool insert(int i,T& x){
       //在第i个元素后插入x 
     96             LinkNode<T> *current=locate(i);
     97             if(current==NULL) return false;
     98             LinkNode<T> *newNode=new LinkNode<T>(x);
     99             newNode->link=current->link;
    100             current->link=newNode;
    101             return true; 
    102         }
    103         bool remove(int i,T& x){
       //删除第i个元素的值 
    104             LinkNode<T> *current=locate(i-1);
    105             if(current==NULL||current->link==NULL) return false;
    106             LinkNode<T> *del=current->link;
    107             current->link=del->link;
    108             x=del->data;
    109             delete del;
    110             return true;
    111         }
    112         bool isEmpty()const{
    113             return (first->link==NULL)?true:false;
    114         }
    115         void inputFront(){
       //向前插入链表法 
    116             makeEmpty();
    117             LinkNode<T> *newNode;
    118             T value; 
    119             cin>>value;
    120             while(value!=-1){
    121                 newNode=new LinkNode<T>(value);
    122                 newNode->link=first->link;
    123                 first->link=newNode;
    124                 cin>>value;
    125             } 
    126         }
    127         void inputRear(){
       //向后插入链表法 
    128             makeEmpty();
    129             LinkNode<T> *newNode,*last=first;
    130             T value;
    131             cin>>value;
    132             while(value!=-1){
    133                 newNode=new LinkNode<T>(value);
    134                 last->link=newNode;
    135                 last=newNode;
    136                 cin>>value;
    137             }
    138         }
    139         void output(){
       //输出整个链表 
    140             LinkNode<T> *current=first->link;
    141             while(current!=NULL){
    142                 cout<<current->data<<" ";
    143                 current=current->link;
    144             }
    145             cout<<endl;
    146         }
    147 };

![复制代码][copycode.gif]

测试代码如下：

![复制代码][copycode.gif]

1 void menu(){
     2     cout<<"1.向前插入建表（-1结束）"<<endl;
     3     cout<<"2.向后插入建表（-1结束）"<<endl;
     4     cout<<"3.输出链表"<<endl;
     5     cout<<"4.搜索元素x所在节点的序号"<<endl;
     6     cout<<"5.取出第i个元素的值"<<endl;
     7     cout<<"6.用x的值修改第i个元素的值"<<endl;
     8     cout<<"7.删除第i个元素"<<endl;
     9     cout<<"8.在第i个元素后面插入x"<<endl;
    10     cout<<"9.退出"<<endl;
    11 } 
    12 
    13 template<class T>
    14 void function(int num,List<T> *list){
    15     switch(num){
    16         int x,i;
    17         case 1:
    18             list->inputFront();
    19             break;
    20         case 2:
    21             list->inputRear();
    22             break;
    23         case 3:
    24             list->output();
    25             break;
    26         case 4:
    27             cin>>x;
    28             list->search(x,i);
    29             cout<<i<<endl;
    30             break;
    31         case 5:
    32             cin>>i;
    33             list->getData(i,x);
    34             cout<<x<<endl;
    35             break;
    36         case 6:
    37             cin>>x>>i;
    38             list->setData(i,x);
    39             break;
    40         case 7:
    41             cin>>i;
    42             list->remove(i,x);
    43             break;
    44         case 8:
    45             cin>>i>>x;
    46             list->insert(i,x);
    47             break;
    48         default:
    49             exit(1);
    50     }
    51 }
    52 int main(int argc, char** argv) {
    53     int num;
    54     List<int> *list=new List<int>(-1);
    55     while(true){
    56         menu();
    57         cin>>num;
    58         function(num,list);
    59     }
    60     return 0; 
    61 }

![复制代码][copycode.gif]

其次是循环链表：

代码我就不放了，就讲讲要修改的地方：

1.构造函数。first=new LinkNode<T>;后面接上:first->link=first;目的是让自身首尾相连。如图：

![1076283-20170115162327072-325780619.png][]

2.在判断循环指针是否到达表尾的条件要从NULL换成first。

小结：

循环链表的目的是只要知道表中任一一个节点的地址，就能遍历表中其他任一节点。

最后是双向链表：

修改：

1.节点的构造函数。需要增加一个前驱指针。

2.搜索、插入删除算法。首先是方向，确定方向后算法和单链表差不多，区别在于通过前驱指针还是后续指针访问节点。其次是插入删除，讲起来比较啰嗦，直接看图：

![1076283-20170115170248510-866688920.jpg][]

这是插入（中间是插入元素），虚线是原来的情况，实线是插入后的情况，可见一共涉及到4个指针。

![1076283-20170115170528338-707044712.jpg][]

这是删除（中间是删除元素）。看上去也是涉及4个指针，实际只动了1和4。

小结：

双向链表的目的是为了解决在链表中不同方向（前/后）访问元素的问题。

[copycode.gif]: /images/20220526/0a6d3849f9a14f2d8ee69d46c8210c45.png
[1076283-20170115162327072-325780619.png]: /images/20220526/bcc4b800d6a249f682ba4fc80256a11c.png
[1076283-20170115170248510-866688920.jpg]: /images/20220526/4783909c8fba48b1a72a072763128e29.png
[1076283-20170115170528338-707044712.jpg]: /images/20220526/174638281e074ed59478a75892ef41e3.png