基于面向对象编程，C++实现单链表

链表：在内存空间中是非连续存储

组成：链表是由一个个节点组成的，每个节点都包含两个元素：数据和指针

节点头文件：

建立一个ListNode.h头文件

#pragma once
class ListNode
{
public:
	int value;
	ListNode* next;

	ListNode(int val);
	~ListNode();
};

节点源文件：

建立一个ListNode.cpp源文件

#include "ListNode.h"

ListNode::ListNode(int val)
{
	this->value = val;
	next = nullptr;
}

ListNode::~ListNode()
{
}

单链表：由一个个节点组成：

链表头文件：

建立一个ListNode.h头文件，将需要的API函数写入其中

#pragma once
#include "ListNode.h"
class LinkList
{
public:
	ListNode* head;
	ListNode* tail;
	int length;

	LinkList();//默认构造
	~LinkList();//默认析构
	LinkList(int val);//有参构造

	void GetLength();//获取长度
	void PrintList();//打印链表
	ListNode* get(int index);//获取元素
	void append(int val);//尾部添加元素
	void prepend(int val);//头部添加元素
	void insert(int index, int val);//插入元素
	ListNode* removeFirst();//移除头部元素
	ListNode* removeLast();//移除尾部元素
	ListNode* remove(int index);//移除元素
	void reverse();//链表翻转
	bool set(int index, int val);//修改元素
	int search(int val);//查找元素
};

链表源文件

建立LinkList.cpp源文件，实现具体的API

#include<iostream>
#include "LinkList.h"
using namespace std;

LinkList::LinkList()
{
}

LinkList::~LinkList()
{
}
                                                                                                                                                       
LinkList::LinkList(int val)
{
    ListNode* newNode = new ListNode(val);
    head = newNode;
    tail = newNode;
    length = 1;
}

void LinkList::GetLength()
{
    cout << "链表长度为：" << length << endl;
}

//打印链表
void LinkList::PrintList()
{
    ListNode* temp = head;
    while (temp != nullptr) {
        cout << temp->value << " ";
        temp = temp->next;
    }
    cout << endl;
}

//获取元素
ListNode* LinkList::get(int index)
{
    if (index < 0 || index >= length) {
        return nullptr;
    }
    ListNode* temp = head;
    for (int i = 0; i < index; i++) {
        temp = temp->next;
    }
    return temp;
}

//尾部增加元素
void LinkList::append(int val)
{
    ListNode* newNode = new ListNode(val);
    if (length == 0) {
        head = newNode;
        tail = newNode;
    }
    else {
        tail->next = newNode;
        tail = newNode;
    }
    length++;
}

//头部增加元素
void LinkList::prepend(int val)
{
    ListNode* newNode = new ListNode(val);
    if (length == 0) {
        head = newNode;
        tail = newNode;
    }
    else {
        newNode->next = head;
        head = newNode;
    }
    length++;
}

//插入元素
void LinkList::insert(int index, int val)
{
    if (index<0 || index>length) {
        cout << "error";
    }
    else if (index == 0) {
        prepend(val);
    }
    else if (index == length - 1) {
        append(val);
    }
    else {
        ListNode* pre = head;
        for (int i = 0; i < index - 1; i++) {
            pre = pre->next;
        }
        ListNode* aft = pre->next;
        ListNode* newNode = new ListNode(val);
        newNode->next = aft;
        pre->next = newNode;
        length++;
    }
}

//尾部移除元素
ListNode* LinkList::removeLast()
{
    if (length == 0) {
        return nullptr;
    }

    ListNode* temp = head;
    ListNode* prev = head;
    while (temp->next) {
        prev = temp;
        temp = temp->next;
    }
    tail = prev;
    tail->next = nullptr;
    length--;

    if (length == 0) {//链表只有一个节点，删除后为空
        head = nullptr;
        tail = nullptr;
    }
    return temp;
}

//头部移除元素
ListNode* LinkList::removeFirst()
{
    if (length == 0) {
        return nullptr;
    }

    ListNode* temp = head;
    head = head->next;
    temp->next = nullptr;
    length--;

    if (length == 0) {
        tail = nullptr;
    }
    return temp;
}

//移除元素
ListNode* LinkList::remove(int index)
{
    if (index<0 || index>length) {
        return nullptr;
    }
    if (index == 0) {
        return removeFirst();
    }
    if (index == length - 1) {
        return removeLast();
    }
    ListNode* prev = head;
    for (int i = 0; i < index-1; i++) {
        prev = prev->next;
    }
    ListNode* temp = prev->next;
    prev->next = temp->next;
    temp->next = nullptr;
    length--;
    return temp;
}

//反转
void LinkList::reverse()
{
    ListNode* temp = head;
    head = tail;
    tail = temp;
    ListNode* after = temp->next;
    ListNode* before = nullptr;
    for (int i = 0; i < length; i++) {
        after = temp->next;
        temp->next = before;
        before = temp;
        temp = after;
    }
}
//修改元素
bool LinkList::set(int index, int val)
{
    ListNode* temp = get(index);
    if (temp) {
        temp->value = val;
        return true;
    }
    return false;
}

