C++链表实现

C++ 二进制

字数统计: 3k阅读时长: 12 min

 2021/06/15 

本文对C++链表记录一些学习笔记以及代码实现。

链表的特点

1、数据分散存储			
			
2、查询性能没有Vector好			
			
3、新增与删除的性能好于Vector

为何会出现链表

第一次学习线性表一定会马上接触到一种叫做顺序表（顺序存储结构），经过上一篇的分析顺序表的优缺点是很显然的，它虽然能够很快的访问读取元素，但是在解决如插入和删除等操作的时候，却需要移动大量的元素，效率较低，那么是否有一种方法可以改善或者解决这个问题呢？

首先我们需要考虑，为什么顺序表中的插入删除操作会涉及到元素的移动呢？

好家伙，问题就是围绕着顺序表的最大的特点出现的——顺序存储，相邻放置元素，也就是说每个元素都是根据编号一个一个挨着的，这就导致了插入或删除后，为了仍然呈顺序线性存储，被操作元素后面的元素的位置均需要发生一定的变化，你应该能想象得到，在拥挤的队伍中突然从中插入一个学生的场景，后面浩浩荡荡的人群，口吐芬芳的向后挪了一个空位，如果人群过大，重新排好队也需要一定的时间

好嘛，人与人之间别这么挤在一起，每个人与人之间都流出一点空隙来，留一定的位置出来，好了，这好像是个办法，但是负责一个一个与学生交流填表的老师可就不干了，这意味着我（找人）遍历的时候，需要多跑好多路，浪费好多时间，先不说这个，体院馆又不行了，你们这么个摆法，我这小馆可放不下，这也就意味着空间复杂度增加了很多

我们刚才所围绕的都是在 “排队” 的基本前提下的，但我们能想到的方法并不是很理想，那么我们索性就不排队了，是不是能有更好的解决方式呢？

一个有效的方法：

让同学们（元素）自己找位置随便站，不过你要知道相对于自己下一位同学的位置，这样既解决了空间上的问题，又能通过这种两两联系的方式访问（遍历）到整个队伍（数组），最重要的是，插入和离开同学，由于同学（元素）之间不存在了那种排队，相邻的特点，所以也不会说影响到过多的同学（元素）只需要和你插入位置的前后两位同学沟通好就行了，反正别人也不知道你们之间发生了什么事

好了思路是有了，我们来看一种最常见的链表——单链表

链表的类型

链表主要分为单链表、循环链表、双向链表

链表的结构

链表中的每个结点都包含一个或多个保存数据的成员。例如，存储在结点中的数据可以是库存记录；或者它可以是由客户的姓名、地址和电话号码等组成的客户信息记录。

除了数据之外，每个结点还包含一个后继指针指向链表中的下一个结点。

非空链表的第一个结点称为链表的头。要访问链表中的结点，需要有一个指向链表头的指针。从链表头开始，可以按照存储在每个结点中的后继指针访问链表中的其余结点。最后一个结点中的后继指针被设置为 nullptr 以指示链表的结束。

因为指向链表头的指针用于定位链表的头部，所以也可以认为它代表了链表头。同样的指针也可以用来定位整个链表，从头开始，后面跟着后续指针，所以也可以很自然地把它看作是代表了整个链表。

图 2 给出了一个由 3 个结点组成的链表，其中显示了指向头部的指针，链表的 3 个结点以及表示链表末尾的 nullptr 指针。

注意，图 2 中绘制的链表结点彼此非常接近，排列整齐。实际上，链表结点可能散布在内存的各个部分。

在链表中新增节点

这里先放一下自己对于新增节点的分析，这里主要是对函数实现的分析，主要有三种情况：

在链表头处添加

在链表尾部添加

在链表中添加

这里再放一下比较完整的新增节点的类型

创建头节点

手动new一个新的Node，将Node的next置为NULL即可。

1	head = new Node(0);head->next = NULL;

从头插入一个新的节点

手动new出一个新的节点p，使p的next的指向head->next所指向的地址,然后将head->next从新指向p即可。

1	Node * p = new Node(int); p->next = head->next; head->next = p;

删除指定节点

先遍历到指定节点的前一个节点,然后通过将前一个节点的next指针指向指定节点的下一个节点,达到悬空指定节点的效果,然后删除指定节点即可。

修改指定节点

遍历到指定节点的位置,将其data修改为要修改的值即可。

链表反转

定义三个临时节点指向头结点之后的第1个节点p,第2个节点q和第3个节点m。将p->next置为空,然后将q->next = p,然后将p向后移动一个节点,即p = q,最后将q向后移动一个节点,即q = m,最后把m向后移动一个节点,即m = m->next;依此类推直到m等于NULL,然后将q->next = p,最后将head->next指向q(即目前第一个节点疑,也就是原本最后的一个节点)。

　　通过三个节点达到从头开始逐个逆序的目的。

代码实现

