单链表

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

值得注意的是：

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;
        DateType* nodetemp = new DateType[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;
}

本栏目推荐文章
• 类模板实现简单的数组
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据

数据结构 模板 结构 数据数据结构 队列 模板 结构 数据结构 双向 模板 结构 数据结构 队列 顺序 模板 数据结构 模板 结构 数据 高维 数据结构 模板 结构 数据结构 算法 模板 结构 数据结构 高阶 算法 模板 结构 线段 数组 模板 数据结构 大屏 模板 数据html5