//查找元素
int LinkList::search(int val)
{
    int index = 0;
    ListNode* temp = head;
    while (temp->value != val) {
        index++;
        temp = temp->next;
        if (temp == nullptr) {
            cout << "未找到！" << endl;
            return -1;
        }
    }
    return index;
}

测试文件：

建一个单链表.cpp文件，用一个例子进行测试

#include<iostream>
#include"LinkList.h"
#include"ListNode.h"
using namespace std;

void test() {
	LinkList* myList1 = new LinkList(1);
	myList1->append(3);
	myList1->append(5);
	myList1->append(7);
	myList1->append(9);
	myList1->PrintList();
	myList1->search(4);
}

int main() {
	test();
}

插入元素：

对于下面的单链表，可以进行头插，尾插，中间任意位置插入

1. 头部插入：

由图可以知道，在头部插入时，先将新节点的next指向头结点，然后再将头结点移动到新节点处：

//头部增加元素
void LinkList::prepend(int val)
{
    ListNode* newNode = new ListNode(val);//创建新节点
    if (length == 0) {//如果单链表为空，就将单链表的头结点和尾节点都指向新节点
        head = newNode;
        tail = newNode;
    }
    else {
        newNode->next = head;
        head = newNode;
    }
    length++;
}

2. 尾部插入：

在进行尾插时，先将尾节点的next指向新节点，然后尾节点移动到新节点上

//尾部增加元素
void LinkList::append(int val)
{
    ListNode* newNode = new ListNode(val);
    if (length == 0) {
        head = newNode;
        tail = newNode;
    }
    else {
        tail->next = newNode;
        tail = newNode;
    }
    length++;
}

3. 其他位置插入：

在任意位置插入节点时，有以下几种情况：
1.如果插入的位置不合法要求，返回false
2.如果index=0，头插法
3.如果index=length-1，尾插法
4.其他情况下，
（1）先创建一个临时节点pre令其指向头结点head，
（2）然后移动pre指向index处前的一个节点
（3）在创建一个节点aft指向index
（4）让新节点的next指向aft
（5）让pre节点的next指向新节点

//插入元素
void LinkList::insert(int index, int val)
{
    if (index<0 || index>length) {
        cout << "error";
    }
    else if (index == 0) {
        prepend(val);
    }
    else if (index == length - 1) {
        append(val);
    }
    else {
        ListNode* pre = head;
        for (int i = 0; i < index - 1; i++) {
            pre = pre->next;
        }
        ListNode* aft = pre->next;
        ListNode* newNode = new ListNode(val);
        newNode->next = aft;
        pre->next = newNode;
        length++;
    }
}

删除元素：

同样，删除节点也可以分为头删，尾删，任意位置删除

1. 头部节点删除

（1）创建一个新节点指向head
（2）让head向后移一个，即head指向head的next节点
（3）然让temp的next指向head

2. 尾部节点删除

（1）先创建两个节点：tmp和pre指向head
（2）依次向后移动temp和pre
（3）tail节点指向pre所指的节点
（4）tail的next指向nullptr

3. 任意位置删除

1.判断index是否合法，不合法返回false
2.如果index=0，则头结点删除法
3.如果index=length-1，则尾节点删除法
4.如果任意位置，则：
（1）创建一个节点prev指向头结点head
（2）移动pre节点至index的前一个节点
（3）创建一个节点temp指向prev的next节点即index指向的节点
（4）让prev的next节点指向temp的next节点
（5）temp的next指向空

修改元素：

（1）获取该节点
（2）如果该节点不为空，将新值赋给该节点的值

//修改元素
bool LinkList::set(int index, int val)
{
    ListNode* temp = get(index);
    if (temp) {
        temp->value = val;
        return true;
    }
    return false;
}

查找元素：

（1）创建一个临时节点temp，指向头结点head
（2）依次移动temp，并判断temp是否为空
（3）找到节点并返回相应的索引

//查找元素
int LinkList::search(int val)
{
    int index = 0;
    ListNode* temp = head;
    while (temp->value != val) {
        index++;
        temp = temp->next;
        if (temp == nullptr) {
            cout << "未找到！" << endl;
            return -1;
        }
    }
    //cout<<index;
    return index;
}

链表反转：

1.创建一个节点temp，指向头结点head
2.头结点和尾节点互换位置
3.创建两个节点：p1指向空，p2指向temp的下一个节点
4.在整个单链表上进行如下操作：
（1）p2指向temp的下一个节点
（2）然后temp的next指向p1
（3）p1移动至temp
（4）temp移动至p2

//链表反转
void LinkList::reverse()
{
    ListNode* temp = head;
    head = tail;
    tail = temp;
    ListNode* after = temp->next;
    ListNode* before = nullptr;
    for (int i = 0; i < length; i++) {
        after = temp->next;
        temp->next = before;
        before = temp;
        temp = after;
    }
}