带头节点的双向循环链表

用C++和Java实现带头节点的双向循环链表，要继承linearList类，并实现它的所有功能，另外，必须实现双向迭代器。

实现带头节点的双向循环链表，要具有以下的功能：

1. 判断表是否为空，如果为空则返回true，不空返回false.
2. 给出表中数据元素的个数。
3. 给定一个索引（位置），返回指向该位置的数据元素的指针，如果给定的位置号不合法，则返回空指针。
4. 给定数据元素x，如果表中有该元素，则返回x第一次出现的索引，若x 不存在，则返回-1.
5. 删除给定索引的数据元素。
6. 给定索引index ,数据元素x，将x插入到index的位置。

C++：设计一个结构体struct chainNode，再设计一个具体类 class doubleChain 作为抽象类 class linearList的派生类实现类linearList中的所有方法，外加实现双向迭代器；

 

C++：

linearList.h:
#ifndef SRC_LINEARLIST_H_
#define SRC_LINEARLIST_H_
#include <iostream>
#include <iterator>
#include <algorithm>

template <typename T>
class linearList {
public:
	virtual ~linearList(){};//需要定义
	virtual bool empty() const = 0;
	virtual int size() const = 0;
	virtual T& get(int theIndex) const = 0;
	virtual int indexOf(const T& theElement) const = 0;
	virtual void erase(int theIndex) = 0;
	virtual void insert(int theIndex, const T& theElement) = 0;
	virtual void output(std::ostream& out) const = 0;
};

#endif /* SRC_LINEARLIST_H_ */

doubleChain.h:
#ifndef DOUBLECHAIN_H_
#define DOUBLECHAIN_H_

#include<iostream>
#include<sstream>
#include<string>
#include<iterator>

#include"linearList.h"

template<typename T>
struct chainNode
{
	T element;
	chainNode<T>* next;//可以将chainNode<T>简写为chainNode，因为这是在class chainNode的作用域内
	chainNode<T>* prev;

	chainNode(){next = NULL;prev = NULL;}
	chainNode(const T& element){
		this->element = element;
		next = NULL;
		prev = NULL;
	}
	chainNode(const T& element,chainNode* next,chainNode* prev)//可以将chainNode<T>简写为chainNode，因为这是在class chainNode的作用域内
	{
		this->element = element;
		this->next = next;
		this->prev = prev;
	}
};

template<class T>
class doubleChain : public linearList<T>{
public:
	doubleChain(int initialCapacity = 10);
	~doubleChain();
	bool empty()const{return listSize == 0;}
	int size() const{return listSize;}
	T& get(int theIndex) const;
	int indexOf(const T& theElement) const;
	void erase(int theIndex);
	void insert(int theIndex, const T& theElement);
	void output(std::ostream& out) const;

public:
	void checkIndex(int theIndex) const;
	chainNode<T>* headNode;
	int listSize;

	class iterator;
	iterator begin() const{
		return iterator(headNode->next);
	}
	iterator end() const{
		return iterator(headNode);
	}

class iterator : public std::iterator<std::bidirectional_iterator_tag,T>{//一个类，提供返回类型的iterator_category表示的双向迭代器函数
public:
	iterator(chainNode<T>* theNode = NULL){
		node = theNode;
	}
	T& operator*() const{
		return node->element;
	}
	T* operator->()const{
		return &node->element;
	}
	bool operator == (const iterator right) const{
		return node == right.node;
	}
	iterator& operator++(){
		node = node->next;
		return *this;
	}
	iterator operator++(int){
		iterator old = *this;
		node = node->next;
		return old;
	}
protected:
	chainNode<T>* node;
};

};





#endif /* DOUBLECHAIN_H_ */

doubleChain.cpp:
#include"doubleChain.h"

template<class T>
doubleChain<T>::doubleChain(int initialCapacity)//建立一个空表
{
	if (initialCapacity < 1)
	   throw std::invalid_argument("Initial capacity = " + std::to_string(initialCapacity) + " Must be > 0");
	headNode = new chainNode<T>();
	headNode->next = headNode;
	headNode->prev = headNode;
	listSize = 0;
}

