本程序List鏈表用兩種方式實(shí)現(xiàn)，一種是雙向鏈表，一種是雙向循環(huán)鏈表。循環(huán)雙向鏈表和雙向鏈表，它們的編碼差別很??；但是循環(huán)鏈表在插入效率上勝出很多，同時(shí)查詢時(shí)候更靈活。綜合考慮，循環(huán)鏈表是首選。

另外，不同于Windows上的ListEntry結(jié)構(gòu)，本LIST結(jié)構(gòu)沒有鏈表頭。對(duì)于鏈表頭，各有各的說法，但是天下沒有免費(fèi)的午餐，某個(gè)地方得了好處，必然會(huì)在別的地方承擔(dān)一定的損失。總之一句話，我個(gè)人的理念是，中間代碼盡可能簡(jiǎn)單易用，以此鏈表頭棄之不用。

非常簡(jiǎn)單的兩種鏈表實(shí)現(xiàn)，主要是查詢、插入、刪除幾個(gè)功能的實(shí)現(xiàn)，總共的cpp代碼不過300行左右，在座的各位都是軟件開發(fā)小能手，功能實(shí)現(xiàn)不再贅述。

完整工程代碼：https://github.com/satadriver/dataStruct

頭文件：

#pragma once

#include "Element.h"


#pragma pack(1)

typedef struct  _LIST
{
	_LIST* prev;
	_LIST* next;
	ELEMENT* e;
}LIST;



#pragma pack()


class List {
public:
	List();
	~List();
	int insert(ELEMENT* e);
	int remove(ELEMENT* e);

protected:
	LIST* search(ELEMENT* e);
	LIST* mList;
	int mSize;
};



class CList {
public:
	CList();
	~CList();
	int insert(ELEMENT* e);
	int remove(ELEMENT* e);

protected:
	LIST* search(ELEMENT* e);
	LIST* mList;
	int mSize;
};

循環(huán)雙向鏈表實(shí)現(xiàn)代碼如下：

int CList::clear() {
	LIST* l = mList;

	int cnt = 0;
	do
	{
		if (l == 0)
		{
			break;
		}
		LIST* next = l;
		delete l->e;
		delete l;
		l = next;
		cnt++;
	} while (l != mList);

	return cnt;
}



CList::CList() {
	mList = 0;
	mSize = 0;
}

CList::CList(LIST* l) {
	mList = l;
	mSize = 0;
}


CList::~CList() {
	if (mList)
	{
		delete[] mList;
		mList = 0;
	}
}

LIST* CList::search(ELEMENT* e) {
	LIST* list = mList;
	int cnt = 0;
	do
	{
		if (list == 0)
		{
			break;
		}
		if (list->e->e == e->e)
		{
			return list;
		}
		list = list->next;
		cnt++;
	} while (list != mList);

	return 0;
}

int CList::insert(ELEMENT* e) {
	LIST* list = search(e);
	if (list)
	{
		return 0;
	}

	list = new LIST;

	ELEMENT* e_new = new ELEMENT;
	memcpy(e_new, e, sizeof(ELEMENT));

	list->e = e_new;

	if (mList == 0)
	{
		list->next = list;
		list->prev = list;
		mList = list;
	}
	else {
		LIST* prev = mList->prev;

		list->next = mList;
		list->prev = mList->prev;

		if (prev)
		{
			prev->next = list;
		}

		mList->prev = list;
	}

	mSize++;

	return 1;
}


int CList::remove(ELEMENT* e) {
	LIST* list = search(e);
	if (list == 0)
	{
		return 0;
	}

	LIST* next = list->next;
	LIST* prev = list->prev;
	if (next)
	{
		next->prev = prev;
	}

	if (prev)
	{
		prev->next = next;
	}

	delete list->e;

	if (list == mList)
	{
		if (mList->next == mList || mList->prev == mList)
		{
			mList = 0;
		}
		else {
			mList = mList->next;
		}
	}

	delete list;

	int result = mSize;

	mSize--;

	return result;
}

雙向鏈表實(shí)現(xiàn)代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-676139.html

List::List() {
	mList = 0;
	mSize = 0;
}

List::List(LIST* l) {
	mList = l;
	mSize = 0;
}

List::~List() {
	if (mList)
	{
		delete[] mList;
		mList = 0;
	}
}

LIST* List::search(ELEMENT* e) {
	LIST* list = mList;
	int cnt = 0;
	while (list)
	{
		if (list->e->e == e->e)
		{
			return list;
		}
		list = list->next;
		cnt++;
	}

	return 0;
}





int List::insert(ELEMENT* e) {
	LIST* list = search(e);
	if (list)
	{
		return 0;
	}

	list = new LIST;

	ELEMENT* e_new = new ELEMENT;
	memcpy(e_new, e, sizeof(ELEMENT));

	list->e = e_new;

	int cnt = 0;

	if (mList == 0)
	{
		list->next = 0;
		list->prev = 0;
		mList = list;

		cnt++;
	}
	else {
		cnt++;

		LIST* tmp = mList;
		while (tmp->next)
		{
			tmp = tmp->next;
			cnt++;
		}

		list->next = 0;
		list->prev = tmp;

		tmp->next = list;
		cnt++;
	}

	mSize = cnt;

	return cnt;
}


int List::clear() {
	LIST* l = mList;

	int cnt = 0;
	do
	{
		if (l == 0)
		{
			break;
		}
		LIST* next = l;
		delete l->e;
		delete l;
		l = next;
		cnt++;
	} while (l != mList);

	return cnt;
}

int List::remove(ELEMENT* e) {
	LIST* list = search(e);
	if (list == 0)
	{
		return 0;
	}

	LIST* next = list->next;
	LIST* prev = list->prev;
	if (next)
	{
		next->prev = prev;
	}

	if (prev)
	{
		prev->next = next;
	}

	delete list->e;
	if (list == mList)
	{
		if (mList->next == 0)
		{
			mList = 0;
		}
		else {
			mList = mList->next;
		}
	}

	delete list;

	int result = mSize;

	mSize--;

	return result;
}

到了這里，關(guān)于鏈表的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！