C++中单链表的实现

• 单链表
• 示例代码
• • 开发环境
  • 运行结果

链表内存空间不一定连续，其扩展性较好。多余的不多说了。该文主要记录单链表的实现，该单链表含有一个非空的头节点。链表的操作实际上是对其指针域与数据域的操作。

直接上代码：
LinkList.h

#pragma once

typedef struct LINKLIST {
	void * data;
	struct LINKLIST *pNext;

}LinkList;

typedef void(*PrintLinkList)(void *);

//无头的链表
class LinkNode
{
public:
	LinkNode();
	~LinkNode();

	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

// LinkList.cpp
//
#include "LinkList.h"
#include 
using namespace std;

LinkNode::LinkNode()
{
	m_pHead = new LinkList;
	m_pHead->data = nullptr;
	m_pHead->pNext = nullptr;
	m_size = 0;
}

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

void LinkNode::insertLinkList(int pos, void * data)
{
	if (m_pHead == nullptr)
	{
		return;
	}

	if (data == nullptr)
	{
		return;
	}

	//插入位置矫正
	if (pos < 0 || pos > m_size )
	{
		pos = m_size;
	}

	LinkList * insertNode = new LinkList;
	insertNode->data = data;
	insertNode->pNext = nullptr;

	//找到前一个位置（pos从0开始）
	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 ;
	}
	//找到前一个位置（pos从0开始）
	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)
	{
		return nPos;
	}
	if (value == nullptr)
	{
		return nPos;
	}
	LinkList *pHead = m_pHead;
	for (int i = 0; i < m_size; ++i)
	{
		//有空的头节点
		pHead = pHead->pNext;
		if (pHead->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;
	pTemp = pTemp->pNext;
	while (pTemp != nullptr)
	{
		print(pTemp->data);
		pTemp = pTemp->pNext;
	}
	cout << endl;
}

mian.cpp

#include 
#include "LinkList.h"
using namespace std;

typedef struct PERSON {
	char name[64];
	int age;
	int score;
}Person;

void myPrint(void *data) 
{
	Person *p = (Person*)data;
	cout << "name : " << p->name << " age: " << p->age << " score: " << p->score << endl;
}

void test() 
{
	LinkNode *plinkList = new LinkNode;
	Person p1 = {"husdh",23,78};
	Person p2 = { "hudfs",23,98 };
	Person p3 = { "术后",23,78 };
	Person p4 = { "喀什",23,67 };
	plinkList->insertLinkList(0, &p1);
	plinkList->insertLinkList(1, &p2);
	plinkList->insertLinkList(2, &p3);
	plinkList->insertLinkList(3, &p4);

	plinkList->printLinkList(myPrint);
	cout <<"链表的节点数： "<< plinkList->getSizeLinkList() << endl;

	plinkList->removeByPosInLinkList(1);
	cout << "remove" << endl;
	plinkList->printLinkList(myPrint);
	cout << "删除后链表的节点数： " << plinkList->getSizeLinkList() << endl;

	cout << "p3位置： " << plinkList->findValueInLinkList(&p3) << endl;

	myPrint(plinkList->getFirstNodeLinkList()->data);

	delete plinkList;
	plinkList = nullptr;
}

int main()
{
	test();

	return 0;
}

以上是单链表实现及测试代码。

vs2017控制台输出程序。

以上仅记录，方便理解。