本文例程下载链接：ListDemo

链表 vs 数组

链表和数组的最大区别在于链表不支持随机访问，不能像数组那样对任意一个（索引）位置的元素进行访问，而需要从头节点开始，一个一个往后访问直到查找到目标位置。

单链表

与顺序表相对，链表是一种链式存储方式。单链表是实现顺序表最简单的一种链表，根据是否包含虚拟头节点，分为含虚拟头节点和不含虚拟头节点两种方式。本文以含虚拟头节点为例，用C++实现单链表数据结构ADT。

节点：链表的组成元素，每个节点包含数据域data和指针域next。例程为了简化设计，data用int类型表示。

虚拟头节点：链表的第一个节点，为了维护链表操作方便，但不存放数据。

虚拟头节点(dummy head) VS 无虚拟头节点

含虚拟头节点的链表优势：所有的数据节点（除去头节点）都是对等的，对链表节点的API操作一般不影响头节点本身指针变化（除去头节点next域）。

缺点：需要额外考虑头节点影响，比如IsEmpty()判断条件, 和Length()是否对等(IsEmpty <=> length==0?)，头节点对用户是否可见，能否被用户直接remove等。

单链表结构设计

含虚拟头节点的单链表list如下图所示，包含一个虚拟头节点V0，而V1~Vn通过前驱节点next域进行链接，从而形成一个单向链式结构。

虚拟头节点V0，不包含数据；V1~Vn包含数据，Vn->next = NULL

名称	描述	代表自定义符号
虚拟头节点	不包含数据	Vh/head
尾节点	链表的最后一个节点，特征：next=NULL	Vn-1/tail
普通数据节点	包含具有实际意义数据的节点	V0~Vn-1
长度	包含实际意义数据节点数为n（不包括Vh）	length
空链表	虚拟头节点为空，即head=NULL	V0=NULL
位置	从V0开始（Vh后继节点）开始计数0，直到Vn-1(尾节点)的节点对应位置。范围[0,n-1]	position
插入节点	在指定位置处插入节点，除插入节点及前驱和后继，不改变链表其他节点关系	insert
删除节点	在指定位置处删除节点, 除插入节点及前驱和后继，不改变链表其他节点关系	remove

单链表 C++ 实现 - 含虚拟头节点

单链表ADT设计

1. 链表节点ADT Node.h

/**
 * 单链表节点类
 */
class Node
{
    int data;
    Node *next;

public:
    Node();
    Node(Node*, int);
};

2. 单链表ADT LinkedList.h

/**
 * 单链表类
 * @description 带虚拟头节点
 */
class LinkedList
{
private:
    Node *head;
    Node *tail;

public:
    LinkedList();
    virtual ~LinkedList();
    Status Init();          // 初始化链表
    Status Destroy();       // 销毁链表

    int Length();           // 求链表长度(有效节点)节点个数
    bool IsEmpty();         // 链表是否为空
    Status Insert(int pos, int value);  // 在指定位置生产节点, 并插入数据
    Status Remove(int pos);  // 删除指定位置节点
    int GetValue(int pos);   // 读取指定位置节点数据
    Node* GetAddress(int pos); // 获取知道位置节点的地址
    int SearchPosition(int value); // 搜索第一个出现的元素值的节点位置
    Status Update(int pos, int value); // 更新指定位置节点数据
    Status ClearList(); // 清除链表数据(不包含头节点)
    Status PrintList(); // 顺序打印链表节点数据
    Status Reverse();   // 反转链表
};

3. Node实现 Node.cpp

#include "Node.h"
#include <cstdlib>

Node::Node() {
    data = 0;
    next = NULL;
}

Node::Node(Node* newNext, int newValue)
{
    data = newValue;
    next = newNext;
}

Node::~Node()
{
    // TODO Auto-generated destructor stub
}

4. 链表实现LinkedList.cpp

#include "LinkedList.h"
#include <cstdlib>
#include <iostream>

