单链表

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

值得注意的是：

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. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。