template<class T>
doubleChain<T>::~doubleChain()//析构函数
{
	chainNode<T>* currentNode = headNode->next;
	while(currentNode != headNode)//循环删除所有节点
	{
		chainNode<T>* nextNode = currentNode->next;
		delete currentNode;
		currentNode = nextNode;
	}
	delete headNode;//删除头结点
}

template<class T>
void doubleChain<T>::checkIndex(int theIndex) const//判断索引是否有效
{
	if(theIndex < 0 || theIndex > listSize)
	{
		throw std::out_of_range("index = "+ std::to_string(theIndex)+ "size = "+ std::to_string(listSize));

	}
}

template<class T>
T& doubleChain<T>::get(int theIndex) const
{
	checkIndex(theIndex);//判断索引是否有效
	if(theIndex < listSize/2){//theIndex<listSize/2,从左向右查找
		chainNode<T>* currentNode = headNode->next;//currentNode指向0号元素
		for(int i = 0;i < theIndex;++i)//循环后移currentNode，使其指向索引所在的节点
			currentNode = currentNode->next;
		return currentNode->element;

	}
	else{//theIndex > listSize/2,从右向左查找
		chainNode<T>* currentNode = headNode->prev;//currentNode指向最后一个元素，最后一个元素的索引为listSize-1
		for(int i = listSize -1;i > theIndex;--i)//循环前移currentNode，使其指向索引所在的节点
			currentNode = currentNode->prev;
		return currentNode->element;
	}
}

template<class T>
int doubleChain<T>::indexOf(const T& theElement) const{
	chainNode<T>* currentNode = headNode->next;
	headNode->element = theElement;//将要查找的元素放入头节点
	int index = 0;
	while(currentNode->element != theElement){//从第一个往后遍历一遍
		currentNode = currentNode->next;
		++index;//记住下标
	}
	if(currentNode == headNode)
		return -1;
	else
		return index;
}

template<class T>
void doubleChain<T>::insert(int theIndex,const T& theElement){
	checkIndex(theIndex);//判断索引是否有效
	chainNode<T>* p = headNode;
	chainNode<T>* q;
	for(int i = 0;i < theIndex;++i)//通过循环将p指向要插入节点索引的前一个节点
		p = p->next;
	q = new chainNode<T>(theElement,p->next,p);//创建一个新节点
	p->next->prev = q;//改变指针指向位置
	p->next = q;

	listSize++;//链表节点个数加1
}

template<class T>
void doubleChain<T>::erase(int theIndex){
	checkIndex(theIndex);//判断索引是否有效
	chainNode<T>* deleteNode;
	chainNode<T>* p = headNode;
	for(int i = 0;i < theIndex;++i)//找到需要删除的节点的前一个节点
		p = p->next;
	deleteNode = p->next;//删除后断开了要重新结合
	p->next = deleteNode->next;
	deleteNode->next->prev = p;
	listSize--;

	delete deleteNode;

}

template<class T>
void doubleChain<T>::output(std::ostream& out)const{
	chainNode<T>* currentNode = headNode->next;
	while(currentNode != headNode){//循环输出element
		out<< currentNode->element<<" ";
		currentNode = currentNode->next;
	}
}

template<class T>
std::ostream& operator<<(std::ostream& out,const doubleChain<T>& x)
{
	x.output(out);
	return out;
}


