单链表，循环链表，双向链表（C++实现）

单链表：

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

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

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

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

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

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 };

测试代码如下：

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 }

其次是循环链表：

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

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

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

小结：

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

最后是双向链表：

修改：

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

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

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

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

小结：

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

原文链接: https://www.cnblogs.com/ytz1996/p/6287420.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