using namespace std;

LinkedList::LinkedList() {
    head = NULL;
    tail = NULL;
}

LinkedList::~LinkedList() {
    Destroy();
}

/**
 * 初始化链表
 */
Status LinkedList::Init()
{
    // 创建虚拟头节点
    head = new Node(NULL, 0);

    if(head != NULL)
    {
        return OK;
    }

    return ERROR;
}

/**
 * 销毁链表
 * @description 与初始化操作相对, 删除所有链表节点, 包括头节点
 */
Status LinkedList::Destroy()
{
    if(head)
    {
        Node *curP = head;

        while(head)
        {
            curP = head->next;
            delete head;
            head = curP;
        }

        return OK;
    }
    else
    {
        cout <<"The list is NULL"<<endl;
                return ERROR;
    }
}

/**
 * 求链表长度(有效节点)节点个数
 * @description 从虚拟头节点的下一个节点开始计算有效节点数
 */
int LinkedList::Length()
{
    if(!head)
    {
        cout <<"The list is NULL"<<endl;
        exit(-1);
    }

    Node *curP = head->next;
    int n = 0;
    while(curP != NULL)
    {
        n ++;
        curP = curP->next;
    }

    return n;
}

/**
 * 判断链表是否为空
 * @description 判断依据: 虚拟头节点head == NULL
 * 注: 长度为0 不代表链表为空
 */
bool LinkedList::IsEmpty()
{
    return (head == NULL);
}

/**
 * 在指定位置生产节点, 并插入数据
 * @param pos [in] 待插入位置. 从头节点的后继开始为0计数，所需要经过的节点数。范围：0~n-1
 * @param value [in] 待插入节点数据域
 */
Status LinkedList::Insert(int pos, int value)
{
    if(IsEmpty())
    {
        cout <<"The list is NULL. Pls Create an List and init it first."<<endl;
        exit(-1);
    }

    // create a new Node
    Node *newNode = new Node(NULL, value);

    if(pos == 0)
    {
        newNode->next = head->next;
        head->next = newNode;
    }
    else if(pos >0 && pos <= Length())
    {
        // find the predecessor node to be inserted
        Node *p = GetAddress(pos-1);

        // insert the new Node to List
        if(p != NULL)
        {
            if(p->next != NULL)
            {// not tail
                newNode->next  = p->next;
            }
            p->next = newNode;
        }
    }
    else
    {
        cout<<"Error: Input param Pos is illegal(<0)"<<endl;
        return ERROR;

    }

    return OK;
}

/**
 * 删除指定位置节点
 * @param pos [in] 待插入位置. pos有效范围: [0, n), 0代表虚拟节点后面一个节点, 虚拟节点无法通过此API删除
 *
 */
Status LinkedList::Remove(int pos)
{
    Node *preNode = NULL;
    Node *curNode = NULL;
    Node *nextNode = NULL;

    if(pos < 0 || pos >= Length())
    {
        cout << "Remove node with error position"<<endl;
        exit (-1);
    }
    else if(pos == 0)
    {// find the prior node, namely , head node
        preNode = head;
    }
    else if(pos < this->Length())
    {
        // find the prior node
        preNode = GetAddress(pos - 1);
    }

    if(!preNode)
    {
        return ERROR;
    }

    curNode = preNode->next;
    if(curNode)
    {
        nextNode = curNode->next;
        preNode->next = nextNode;
        delete curNode;
    }

    return OK;
}

/**
 * 读取指定位置节点数据
 */
int LinkedList::GetValue(int pos)
{
    // find the  node
    Node *curP = GetAddress(pos);
    if(curP != NULL)
    {
        return curP->data;
    }
    else
    {
        return 0;
    }
}

/**
 * 获取位置节点的地址
 * @param pos [in] 从头节点的后继开始为0计数，所需要经过的节点数。范围：[0, n-1], n是链表长度(有效数据节点数)
 * @return 节点的地址
 */