// cplus链表.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <Windows.h>
#define SUCCESS           1 // 执行成功								
#define ERROR            -1 // 执行失败								
#define INDEX_IS_ERROR   -2 // 错误的索引号								
#define BUFFER_IS_EMPTY  -3 // 缓冲区已空								
								
								
template <class T_ELE>								
class LinkedList								
{								
public:								
	LinkedList();							
	~LinkedList();							
public:								
	BOOL  IsEmpty();	//判断链表是否为空 空返回1 非空返回0	
	void  Clear();    //清空链表	
	DWORD GetElement(IN DWORD dwIndex,OUT T_ELE& Element);    //根据索引获取元素	
	DWORD GetElementIndex(IN T_ELE& Element);    //根据元素获取链表中的索引	
	DWORD Insert(IN T_ELE Element);    //新增元素	
	DWORD Insert(IN DWORD dwIndex, IN T_ELE Element);    //根据索引新增元素	
	DWORD Delete(IN DWORD dwIndex);    //根据索引删除元素	
	DWORD GetSize();    //获取链表中元素的数量	
private:								
	typedef struct _NODE 							
	{							
		T_ELE  Data;						
		_NODE* pNext;						
	}NODE,*PNODE;							
	PNODE GetIndexCurrentNode(DWORD dwIndex);    //获取索引为dwIndex的指针	
	PNODE GetIndexPreviousNode(DWORD dwIndex);    //获取索引为dwIndex的前一个节点指针	
	PNODE GetIndexNextNode(DWORD dwIndex);    //获取索引为dwIndex的后一个节点指针	
private:								
	PNODE m_pList;    //链表头指针，指向第一个节点	
	DWORD m_dwLength; //元素的数量	
};								
								
//无参构造函数 初始化成员								
template<class T_ELE> LinkedList<T_ELE>::LinkedList()								
	:m_pList(NULL),m_dwLength(0)							
{								
								
}	
							
//析构函数 清空元素								
template<class T_ELE> LinkedList<T_ELE>::~LinkedList()								
{								
	Clear();
	printf("The destructor has already been executed!");
}	

//获取dwIndex前面节点的地址								
template<class T_ELE> 								
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexPreviousNode(DWORD dwIndex)								
{					
	PNODE ptempNODE = m_pList;

	for (int w = 0 ; w < dwIndex - 1; w++)
	{
		ptempNODE = ptempNODE->pNext;
	}
	
	return ptempNODE;

}								
//获取dwIndex节点的地址								
template<class T_ELE> 								
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexCurrentNode(DWORD dwIndex)								
{								
	PNODE ptempNODE = m_pList;

	for (int w = 0 ; w < dwIndex; w++)
	{
		ptempNODE = ptempNODE->pNext;
	}	
	
	return ptempNODE;
								
}								
//获取dwIndex后面节点的地址								
template<class T_ELE> 								
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexNextNode(DWORD dwIndex)								
{								
	PNODE ptempNODE = m_pList;

	for (int w = 0 ; w < dwIndex + 1; w++)
	{
		ptempNODE = ptempNODE->pNext;
	}						
	
	return ptempNODE;
}
							
