一、链表

链表：是一种常见的数据结构，所有的数据以节点的形式存储在一个线性结构中，但是，链表的节点并不是顺序存储的，而是通过节点的指针把所有节点连接起来；对链表的操作主要就是对节点的操作，对链表的插入和删除操作的时间复杂度是O(1),但是对链表的随机访问的时间复杂度是O(n)

节点：数据 域+ 指针域（数据域存放具体的数据、各节点之间通过指针域连接起来)

1、单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

本例使用C++类模版实现单向链表，主要提供以下接口：

1、创建链表 2、在链表的尾节点、及其他索引插入新节点 3、删除指定索引的节点 4、更新指定索引的节点的值 

1.1、单向链表的节点结构

 使用类模版封装链表的节点结构, 链表的节点除了存储数据之外还要还要存储指针, 而且链表应该还能对节点的指针进行操作

template 
    
     class CListNode{protected:	//节点的值	T m_nodeValue;	//节点对应的指针，用于指向下一节点	CListNode
     
       * m_link;public:	//默认构造函数	CListNode();	//构造函数	CListNode(const T& value);	//获取节点的值	const T& GetNodeValue() const;	//设置节点的值	void SetNodeValue(T value);	//设置节点的指针	void SetNodeLink(CListNode
      
        * next);	//获取节点的指针	CListNode
       
        * GetNodeLink();};
       
      
     
    

1.1.1、节点的构造函数实现

主要是初始化节点的值和指针

template
    
     CListNode
     
      ::CListNode():m_link(0){}template
      
       CListNode
       
        ::CListNode(const T& value):m_nodeValue(value), m_link(0){}
       
      
     
    

1.1.2、设置和获取节点的值

template
    
     const T& CListNode
     
      ::GetNodeValue() const{	return m_nodeValue;}template
      
       void CListNode
       
        ::SetNodeValue(T value){	m_nodeValue = value;}
       
      
     
    

1.1.3、设置和获取节点的指针

template
    
     void CListNode
     
      ::SetNodeLink(CListNode
      
        * next){	m_link = next;}template
       
        CListNode
        
         * CListNode
         
          ::GetNodeLink(){ return m_link;}
         
        
       
      
     
    

 

 1.2、单向链表的定义和实现

 

template 
    
     class CLinkList{private:	//链表的头节点	CListNode
     
       * m_head;	//链表的尾节点	CListNode
      
        * m_tail;private:	//获取指定索引的指针（从头节点开始（索引0））	CListNode
       
         * GetLink(size_t index);	//获取链表节点个数	size_t GetCount() const;	//获取链表的头节点	CListNode
        
          *GetHead() const;public:	CLinkList();	virtual ~CLinkList();	//链表表尾插入节点	bool AddTail(const T value);	//在链表指定位置插入节点	bool InsertAt(unsigned int index, const T& value);	//删除链表指定位置的节点	bool RemoveAt(size_t index, T & value);	//获取指定位置节点的值	bool GetNodeAt(size_t index, T & value); 	//更新指定位置节点的值	bool UpdateAt(size_t index, const T & value);	//删除链表所有节点	bool RemoveAll();	//重载链表输出运算	friend ostream & operator<<(ostream & os, const CLinkList
         
           & alist) { CListNode
          
            * pNode = alist.GetHead(); while(pNode = pNode->GetNodeLink()) { os << pNode->GetNodeValue() << " "; } return os; } };
          
         
        
       
      
     
    

 1.2.1、创建链表及获取链表的头节点

template
    
     CListNode
     
      * CLinkList
      
       ::GetHead() const{	//返回首节点指针	return m_head;}template
       
        CLinkList
        
         ::CLinkList(){	//创建首节点和尾节点	m_head = m_tail = new CListNode
         
          ; //设置节点 m_tail->SetNodeLink(0);}
         
        
       
      
     
    

 

1.2.2、获取链表指定索引的指针

template
    
     CListNode
     
       * CLinkList
      
       ::GetLink(size_t index){	//判断位置的合法性	if(index < 0 || index >= GetCount())	{		return 0;	}	//从首节点开始查找	CListNode
       
         * curNode = m_head;	while(index--)	{			curNode = curNode->GetNodeLink();	}	//返回找到的节点	return curNode;}
       
      
     
    

1.2.3、获取链表的节点个数

template
    
     size_t CLinkList
     
      ::GetCount() const{	size_t cnt = 0;	//从首节点开始遍历，	CListNode
      
        * pLink = m_head;	while(true)	{		cnt++;		pLink = pLink->GetNodeLink();		//链表遍历完成退出循环		if(m_tail == pLink)			break;	}	//返回链表节点个数	return cnt;}
      
     
    

1.2.4、在链表的尾节点插入新节点

template
    
     bool CLinkList
     
      ::AddTail(const T value){	//创建新节点	CListNode
      
        * aNode = new CListNode
       
        (value);	//创建失败，返回false	if(0 == aNode)		return false;	//在尾节点插入新节点	m_tail->SetNodeLink(aNode);	m_tail = m_tail->GetNodeLink();	m_tail->SetNodeLink(0);	if(0 == m_tail)	{		return false;	}	return true;}
       
      
     
    

1.2.5、在链表任意指定索引中插入新节点

template
    
     bool CLinkList
     
      ::InsertAt(unsigned int index, const T& value){	//创建新节点	CListNode
      
        * aNode = new CListNode
       
        (value);	if(0 == aNode)		return false;	//获取指定位置节点的指针	CListNode
        
          * curNode = GetLink(index);	//插入新节点	aNode->SetNodeLink(curNode->GetNodeLink());	curNode->SetNodeLink(aNode);	if(0 == curNode->GetNodeLink())	{		return false;	}	return true;}
        
       
      
     
    

1.2.6、删除链表中任意指定索引的节点

template
    
     bool CLinkList
     
      ::RemoveAt(size_t index, T & value){	//获取待删除索引的节点	CListNode
      
        * pNode = GetLink(index);	if(0 ==pNode)	{		return false;	}	//获取待删除索引的前一个节点	CListNode
       
         * pPreNode = GetLink(index-1);		if(0 != pPreNode)	{		pPreNode->SetNodeLink(pNode->GetNodeLink());	}	else		m_head->SetNodeLink(pNode->GetNodeLink()); //在链表首节点插入新节点	value = pNode->GetNodeValue();//返回删除节点的值	delete pNode;	return true;}
       
      
     
    

1.2.7、获取链表中指定索引的节点的值

template
    
     bool CLinkList
     
      ::GetNodeAt(size_t index, T & value) {	//获取节点的指针	CListNode
      
        * pNode = GetLink(index);	if(0 == pNode)	{		return false;	}	//获取节点的值	value = pNode->GetNodeValue();	return true;}
      
     
    

1.2.9、更新链表中指定索引的节点的值

template
    
     bool CLinkList
     
      ::UpdateAt(size_t index, const T & value){	CListNode
      
        * pNode = GetLink(index);	if(0 == pNode)	{		return false;	}	//设置节点的值	pNode->SetNodeValue(value);	return true;}
      
     
    

1.2.10、删除链表中所有的节点

template 
    
     bool CLinkList
     
      ::RemoveAll(){	size_t i = 1;	T value;	for(; i < GetCount(); ++i)	{		RemoveAt(i, value);	}	return true;}
     
    

1.2.11、析构函数

template
    
     CLinkList
     
      ::~CLinkList(){  RemoveAll(); }
     
    

 1.3、存在的问题

 单向链表在获取当前节点的前一个节点时，需要从链表的首节点重新开始查找