text.cpp:
#include"doubleChain.cpp"
#include<numeric>
using std::cout;
using std::endl;
int main(){
	doubleChain<int> y(2);
	cout<<"y的初始尺寸为 "<<y.size()<<endl;
	if(y.empty())
		cout<<"y为空"<<endl;
	else
		cout<<"y不为空"<<endl;

	y.insert(0,1);
	y.insert(1,2);
	y.insert(2,3);
	y.insert(3,4);
	y.insert(4,5);
	y.insert(4,6);
	cout<<"插入6后y应该为 1 2 3 4 5 6"<<endl;
	cout<<"y的尺寸为"<<y.size()<<endl;
	if(y.empty())
		cout<<"y为空"<<endl;
	else
		cout<<"y不为空"<<endl;
	cout<<y<<endl;
	cout<<"元素4的索引为:"<<y.indexOf(4)<<endl;
	y.erase(0);
	cout<<"删除0号元素后应该为 2 3 4 6 5:"<<endl;
	cout<<y<<endl;
	y.erase(3);
	cout<<"删除3号元素后应该为 2 3 4 5:"<<endl;
	cout<<y<<endl;
	return 0;
}

Java：设计一个接口interface linearList<T>，设计一个类class doubleChainNode<T>相当于C++中的结构体，设计一个类class doubleChainjava<T>实现了了接口linearList<T>所有方法，以及实现迭代器接口Iterable<T>中的一个方法Iterator<T> iterator();

Java:

linearList.java:
public interface linearList<T> {
	public boolean empty();
	public int size();
	public T get(int theIndex) throws Exception;
	public int indexOf(T theElement);
	public void erase(int theIndex) throws Exception;
	public void insert(int theIndex,T theElement) throws Exception;
	public void output();

}

doubleChainNode.java:
public class doubleChainNode<T> {
	T element;
	doubleChainNode<T> next;
	doubleChainNode<T> prev;
	
	public doubleChainNode() {next = prev = null;}
	public doubleChainNode(T element) {
		this.element = element;	
		next = prev = null;
		}
	public doubleChainNode(T element,doubleChainNode<T> prev,
			doubleChainNode<T> next) {
		this.element = element;
		this.prev = prev;
		this.next = next;
	}

}
doubleChain.java:
import java.util.*;

public class doubleChain<T> implements linearList<T>,Iterator<T>{
	public doubleChainNode<T> headNode;//指向链表的头结点
	public int listSize;//链表的元素个数
	
	private void checkIndex(int theIndex) throws Exception{//判断索引是否有效
		if(theIndex<0 || theIndex >= listSize)//索引要在0和listSize之间
			throw new Exception("index = "+theIndex+"size = "+listSize);//抛出异常
		
	}
	public doubleChain(int initialCapacity) throws Exception{//doubleChain的构造函数，创建一个空链表
		if(initialCapacity < 1) {//定义时链表长度<1就抛出异常
			throw new Exception("Initial capacity = "+initialCapacity+"Must be > 0 ");
			
		}
		headNode = new doubleChainNode<T>(null);//空的头结点
		headNode.next = headNode;//头结点的next指向头结点
		headNode.prev = headNode;//头结点的prev指向头结点
		listSize = 0;//链表内没有元素
	}
	

	
	public boolean empty() {//判断链表是否为空
		return listSize == 0;//listSize为0是返回true，链表为空。listSize不为0时返回false，链表不为空
	}
	
	public int size() {//返回双向链表的长度
		return listSize;//listSize的值就是链表中元素的个数
	}
	
	public T get(int theIndex) throws Exception {//获得相应索引的element
		
		checkIndex(theIndex);//判断索引是否有效
		if(theIndex < listSize/2) {//theIndex < listSize/2,从左向右查找 
			doubleChainNode<T> currentNode = headNode.next;//currentNode指向0号节点
			for(int i = 0;i < theIndex;i++)//找到theIndex所在的位置
				currentNode = currentNode.next;//循环将currentNode后移
			return currentNode.element;//返回element
			
		}
		else {//teIndex > listSize/2,从右向左查找
			doubleChainNode<T> currentNode = headNode.prev;//currentNode指向最后一个节点
			for(int i = listSize-1;i>theIndex;i--)//最后一个元素的索引是listSize-1，
				currentNode = currentNode.prev;//循环将currentNode前移
			return currentNode.element;//返回element
			
		}
	}

