配列実現チェーン

黎大王はnext[]で二つの置換軌道を表し、一つはoccupied、もう一つはvacantという方法を提案しました.
そして操作ごとにこの二つのレールを維持します.
暇があったら、また書きましょう.
---------------------------------
2018-1-2
利用可能な場所を探す方法は最適化できます.
利用可能な位置は、データ構造(スタックまたはキュー)を使用して記憶されます.
O(1)の効率を達成することができます.
------------------------------------
曹様の招待に応じて、配列でチェーンを実現する方法について書いてください.
2017-12-31
参考:『アルジェブラ引論』——カーストリーゴールドP 36置き換え
https://zh.wikipedia.org/wiki/%E7%BD%AE%E6%8F%9B
参考テーマ:
http://www.lintcode.com/zh-cn/problem/recover-rotated-sorted-array/
http://blog.csdn.net/rsy56640/article/details/78494242
悲劇のテキストBroken Keyboard
http://www.cnblogs.com/zx-zhang/p/7719944.html
http://www.voidcn.com/article/p-oxiboomv-bkb.html

#include  
#include 
using namespace std;

class MyListException {
public:
	MyListException(std::string _msg) :msg(_msg) {}
	friend ostream& operator< list_size + 1)throw MyListException("The position is invalid.");
	if (list_size == maxSize)throw MyListException("List is full.");
	//after the cur
	if (num == list_size + 1) {
		push_back(e);
		return;
	}
	list_size++;
	int index = head, pre, pos = pos_available();
	for (int i = 1; i < num; ++i) {
		pre = index;
		index = next[index];
	}
	//before the head
	if (num == 1) {
		list[pos] = e;
		next[pos] = head;
		head = pos;
		return;
	}
	//other trivial conditions
	next[pre] = pos;
	list[pos] = e;
	next[pos] = index;
}

void MyList::push_back(const int e) {
	if (list_size == maxSize)throw MyListException("List is full.");
	if (list_size++ == 0) {
		list[head] = e;
		cur = head;
		return;
	}
	int pos = pos_available();
	next[cur] = pos;
	list[pos] = e;
	cur = pos;
}

//delete the nth element.
void MyList::erase(const int num) {
	if (num < 1 || num > maxSize)throw MyListException("The position is invalid.");
	if (list_size < num)throw MyListException("Not enough elements.");
	if (list_size == 0)throw MyListException("List is empty.");
	list_size--;
	int index = head, pre;
	for (int i = 1; i < num; ++i) {
		pre = index;
		index = next[index];
	}
	//delete head == cur
	if (list_size == 0) {
		cur = -1;
		return;
	}
	//delete head element.
	if (num == 1) {
		head = next[index];
		next[index] = null;
		return;
	}
	//delete the last;
	if (index == cur) {
		cur = pre;
		next[pre] = null;
		return;
	}
	//other trivial conditions
	next[pre] = next[index];
	next[index] = null;
}

int MyList::front() const {
	return list[head];
}

int MyList::back() const {
	if (list_size == 0)throw MyListException("List is empty.");
	return list[cur];
}

int MyList::size() const {
	return list_size;
}

int MyList::max_size() const {
	return maxSize;
}

bool MyList::empty() const {
	return list_size == 0;
}

int MyList::pos_available() const {
	int pos = 0;
	for (int i = 1; i < maxSize; ++i) {
		pos = (i + cur) % maxSize;
		if (next[pos] == null)return pos;
	}
}

MyList::~MyList() {
	delete[] list;
	delete[] next;
}


int main() {

	MyList list(5);

	try {
		//do something


	}
	catch (MyListException e) {
		cout << e << endl;
	}

	system("pause");
	return 0;
}