单链表的相关定义与实现（8.24加入链表反转）

顺序表的缺点及解决办法：

缺点：

• 插入和删除时需要移动大量元素，算法时间复杂度为O(n)。
• 顺序线性表长度变化较大时难以确定存储空间的容量。
• 造成存储空间的“碎片”。

解决思路：

• 所有元素不要考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道它下一个元素的位置在哪里，这样就可以依次查找了。同时也解决了“难以确定存储空间容量”的问题了。
• 思考：这么做是不是也有缺点？
  答：有缺点。如c++标准容器类forward_list用链表连接，我要查找里面第n个元素，那么就要从第一个元素开始遍历，时间复杂度为O(n)。

链表方案：

• 为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。
  把存储数据元素信息的域成为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
• n个结点链结成一个链表。即为线性表的链式存储结构。如果每个结点中只包含一个指针域，就称为单链表。
• 链表中第一个结点的存储位置称为头指针。存取从头指针开始进行。
• 最后一个指针为尾指针，next指针指向NULL。

项目代码实现思路：

• 现在设计一个具体的单链表实现。假设项目中，链表的数据域存储一个姓名，指针域存储下一个姓名。将数据域和指针域用一个struct封装起来。
• 要实现的功能为：
  1）获取单链表第i个元素的数据
  2）对单链表实现任意位置插入与删除操作
  3）实现整表创建与整表删除（C++更好实现，使用构造函数和析构函数即可）
  4）打印链表最终内容

1）获取单链表中第i个元素的数据

强调：这种做法需要让指针遍历，因此不是一个效率很高的做法。
具体算法思路：

• 声明一个指针p指向链表第一个结点，初始化j从1开始。
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
• 若到链表末尾p为空，则说明第i个结点不存在。
• 否则查找成功，返回结点p的数据。
  说明：第三条很重要，因为在面试中，一个程序的鲁棒性非常重要。它意味着你的程序是否健壮以及是否有抵御bug的能力。

2）在任意位置插入元素

强调：单链表的尾插非常方便，但是如果在任意位置插入，则需要遍历之前的所有元素直至找到当前位置。因此时间复杂度也较高，消耗资源大。
具体算法思路：

• 声明一个指针p指向链表头结点，初始化j从1开始。
• 当j<pos时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
• 若到链表末尾p为空，则说明第pos个结点不存在。（鲁棒性）
• 否则查找成功，在系统中生成一个空结点s。
• 将string对象st赋值给node->name。
• 插入标准语句node->next = p->next;,p->next=node。
• 长度length加一。
• 返回。
  （p是一个查找用的指针）

3）在任意位置删除元素

具体算法思路：

• 核心就是删除第pos个元素，将第pos-1个指针的next指针绕过第i个元素，指向第pos+1个结点。
• 首先声明指针p指向链表头指针，初始化j从1开始。
• 当j<i时遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1。
• 若到链表末尾p为空，则说明第i个结点不存在。
• 否则查找成功，将欲删除的结点p->next赋值给q。
• 单链表的删除标准语句p->next=q->next，p为q之前的结点。
• 长度length减一。
• 释放q结点，返回成功。

具体代码

1）Linklist.h

#include<string>
using std::string;
struct Node
{
    string name;
    Node * next;
};
class Linklist
{
private:
    Node * head;
    int length;
public:
    Linklist():head(NULL),length(0){};
    ~Linklist();
    Node * GetHead();
    Node * ReverseList(Node * head);
    void Insert(int pos,string st);
    void Delete(int pos);
    void GetLinkListElem(int i,string st);
    void Print();
};

2）Linklist.cpp

#include<iostream>
#include"Linklist.h"
using std::cout;
using std::endl;
Linklist::~Linklist()
{
    Node * temp = new Node;  
    for(int i=0;i<length;i++)  
    {  
        temp = head;  
        head = head->next;  
        delete temp; 
    }
}
Node * Linklist::GetHead()
{
    return this->head;
}
Node * Linklist::ReverseList(Node * head)
{
    Node * node = head;
    Node * prev = NULL;
    while(node != NULL)
    {
        Node * next1 = node->next;
        node->next = prev;
        prev = node;
        node = next1;
    }
    this->head = prev;
    return prev;
}
void Linklist::Insert(int pos,string st)
{
    int j = 1;
    Node * node = new Node;
    Node * p = head;
    if (pos == 1)
    {
        node->name = st;
        node->next = p;
        head = node;
        length++;
        return;
    }
    while(p && j < pos-1)//寻找p==pos-1的位置,在其后插入即为在pos处插入。
    {
        p=p->next;
        j++;
    }
    if(!p || j > pos)//考虑p超出链表范围（变成NULL），pos为0或小于0的情况
    {
        cout << "Cannot insert!" << endl;
        return;
    }
    node->name = st;
    node->next = p->next;
    p->next = node;
    length++;
}
void Linklist::Delete(int pos)
{
    int j = 1;
    Node * p = head;
    if (pos == 1)
    {
        head = head->next;
        length--;
        return;
    }
    while(p && j < pos-1)//寻找p==pos-1的位置，在p->next删除即为在pos删除。
    {
        p=p->next;
        j++;
    }
    if(!p || j > pos)//如果p超出范围或pos太小
    {
        cout << "Cannot delete!" << endl;
        return;
    }
    Node * temp = new Node;
    temp = p->next;
    p->next = temp->next;//把temp后面的结点和p->next链起来。
    delete temp;//释放temp，即p->next。
    length--;
}
void Linklist::Print()
{
    if(head == NULL)
    {
        cout << "Linklist has no elements." << endl;
        return;
    }
    Node * temp = head;
    while(temp != NULL)
    {
        cout << temp->name << "," << endl;
        temp = temp->next;
    }
    cout << endl;
}

3）具体测试main.cpp

#include"Linklist.h"
#include<iostream>
using std::cout;
using std::endl;
int main()
{
    Linklist L;
    L.Insert(1,"sword");
    L.Print();
    L.Insert(2,"edward");
    L.Print();
    L.Insert(3,"ed");
    L.Print();
    Node * head = L.GetHead();
    head = L.ReverseList(head);
    head = L.GetHead();
    L.Print();
    return 0;
}

4）输出结果

Paste_Image.png