	public int indexOf(T theElement) {
		
		int index = 0;//定义index来记住元素位置
		doubleChainNode<T> currentNode = headNode.next;//currentNode指向0号节点
		headNode.element = theElement;//将要查找的元素放入头节点
		while(currentNode.element != theElement) {//currentNode的element不等于theElement
			//从第一个往后遍历一遍
			currentNode = currentNode.next;//currentNode后移
			index++;//记住下标
			
		}
		if(currentNode == headNode)//currentNode等于headerNode，链表中没有这个元素，返回-1
			return -1;
		else return index;//对应的下标就是索引
	}
	
	public void erase(int theIndex) throws Exception{//删除对应索引的节点
		checkIndex(theIndex);//判断索引是否有效
		doubleChainNode<T> deleteNode;//定义一个空节点
		doubleChainNode<T> p = headNode;//定义p等于headerNode
		for(int i= 0;i < theIndex;++i)//找到要删除的节点
			p = p.next;//循环后移p，使p指向要删除节点的前一个节点
		deleteNode = p.next;//删除后断开了还要进行左右缝合
		p.next = deleteNode.next;//p的next指向要删除节点的后一个节点
		deleteNode.next.prev = p;//要删除节点的后一个节点的prev指向p
		
		listSize--;//链表元素个数-1
		//delete deleteNode;
		
	}
	@Override
	public void insert(int theIndex,T theElement) throws Exception{//插入函数

		doubleChainNode<T> p = headNode;
		doubleChainNode<T> q;
		checkIndex(theIndex);//判断索引是否有效
		for(int i = 0;i < theIndex;++i) {//移动p，使p指向要插入位置的前一个节点
			p = p.next;
		}
		q = new doubleChainNode<T>(theElement,p,p.next);//定义节点q，里面存放元素theElement，前驱指向p，后驱指向要插入位置的节点，q就是要插入的节点
		p.next.prev = q;//要插入位置节点的前驱指向q
		p.next = q;//插入位置的前一个节点的后驱指向q
		
		listSize++;//链表中元素个数加1
		
	}

	public void output() {//输出函数

		doubleChainNode<T> currentNode = headNode.next;//currentNode指向0号节点
		for(int i = 0;i < listSize;++i) {
			System.out.print(currentNode.element+" ");//输出element
			currentNode = currentNode.next;//currentNode后移
		}
		
	}
	public Iterator<T> iterator(){//迭代器
		class Myiterator implements Iterator<T>{
			public doubleChainNode<T> currentNode = headNode;
			public boolean hasNext() {//判断currentNode是否等于头节点
				return currentNode.next != headNode;
			}
			public T next() {//返回element
				if(currentNode.next != headNode) {
					currentNode = currentNode.next;
					return currentNode.element;
				}
				return null;
			}
		}
		return new Myiterator();
	}

	public boolean hasNext() {

		return false;
	}
	
	public T next() {

		return null;
	}
}

text.java:
import java.util.Iterator;


public class text {
	public static void main(String[] args)throws Exception{
		doubleChain<Integer> p = new doubleChain<Integer>(5);
		p.insert(0,1);
		p.insert(1,2);
		p.insert(2,3);
		p.insert(3,4);
		p.insert(0,5);
		
		if(p.empty())
			System.out.println("y为空");
		else
			System.out.println("y不为空");
		System.out.println("p的尺寸为 "+p.size());
		System.out.print("p是");
		p.output();
		System.out.print("\n 元素1的索引为 "+p.indexOf(1));
		System.out.println("\n 索引为2的元素为 "+p.get(2));
		p.erase(3);
		System.out.println("删除3后p为");
		p.output();
		p.insert(2, 6);
		System.out.println("\n 2号位置上插入6后p为");
		p.output();
		System.out.println("\n 迭代器列表是:");
		for(Iterator<Integer> iter = p.iterator(); iter.hasNext();) {
			Integer i = (Integer)iter.next();
			System.out.println(i);
		}

	}

}