//判断链表是否为空								
template<class T_ELE> BOOL LinkedList<T_ELE>::IsEmpty()								
{								
	if ( m_pList == NULL || m_dwLength == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
															
}								
//清空链表								
template<class T_ELE> void LinkedList<T_ELE>::Clear()								
{	
	PNODE pNode = m_pList;
	PNODE ptemp = pNode->pNext;

	// 1. 判断链表是否为空							
	
	if ( m_pList == NULL || m_dwLength == 0)
	
		return ;	

	// 2. 循环删除链表中的节点	
	
	for (int i = 0 ; i < m_dwLength; i++)
	{
		delete pNode;
		pNode = ptemp;
	}
	
	// 3. 删除最后一个节点并将链表长度置为0	
	
	m_dwLength = 0;
								
}
								
//根据索引获取元素								
template<class T_ELE> DWORD LinkedList<T_ELE>::GetElement(IN DWORD dwIndex,OUT T_ELE& Element)							
{	
	PNODE ptemp = m_pList;

	// 1. 判断索引是否有效							
		
	if (dwIndex < 0 || dwIndex >= m_dwLength)
	{
		return INDEX_IS_ERROR;
	}

	// 2. 取得索引指向的节点							
					
	for (int k = 0; k < dwIndex; k++)
	{
		ptemp = ptemp->pNext;
	}

	// 3. 将索引指向节点的值复制到OUT参数	
	
	memcpy(&Element, ptemp, sizeof(T_ELE));
	return SUCCESS;
								
}								
//根据元素内容获取索引								
template<class T_ELE> DWORD LinkedList<T_ELE>::GetElementIndex(IN T_ELE& Element)								
{
	PNODE ptemp = m_pList;

	// 1. 判断链表是否为空							
				
	if(IsEmpty())
	{
		return BUFFER_IS_EMPTY;
	}
	
	// 2. 循环遍历链表，找到与Element相同的元素	
	
	for (int t = 0; t < m_dwLength; t++)
	{
		if (!memcmp(ptemp, &Element, sizeof(T_ELE)))
		{
			printf("The value is %d,find successfully!",t);
			return t;
		}
		ptemp = ptemp->pNext;
	}
    retrun SUCCESS;
								
}								
//在链表尾部新增节点								
template<class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN T_ELE Element)								
{	
	PNODE pNewNode = new NODE;
	PNODE pTempNode = m_pList;
	memset(pNewNode, 0, sizeof(NODE));
	memcpy(pNewNode, &Element, sizeof(T_ELE));

	// 1. 判断链表是否为空							
				
	if(IsEmpty())
	{
		m_pList = pNewNode;
		m_dwLength++;
		return SUCCESS;
	}
	// 2. 如果链表中已经有元素	
		
	for ( int q = 0 ; q < m_dwLength - 1 ; q++)
	{
		pTempNode = pTempNode->pNext;
	}
	pTempNode->pNext = pNewNode;
	m_dwLength++;
	return SUCCESS;

}								
//将节点新增到指定索引的位置							
template<class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN DWORD dwIndex, IN T_ELE Element)								
{	
	PNODE pPreviousNode = NULL;
	PNODE pCurrentNode = NULL;
	PNODE pNewNode = new NODE;
	memset(pNewNode, 0, sizeof(NODE));
	memcpy(pNewNode, &Element, sizeof(T_ELE));
								
	//  1. 判断链表是否为空							 
				
	if(IsEmpty())
	{
		if ( !dwIndex)
		{
			return ERROR;
		}
		Insert(Element);
	}
	
	//  2. 判断索引值是否有效							
				
	if ( dwIndex < 0 || dwIndex > m_dwLength)
	{
		printf("It's seems not a valid index value,please try again!\n");
		return INDEX_IS_ERROR;
	}bu
	
	//  3. 如果索引为0	
	
	if ( dwIndex == 0 )
	{
		pNewNode->pNext = m_pList;
		m_pList = pNewNode;
		m_dwLength++;
		return SUCCESS;
	}
								
	//  4. 如果索引为链表尾	
	
	if ( dwIndex == m_dwLength)
	{
		pPreviousNode = GetIndexPreviousNode(dwIndex);	//获取dwIndex前面节点的地址	
		pPreviousNode->pNext = pNewNode;
		m_dwLength++;
		return SUCCESS;
	}
								
	//  5. 如果索引为链表中	
	if ( dwIndex > 0 && dwIndex < m_dwLength)
	{
		pPreviousNode = GetIndexPreviousNode(dwIndex);	//获取dwIndex前面节点的地址
		pCurrentNode = GetIndexCurrentNode(dwIndex);	//获取dwIndex节点的地址	
		pPreviousNode->pNext = pNewNode;
		pNewNode->pNext = pCurrentNode;
		m_dwLength++;
		return SUCCESS;
	}
}	

//根据索引删除节点
template<class T_ELE> DWORD LinkedList<T_ELE>::Delete(IN DWORD dwIndex)								
{
  	PNODE pdeltemp = m_pList;
	PNODE ptemp = pdeltemp;
								
	//  1. 判断链表是否为空	

	if ( IsEmpty() )
	{
		return BUFFER_IS_EMPTY;
	}
								
	//  2. 判断索引值是否有效	
	
	if ( dwIndex < 0 || dwIndex > m_dwLength )
	{
		printf("It's seems not a valid index value,please try again!\n");
		return INDEX_IS_ERROR;
	}
								
	//  3. 如果链表中只有头节点，且要删除头节点	
	
	if ( dwIndex == 0 && m_dwLength == 1)
	{
		delete m_pList;
	}
								
	//  4. 如果要删除头节点	
	//  5. 如果是其他情况
	
	if ( dwIndex >= 0 && dwIndex <=	m_dwLength)
	{
	    for (int m = 0; m < dwIndex - 1; m++)
        {
            ptemp = ptemp->pNext;
        }
        pdeltemp = ptemp->pNext;
        ptemp->pNext = pdeltemp->pNext;
        delete pdeltemp;
        return SUCCESS;
	}  
}

//获取链表中节点的数量								
template<class T_ELE> DWORD LinkedList<T_ELE>::GetSize()								
{								
	return m_dwLength;							
}																

void TestLink()
{

    LinkedList<int>* p = new LinkedList<int>;

    p->Insert(1);
    p->Insert(2);
    p->Insert(3);
    p->Insert(4);
	p->Insert(0,10);
  
	int x = 0;   
    p->GetElement(0,x);
    printf("The value is:%d\n", x);
    //p->Delete(2);
    p->GetElement(2,x);
    printf("The value is:%d\n", x);
}


int main(int argc, char* argv[])
{
	TestLink();

	return 0;
}