C++单链表完整实现：节点定义、核心操作与类封装实例

单链表的底层结构与核心概念

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构。其数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由于链表由一系列结点（通常作为类或结构体类型实例）组成，这些结点可以在运行时动态生成，因此其扩展性较好，能够灵活地适应数据量的变化。

线性表的链式存储称为单链表。它使用一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息（数据域）外，还需要存放一个指向其后继结点的指针（指针域）。

结点类型的定义：

typedef struct LNode {  // 定义单链表节点类型
  ElemType data;       // 数据域
  struct LNode* next;  // 指针域
}LNode, *LinkList;

注意：在实际C++工程中，通常会在链表头部设置一个“头节点”（Head Node），其数据域可以不存储任何信息或用于存储链表长度等附加信息，指针域指向第一个真正的数据节点（首元节点）。引入头节点可以简化空表和首元节点的处理逻辑，使得无论链表是否为空，插入或删除操作的代码逻辑保持统一。

单链表的基本操作原语

以下操作均基于带有非空头节点的单向链表结构。假设链表指针为L。

第1步：初始化单链表

目的：构造一个空的单链表，创建头节点并将其指针域置空。

操作逻辑：通过new操作符生成一个新的节点作为头节点，使头指针L指向该节点，并将该节点的next成员初始化为NULL。

// 初始化单链表
void InitList(LinkList &L) 
{
  L = new LNode;         // 生成新节点作为头节点
  L->next = NULL;        // 头节点的指针域置空
}

第2步：按位取值（GetElem）

目的：获取单链表中第i个位置上元素的内容。

操作逻辑：由于链表不具备随机访问特性，必须从头节点出发，顺着next链逐个节点向下访问。利用计数器追踪当前访问的是第几个节点，直到找到第i个节点或到达链表尾部。

// 单链表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
  LinkList p = L->next;  // p指向首元节点（第一个实际存数据的节点）
  int j = 1;             // 计数器初值为1
  
  // 循环向后查找，直到p为空（越界）或找到第i个节点
  while (p && j < i) 
  {
    p = p->next;  // 移动到下一个节点
    ++j;          // 计数器加1
  }
  
  // 如果p为空说明链表太短，或者j>i表示下标越界
  if (!p || j > i) return false;   
  
  e = p->data;   // 取出第i个节点的数据域
  return true;
}

第3步：按值查找（LocateElem）

目的：在单链表中查找第一个数据值等于给定值e的节点。

操作逻辑：从首元节点开始遍历，逐一比较节点的数据域与目标值e。若找到匹配的节点，将该节点的指针通过引用返回；若遍历结束未找到，则返回false。

// 单链表的按值查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
  // 从首元结点开始查找
  p = L->next; 
  
  // 当指针不为空且数据不等于目标值时继续向后移动
  while (p && p->data != e)
  {
    p = p->next;
  }
  
  // 如果p不为空，说明找到了该节点
  if (p)
  {
    return true;
  }
  return false;
}

第4步：按位插入（ListInsert）

目的：在单链表的第i个位置插入新的数据元素e。

操作逻辑：关键步骤是调整指针顺序，防止断链。首先找到第i-1个位置的节点（即插入位置的前驱节点），记为p。然后创建一个新节点s，将s->next指向p->next，再将p->next指向s。

// 单链表的插入
bool ListInsert(LinkList &L, int i, ElemType e)
{
  LinkList p = L;
  LNode* s;
  int j = 0;
  
  // 遍历寻找第i-1个节点
  while (p && j < i - 1)
  {
    p = p->next;
    j++;
  }
  
  // 判断插入位置是否合法：
  // 1. p == NULL 说明找不到前驱节点（i大于表长+1）
  // 2. i < 1 说明下标非法
  if (!p || i < 1)
  {
    return false;
  }
  
  // 创建新节点s并赋值
  s = new LNode;
  s->data = e;
  
  // 执行插入操作：修改指针指向
  s->next = p->next;   // 新节点指向原后继节点
  p->next = s;         // 前驱节点指向新节点
  
  return true;
}

第5步：按位删除（ListDelete）

目的：删除单链表中第i个位置的节点，并返回被删节点的数据。

