数据结构初阶–单链表（讲解+类模板实现）

单链表

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

值得注意的是：

1.链表的在逻辑是连续的，物理上不一定是连续的；
2.现实中节点是从堆上申请的。

链表的实现

链表的单个结点的定义

就像这个图一样，一个空间用了存放数据（数据域），另一个空间用了存放下一个节点的地址（指针域）。

template <class DateType> struct LinkNode {     //数据域     DateType data;     //指针域     LinkNode<DateType>* next;     //注意两个事项：1.如果程序员提供了有参构造，那么编译器就不会提供默认的构造函数，但是会提供默认的拷贝构造     //2.注意事项2：如果程序员提供了拷贝构造，那么编译器不会提供默认的构造函数和拷贝构造     LinkNode(LinkNode<DateType> *ptr = NULL):next(ptr) {  }     //struct的构造函数，默认参数构造, //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面     LinkNode(const DateType& item, LinkNode<DateType>* ptr = NULL)     {         next = ptr;         data = item;     } }; 

链表的小框架

template <class DateType> class LinkList { public:  private: 	//头节点     LinkNode<DateType>* head; }; 

链表的接口

LinkList(); //构造函数,初始化为空链表 LinkList(const DateType &item);//有参构造，初始化头节点 LinkList(const LinkList<DateType>& list);//拷贝构造,拷贝单链表 CreateLink(int n);//创建单链表 ~LinkList();//析构函数,单链表的删除 void PushBack(const DateType& data);//尾插 void PopBack();//尾删 void PushFront(const DateType &data)；//头插 void PopFront();//头删 int Length()const;//求单链表的长度 bool GetElem(int pos, DateType& data);//获得pos位置的元素 LinkNode<DateType>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL bool Insert(int pos, const DateType &data);//在序号pos位置插入元素值为data的结点 bool Delete(int pos, DateType& data);//删除pos位置的结点，并且返回结点 LinkNode<DateType>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL void Clear();//清空链表 void PrintList()const;//输出单链表所有结点的元素值 void Exchangedata(int pos1, int pos2);//进行两结点元素值的交换 

构造和析构

1.无参构造函数：没什么好说的，用new从堆分配一个结点的空间给我们都头结点指针，注意检查堆是否满是一个很好的习惯

2.含参构造函数：初始化头节点指向第一个结点

3.析构函数（单链表的删除）：单链表的删除很简单用两个指针，从头结点开始，一前一后依次释放申请的内存即可

4.拷贝构造：操作都很简单，依次分配内存拷贝链接即可，类似于链表的构建。区别在于拷贝构造还没有LinkList对象，需要创建，而赋值已经有了LinkList对象，需要将其链表删除再重新构造

    //构造函数,初始化为空链表     LinkList()     {         head = new LinkNode<DateType>;         if (head == NULL)         {             cout << "内存分配失败" << endl;             exit(-1);         }     }     //有参构造，初始化头节点     LinkList(const DateType &item)     {         //LinkNode会调用构造函数，初始化结点内的内容         head = new LinkNode<DateType>();         LinkNode<DateType> *p = new LinkNode<DateType>(item);         head->next = p;         if (head == NULL)         {             cout << "内存分配失败" << endl;             exit(-1);         }     }     //拷贝构造,拷贝单链表     LinkList(const LinkList<DateType>& list)     {         LinkNode<DateType>* p = list.head->next;         if (p == NULL)         {             cout << "内存分配失败" << endl;             exit(-1);         }         head = new LinkNode<DateType>;         LinkNode<DateType>* h = head;         while (p != NULL)         {             LinkNode<DateType>* t = new LinkNode<DateType>;             h->next = t;             t->data = p->data;             p = p->next;             h = h->next;         }     }     //析构函数,单链表的删除     ~LinkList()     {         //申请一个指针指向头节点         LinkNode<DateType>* cur = head;         LinkNode<DateType>* next;         while (cur)         {             next = cur->next;             delete cur;             cur = next;         }      } 

尾插

首先，我们先来实现一个尾插的接口，尾插就是在链表的尾部插入一个节点。
在进行尾插的时候我们要考虑的几点：

1. 此时链表是否为空，如果为空我们应该怎么做，不为空又应该怎么做，这两种情况我们要分开讨论；
2. 如何申请节点，是在堆上还是栈上？

为了更好的理解尾插，我们先看一个动图展示：

void PushBack(const DateType& data)    {       LinkNode<DateType>* p = new LinkNode<DateType>(data);       if (head->next == NULL)       {           head->next = p;       }       else       {           LinkNode<DateType>* cur = head;           while (cur->next != NULL)           {               cur = cur->next;           }           cur->next = p;       }    } 

创建单链表

首先定义一个指向Head的指针q；
然后不断重复以下三个步骤完成单链表的构造：
①用new申请一个LinkNode的空间返回指针p，并输入数据元素；
②q->next=p，将q指针对应结点的后继修改为p；
③q=q->next,将指针指向其直接后继，这样一个结点就被链接进了链表之中

//创建单链表     void CreateLink(int n)     {         LinkNode<DateType>* q = head;         int* nodetemp = new int[n];         for (size_t i = 0; i < n; i++)         {             cout << "Enter the element:  " << endl;             cin >> nodetemp[i];         }         //尾插法         for (size_t i = 0; i < n; i++)         {             LinkNode<DateType>* p = new LinkNode<DateType>;             p->data = nodetemp[i];             p->next = q->next;             q->next = p;             q = q->next;         }         delete[] nodetemp;     } 

尾删

尾删无非就是在链表的尾部删除一个节点，听起来很简单，但是有很多细节是我们要注意的，我们要分三种情况来进行讨论：

1. 没有节点
2. 只有一个节点
3. 两个及两个以上的节点

先看动图演示：

//尾删 void PopBack() {     //分三种情况     //1.没有结点     if (head->next == NULL)     {         return;     }      //2.只有一个结点     else if (head->next->next == NULL) {         delete head->next;         head->next= NULL;      }      //3.两个以及两个以上的结点      else      {          LinkNode<DateType>* prev = NULL;          LinkNode<DateType>* cur = head;          while (cur->next != NULL)          {              prev = cur;              cur = cur->next;          }          delete cur;          cur = NULL;          prev->next = NULL;      } } 

头插

先看动图演示：

//头插 void PushFront(const DateType &data) {     LinkNode<DateType>* p = new LinkNode<DateType>(data);     p->next = head->next;     head->next = p; } 

头删

头删就要分情况讨论：

1. 链表为空
2. 链表不为空

先看动图演示：

//头删 void PopFront() {      //分两种情况      if (head->next == NULL)      {          return;      }      else      {          LinkNode<DateType>* p = head->next;          head->next = p->next;          delete p;          p = NULL;     } } 

定位位置

封装一个函数，返回第pos位置的地址，在下面用得到

//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL     LinkNode<DateType>* Locate(int pos)     {         int i = 0;         LinkNode<DateType>* p = head;         if (pos < 0)             return NULL;         while (NULL != p && i < pos)         {             p = p->next;             i++;         }         return p;     } 

单链表任意位置插入

//在序号index位置插入元素值为data的结点     bool Insert(int pos, const DateType &data)     {         LinkNode<DateType>* p = Locate(pos);         if (p == NULL)         {             return false;         }         LinkNode<DateType>* node = new LinkNode<DateType>(data);         if (NULL == node)         {             cerr << "分配内存失败!" << endl;             exit(-1);         }         node->next = p->next;         p->next = node;         return true;     } 

单链表的任意位置删除

先看动图演示：

//删除pos位置的结点，并且返回结点     bool Delete(int pos, DateType& data)     {         LinkNode<DateType>* p = Locate(pos-1);         if (NULL == p || NULL == p->next)             return false;         LinkNode<DateType>* del = p->next;         p->next = del->next;         data = del->data;         delete del;         return true;      } 

打印链表

//输出单链表所有结点的元素值     void PrintList()const     {         int count = 0;         LinkNode<DateType>* p = head->next;         while (p)         {             cout << p->data<<"  ";             p = p->next;             //打印十个元素换行             if (++count % 10 == 0)             {                 cout << endl;             }         }     } 

清空链表

//清空链表     void Clear()     {         //所有结点的next清空，最后头节点head清空         LinkNode<DateType>* p = NULL;         while (head->next != NULL)         {             p = head->next;             head->next = p->next;             delete p;         }     } 

单链表的长度

    //求单链表的长度     int Length()const     {         int count = 0;         LinkNode<DateType>* p = head;         while (p->next != NULL)         {             p = p->next;             ++count;         }         return count;     } 

两结点元素值的互换

    //进行两结点元素值的交换     void Exchangedata(int pos1, int pos2)     {         LinkNode<DateType>* p1 = Locate(pos1);         LinkNode<DateType>* p2 = Locate(pos2);         DateType tmp = p1->data;         p1->data = p2->data;         p2->data = tmp;     } 

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 template <class DateType> struct LinkNode {     //数据域     DateType data;     //指针域     LinkNode<DateType>* next;     //注意两个事项：1.如果程序员提供了有参构造，那么编译器就不会提供默认的构造函数，但是会提供默认的拷贝构造     //2.注意事项2：如果程序员提供了拷贝构造，那么编译器不会提供默认的构造函数和拷贝构造     LinkNode(LinkNode<DateType> *ptr = NULL):next(ptr) {  }     //struct的构造函数，默认参数构造, //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面     LinkNode(const DateType& item, LinkNode<DateType>* ptr = NULL)     {         next = ptr;         data = item;     } }; template <class DateType> class LinkList { public:     //构造函数,初始化为空链表     LinkList()     {         head = new LinkNode<DateType>;         if (head == NULL)         {             cout << "内存分配失败" << endl;             exit(-1);         }     }     //有参构造，初始化头节点     LinkList(const DateType &item)     {         //LinkNode会调用构造函数，初始化结点内的内容         head = new LinkNode<DateType>();         LinkNode<DateType> *p = new LinkNode<DateType>(item);         head->next = p;         if (head == NULL)         {             cout << "内存分配失败" << endl;             exit(-1);         }     }     //拷贝构造,拷贝单链表     LinkList(const LinkList<DateType>& list)     {         LinkNode<DateType>* p = list.head->next;         if (p == NULL)         {             cout << "内存分配失败" << endl;             exit(-1);         }         head = new LinkNode<DateType>;         LinkNode<DateType>* h = head;         while (p != NULL)         {             LinkNode<DateType>* t = new LinkNode<DateType>;             h->next = t;             t->data = p->data;             p = p->next;             h = h->next;         }     }     //创建单链表     void CreateLink(int n)     {         LinkNode<DateType>* q = head;         int* nodetemp = new int[n];         for (size_t i = 0; i < n; i++)         {             cout << "Enter the element:  " << endl;             cin >> nodetemp[i];         }         //尾插法         for (size_t i = 0; i < n; i++)         {             LinkNode<DateType>* p = new LinkNode<DateType>;             p->data = nodetemp[i];             p->next = q->next;             q->next = p;             q = q->next;         }         delete[] nodetemp;     }     //析构函数,单链表的删除     ~LinkList()     {         //申请一个指针指向头节点         LinkNode<DateType>* cur = head;         LinkNode<DateType>* next;         while (cur)         {             next = cur->next;             delete cur;             cur = next;         }      }     //尾插    void PushBack(const DateType& data)     {        LinkNode<DateType>* p = new LinkNode<DateType>(data);        if (head->next == NULL)        {            head->next = p;        }        else        {            LinkNode<DateType>* cur = head;            while (cur->next != NULL)            {                cur = cur->next;            }            cur->next = p;        }     }    //尾删    void PopBack()    {        //分三种情况        //1.没有结点        if (head->next == NULL)        {            return;        }        //2.只有一个结点        else if (head->next->next == NULL) {            delete head->next;            head->next= NULL;        }        //3.两个以及两个以上的结点        else        {            LinkNode<DateType>* prev = NULL;            LinkNode<DateType>* cur = head;            while (cur->next != NULL)            {                prev = cur;                cur = cur->next;            }            delete cur;            cur = NULL;            prev->next = NULL;        }    }     //头插    void PushFront(const DateType &data)    {        LinkNode<DateType>* p = new LinkNode<DateType>(data);        p->next = head->next;        head->next = p;    }     //头删    void PopFront()    {        //分两种情况        if (head->next == NULL)        {            return;        }        else        {            LinkNode<DateType>* p = head->next;            head->next = p->next;            delete p;            p = NULL;        }    }     //求单链表的长度     int Length()const     {         int count = 0;         LinkNode<DateType>* p = head;         while (p->next != NULL)         {             p = p->next;             ++count;         }         return count;     }     //得到序号为index的结点元素值     bool GetElem(int pos, DateType& data)     {         LinkNode<DateType>* p = Locate(pos);         if (p == NULL)         {             return false;         }         data = p->data;         return true;     }     //返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL     LinkNode<DateType>* Locate(int pos)     {         int i = 0;         LinkNode<DateType>* p = head;         if (pos < 0)             return NULL;         while (NULL != p && i < pos)         {             p = p->next;             i++;         }         return p;     }     //在序号index位置插入元素值为data的结点     bool Insert(int pos, const DateType &data)     {         LinkNode<DateType>* p = Locate(pos);         if (p == NULL)         {             return false;         }         LinkNode<DateType>* node = new LinkNode<DateType>(data);         if (NULL == node)         {             cerr << "分配内存失败!" << endl;             exit(-1);         }         node->next = p->next;         p->next = node;         return true;     }     //删除pos位置的结点，并且返回结点     bool Delete(int pos, DateType& data)     {         LinkNode<DateType>* p = Locate(pos-1);         if (NULL == p || NULL == p->next)             return false;         LinkNode<DateType>* del = p->next;         p->next = del->next;         data = del->data;         delete del;         return true;      }     //清空链表     void Clear()     {         //所有结点的next清空，最后头节点head清空         LinkNode<DateType>* p = NULL;         while (head->next != NULL)         {             p = head->next;             head->next = p->next;             delete p;         }     }     //输出单链表所有结点的元素值     void PrintList()const     {         int count = 0;         LinkNode<DateType>* p = head->next;         while (p)         {             cout << p->data<<"  ";             p = p->next;             //打印十个元素换行             if (++count % 10 == 0)             {                 cout << endl;             }         }     }     //进行两结点元素值的交换     void Exchangedata(int pos1, int pos2)     {         LinkNode<DateType>* p1 = Locate(pos1);         LinkNode<DateType>* p2 = Locate(pos2);         DateType tmp = p1->data;         p1->data = p2->data;         p2->data = tmp;     } private:     //头节点     LinkNode<DateType>* head; }; /* LinkList(); //构造函数,初始化为空链表 LinkList(const DateType &item);//有参构造，初始化头节点,      有问题 LinkList(const LinkList<DateType>& list);//拷贝构造,拷贝单链表 CreateLink(int n);//创建单链表 ~LinkList();//析构函数,单链表的删除 void PushBack(const DateType& data);//尾插 void PopBack();//尾删 void PushFront(const DateType &data)；//头插 void PopFront();//头删 int Length()const;//求单链表的长度 bool GetElem(int pos, DateType& data);//获得pos位置的元素 LinkNode<DateType>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL bool Insert(int pos, const DateType &data);//在序号pos位置插入元素值为data的结点 bool Delete(int pos, DateType& data);//删除pos位置的结点，并且返回结点 void Clear();//清空链表 void PrintList()const;//输出单链表所有结点的元素值 void Exchangedata(int pos1, int pos2);//进行两结点元素值的交换 */ int main() {      LinkList<int> list;     list.CreateLink(5);     list.PrintList();     cout << "-------------------" << endl;     list.PushBack(299);     list.PrintList();     cout << "-------------------" << endl;     list.PopBack();     list.PrintList();     cout << "-------------------" << endl;     list.PushFront(19);     list.PrintList();     cout << "-------------------" << endl;     list.PopFront();     cout << list.Length() << endl;     list.PrintList();     cout << "-------------------" << endl;     int b = 0;     list.GetElem(2,b);     cout << b << endl;     list.PrintList();     cout << "-------------------" << endl;     list.Insert(2, 99);     list.PrintList();     cout << "-------------------" << endl;     list.Exchangedata(1, 2);     list.PrintList();     cout << "-------------------" << endl;     list.Clear();     list.PrintList();     cout << "-------------------" << endl;     LinkList<int> list2(list);     list2.PrintList();     LinkList<int> list(90);     list.PrintList(); 	system("pause"); 	return EXIT_SUCCESS; }