C++实现单链表

本篇介绍如何用C++实现单链表

首先需要定义节点 Node.h

#ifndef NODE_H
#define NODE_H

class Node
{
public:
	int data;
	Node *next;

public:
	void printNode();
};

#endif

Node.cpp

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

void Node::printNode()
{
	cout next;
		delete currentNode;
		currentNode = temp;
	}
	m_pList->next = NULL;
}

//销毁链表
List::~List()
{
	ClearList();
	delete m_pList;
	m_pList = NULL;
}

//从头结点插入,插入到头结点后面
bool List::ListInsertHead(Node *pNode)
{
	Node *temp = m_pList->next;
	Node *newNode = new Node;
	if(newNode == NULL)
	{
		return false;
	}
	newNode->data = pNode->data;
	m_pList->next = newNode;
	newNode->next = temp;
	m_iLength++;

	return true;
}

//从尾结点插入
bool List::ListInsertTail(Node *pNode)
{
	Node *currentNode = m_pList;
	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;

	}
	Node *newNode = new Node;
	if(newNode == NULL)
	{
		return false;
	}
	newNode->data = pNode->data;
	newNode->next = NULL;
	currentNode->next = newNode;
	m_iLength++;
	return true;
}

//从指定位置插入
bool List::ListInsert(int i, Node *pNode)
{
	if(i  m_iLength)
	{
		return false;
	}
	Node *currentNode = m_pList;
	for(int k = 0; k next;
	}
	Node *newNode = new Node;
	if(newNode == NULL)
	{
		return false;
	}
	newNode->data = pNode->data;
	newNode->next = currentNode->next;
	currentNode->next = newNode;
	m_iLength++;
	return true;
}

//删除指定位置
bool List::ListDelete(int i, Node *pNode)
{
	if(i= m_iLength)
	{
		return false;
	}
	Node *currentNode = m_pList;
	Node *currentNodeBefore = NULL;
	for(int k = 0; k next;
	}

	currentNodeBefore->next = currentNode->next;
	pNode->data = currentNode->data;
	delete currentNode;
	currentNode = NULL;
	m_iLength--;
	return true;
}

//获取指定位置的节点
bool List::GetElem(int i, Node *pNode)
{
	if(i= m_iLength)
	{
		return false;
	}

	Node *currentNode = m_pList;
	Node *currentNodeBefore = NULL;
	for(int k = 0; k next;
	}
	pNode->data = currentNode->data;
	return true;
}

//判断节点是否在链表中
int List::LocateElem(Node *pNode)
{
	Node *currentNode = m_pList;
	int count = 0;
	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;
		if(currentNode->data == pNode->data)
		{
			return count;
		}
		count++;
	}
	return -1;
}

//查找当前节点的前节点
bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
	Node *currentNode = m_pList;
	Node *tempNode = NULL;
	while(currentNode->next != NULL)
	{
		tempNode = currentNode;
		currentNode = currentNode->next;
		if(currentNode->data == pCurrentNode->data)
		{
			if(tempNode == m_pList)
			{
				return false;
			}
			pPreNode->data = tempNode->data;
			return true;
		}
	}
	return false;
}

//查找当前节点的下一个节点
bool List::NextElem(Node *pCurrentNode, Node *pNextNode)
{
	Node *currentNode = m_pList;

	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;
		if(currentNode->data == pCurrentNode->data)
		{
			if(currentNode->next == NULL)
			{
				return false;
			}
			pNextNode->data = currentNode->next->data;
			return true;
		}
	}
	return false;
}

//链表遍历
void List::ListTraverse()
{
	Node *currentNode = m_pList;
	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;
		currentNode->printNode();
	}
}

main函数测试

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

int main(void)
{
	Node node1;
	node1.data = 100;

	Node node2;
	node2.data = 200;
	Node node3;
	node3.data = 300;
	Node node4;
	node4.data = 400;

	Node node5;
	node5.data = 500;

	Node temp;


	List *pList = new List();

	/*pList->ListInsertHead(&node1);
	pList->ListInsertHead(&node2);
	pList->ListInsertHead(&node3);
	pList->ListInsertHead(&node4);*/

	pList->ListInsertTail(&node1);
	pList->ListInsertTail(&node2);
	pList->ListInsertTail(&node3);
	pList->ListInsertTail(&node4);

	pList->ListInsert(1, &node5);

	//pList->ListDelete(1, &temp);

	pList->NextElem(&node5, &temp);

	pList->ListTraverse();

	cout