操作逻辑：同样先找到第i-1个节点（前驱节点p）。保存要被删除节点（p->next，记为q）的地址，修改p->next使其跳过q指向q的后继节点，然后释放q占用的内存。

// 单链表的删除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
  LinkList p = L;
  LNode* q;
  int j = 0;
  
  // 寻找第i-1个节点
  // 注意终止条件检查 p->next，因为我们要取走的是p后面的节点
  while (p->next && j < i - 1)
  {
    p = p->next;
    j++;
  }
  
  // 判断删除位置是否合法：
  // 1. ! (p->next) 说明没有第i个节点可删
  // 2. i < 1 索引非法
  if (!(p->next) || i < 1)
  {
    return false;
  }
  
  // q指向待删除的第i个节点
  q = p->next; 
  
  // 将第i-1个节点的指针直接连到第i+1个节点
  p->next = q->next;
  
  e = q->data;           // 保存被删结点的数据
  delete q;              // 释放被删结点的空间
  
  return true;
}

面向对象封装与完整工程示例

在实际开发中，单纯的过程式函数调用不够便捷。下面展示一种基于C++类的单链表实现方案。该方案使用了泛型指针void*来容纳任意数据类型，并通过回调函数PrintLinkList来处理数据的具体打印逻辑。

头文件定义 (LinkList.h)

定义了链表节点结构体、打印函数指针 typedef，以及封装了链表操作接口的LinkNode类。

#pragma once
#include <iostream>

// 链表节点定义
struct LINKLIST {
	void * data;
	LINKLIST *pNext;
};

// 定义打印回调函数类型
using PrintLinkList = void(*)(void *);

// 链表管理类（内部维护了一个带空数据头的链表）
class LinkNode
{
public:
	LinkNode();
	~LinkNode();
	
	// 在指定位置插入数据(pos从0开始计数)
	void insertLinkList(int pos, void * data);
	// 移除指定位置的数据
	void removeByPosInLinkList(int pos);
	// 获取链表有效数据长度
	int getSizeLinkList();
	// 查找特定数据指针的位置
	int findValueInLinkList(void* value);
	// 获取指向第一个真实数据节点的指针
	LINKLIST* getFirstNodeLinkList();
	// 打印所有数据
	void printLinkList(PrintLinkList print);
	
private:
	LINKLIST *m_pHead;  // 头节点
	int m_size;         // 记录节点数量
};

实现细节 (LinkList.cpp)

实现了类的构造函数（初始化）、析构函数（遍历释放内存，防止泄漏）以及核心操作方法。特别注意insertLinkList中对于超出范围位置的处理，这里将其修正为追加到末尾。

#include "LinkList.h"

LinkNode::LinkNode()
{
	// 创建头节点，数据域不存内容，pNext置空
	m_pHead = new LINKLIST;
	m_pHead->data = nullptr;
	m_pHead->pNext = nullptr;
	m_size = 0;
}

LinkNode::~LinkNode()
{
	if (m_pHead != nullptr)
	{
		LINKLIST *curr = m_pHead;
		while (curr != nullptr)
		{
			LINKLIST *pNext = curr->pNext;
			delete curr;
			curr = nullptr;
			curr = pNext;
		}
	}
}

void LinkNode::insertLinkList(int pos, void * data)
{
	if (m_pHead == nullptr || data == nullptr)
	{
		return;
	}
	
	// 插入位置矫正：如果pos无效或过大，默认追加到末尾
	if (pos < 0 || pos > m_size )
	{
		pos = m_size;
	}
	
	LINKLIST * insertNode = new LINKLIST;
	insertNode->data = data;
	insertNode->pNext = nullptr;
	
	// 定位到pos对应的前一个节点
	LINKLIST *pPre = m_pHead;
	for (int i = 0; i < pos; ++i)
	{
		pPre = pPre->pNext;
	}
	
	// 执行插入
	insertNode->pNext = pPre->pNext;
	pPre->pNext = insertNode;
	
	m_size++;
}