Node* LinkedList::GetAddress(int pos)
{
    // valid list is null or not
    if(!head)
    {
        cout <<"The list is NULL"<<endl;
        exit(-1);
    }

    // valid intput param
    if(pos < 0 || pos >= Length())
    {
        cout <<"Insert position is out of the list's bounds"<<endl;
        exit(-1);
    }

    // 顺序查找位置pos的节点
    int i = 0;
    Node *curP = head->next;
    while(curP != NULL)
    {
        if(i == pos)
        {
            return curP;
        }

        i ++;

        curP = curP->next;
    }

    return NULL;
}

/**
 * 搜索第一个出现的元素值的节点位置
 * @param value 待查找值
 * @return 链表第一个节点的数据域=value的位置
 * - ERROR 错误
 * - >=0 位置序号
 */
int LinkedList::SearchPosition(int value)
{
    // valid list is null or not
    if(!head)
    {
        cout <<"The list is NULL"<<endl;
        exit(-1);
    }

    // sequential search
    Node *p = head->next;
    int i = 0;
    while(p != NULL)
    {
        i ++;
        if(p->data == value)
            return i;
        else
            p = p->next;
    }

    cout<< "Can't find the value in list"<<endl;
    return ERROR;
}

/**
 * 更新指定位置节点数据
 * @param pos [in] 待更新节点位置
 * @param value [in] 待更新节点要修改的目标值
 * @return 更新结果
 * - OK 正常更新
 * - ERROR 没有找到待更新节点, 可能由位置错误或者链表为空导致
 */
Status LinkedList::Update(int pos, int value)
{
    // find the node
    Node *curP = GetAddress(pos);
    if(curP != NULL)
    {
        curP->data = value;
        return OK;
    }

    return ERROR;
}

/**
 * 清除链表数据(不包含头节点)
 */
Status LinkedList::ClearList()
{
    // valid list is null or not
    if(!head)
    {
        cout <<"The list is NULL"<<endl;
        exit(-1);
    }

    Node *p = head->next;
    Node *tmp = NULL;

    while(p!=NULL)
    {
        tmp = p;
        p = p->next;
        delete tmp;
    }

    head->next = NULL;

    return OK;
}

/**
 * 顺序打印链表节点数据
 */
Status LinkedList::PrintList()
{
    // valid list is null or not
    if(IsEmpty())
    {
        cout <<"The list is NULL. Pls Create an List and init it first."<<endl;
        return ERROR;
    }

    cout <<"List:[ ";
    if(Length() == 0)
    {
        cout<<"NULL";
    }
    else
    {
        Node *p = head->next;

        while(p != NULL)
        {
            cout<<p->data<<" ";
            p = p->next;
        }
    }
    cout <<"] "<<endl;
    return OK;
}

/**
 * 反转链表, 除虚拟头节点
 */
Status LinkedList::ReverseList()
{
    // valid list is null or not
    if(IsEmpty())
    {
        cout <<"The list is NULL. Pls Create an List and init it first."<<endl;
        exit(-1);
    }

    if(Length() == 0)
    {
        cout <<"The list length = 0. Pls insert new Node."<<endl;
        exit(-1);
    }

    // reverse List
    Node *pre = head->next; // precursor Node
    Node *cur = pre->next;  // current Node
    Node *nxt = NULL;       // successor Node

    while(cur != NULL)
    {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }

    // set the tail Node
    head->next->next = NULL;

    // set the head Node's next field
    head->next = pre;

    return OK;
}

6. 测试结果

可以看到已经实现了链表基本的插入、打印、反转等功能。

单链表 C++ 实现 - 含虚拟头节点

原文链接: https://www.cnblogs.com/fortunely/p/9868471.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/403249

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

单链表 C++ 实现 – 含虚拟头节点

链表 vs 数组

单链表

虚拟头节点(dummy head) VS 无虚拟头节点

单链表结构设计

单链表ADT设计

相关推荐