void LinkNode::removeByPosInLinkList(int pos)
{
	if (m_pHead == nullptr)
	{
		return;
	}
	if (pos < 0 || pos >= m_size)
	{
		return ;
	}
	
	LINKLIST *pPre = m_pHead;
	for (int i = 0; i < pos; ++i)
	{
		pPre = pPre->pNext;
	}
	
	LINKLIST *delNode = pPre->pNext;
	pPre->pNext = delNode->pNext;
	delete delNode;
	delNode = nullptr;
	m_size--;
}

int LinkNode::getSizeLinkList()
{
	return m_size;
}

int LinkNode::findValueInLinkList(void* value)
{
	int nPos = -1;
	if (m_pHead == nullptr || value == nullptr)
	{
		return nPos;
	}
	
	LINKLIST *pCurr = m_pHead;
	for (int i = 0; i < m_size; ++i)
	{
		pCurr = pCurr->pNext; // 跳过头节点
		if (pCurr->data == value)
		{
			nPos = i;
			break;
		}
	}
	return nPos;
}

LINKLIST * LinkNode::getFirstNodeLinkList()
{
	if (m_pHead == nullptr)
	{
		return nullptr;
	}
	return m_pHead->pNext;
}

void LinkNode::printLinkList(PrintLinkList print)
{
	if (m_pHead == nullptr)
	{
		return ;
	}
	
	LINKLIST *pTemp = m_pHead->pNext; // 指向第一个有效数据节点
	while (pTemp != nullptr)
	{
		print(pTemp->data);     // 调用外部传入的打印函数
		pTemp = pTemp->pNext;
	}
	std::cout << std::endl;
}

主程序测试 (main.cpp)

构建一个简单的测试场景：创建三个Person结构体对象，依次插入链表，打印结果，删除中间节点后再查看状态，最后清理内存。

#include <iostream>
#include "LinkList.h"

// 自定义人员结构体
struct PERSON {
	char name[64];
	int age;
	int score;
};

// 针对PERSON的打印回调函数
void myPrint(void *data) 
{
	PERSON *p = (PERSON*)data;
	std::cout << "name : " << p->name 
	<< " age: " << p->age 
	<< " score: " << p->score << std::endl;
}

void test() 
{
	// 1. 创建链表实例
	LinkNode *plinkList = new LinkNode;
	
	// 2. 准备测试数据（堆内存分配，以便验证删除后的效果）
	PERSON p1 = {"husdh", 23, 78};
	PERSON p2 = { "hudfs", 23, 98 };
	PERSON p3 = { "术后", 23, 78 };
	PERSON p4 = { "喀什", 23, 67 };
	
	// 3. 插入数据 (pos 0, 1, 2, 3)
	plinkList->insertLinkList(0, &p1);
	plinkList->insertLinkList(1, &p2);
	plinkList->insertLinkList(2, &p3);
	plinkList->insertLinkList(3, &p4);
	
	std::cout << "=== 初始列表 ===" << std::endl;
	plinkList->printLinkList(myPrint);
	std::cout << "链表的节点数： " << plinkList->getSizeLinkList() << std::endl;
	
	// 4. 删除位置为1的节点 (p2)
	std::cout << "=== 删除索引1后 ===" << std::endl;
	plinkList->removeByPosInLinkList(1);
	plinkList->printLinkList(myPrint);
	std::cout << "删除后链表的节点数： " << plinkList->getSizeLinkList() << std::endl;
	
	// 5. 查找剩余节点
	int pos = plinkList->findValueInLinkList(&p3);
	std::cout << "p3在当前链表中的位置： " << pos << std::endl;
	
	// 6. 输出首节点内容
	LINKLIST* first = plinkList->getFirstNodeLinkList();
	if(first) myPrint(first->data);
	
	// 7. 销毁对象（会自动触发析构函数释放所有节点内存）
	delete plinkList;
	plinkList = nullptr;
}

int main()
{
	test();
	return 0;
}

上述代码涵盖了从底层节点操作到高级类封装的全过程。通过观察析构函数中的循环遍历delete过程，可以看到良好的资源管理习惯能有效避免内存泄漏。以上就是C++单链表详细实现与封装的详细内容，更多关于C++链表进阶技术的资料请关注本站其它相关文章！