链表的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本程序List链表用两种方式实现，一种是双向链表，一种是双向循环链表。循环双向链表和双向链表，它们的编码差别很小；但是循环链表在插入效率上胜出很多，同时查询时候更灵活。综合考虑，循环链表是首选。

另外，不同于Windows上的ListEntry结构，本LIST结构没有链表头。对于链表头，各有各的说法，但是天下没有免费的午餐，某个地方得了好处，必然会在别的地方承担一定的损失。总之一句话，我个人的理念是，中间代码尽可能简单易用，以此链表头弃之不用。

非常简单的两种链表实现，主要是查询、插入、删除几个功能的实现，总共的cpp代码不过300行左右，在座的各位都是软件开发小能手，功能实现不再赘述。

完整工程代码：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;
};

循环双向链表实现代码如下：



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;
}

双向链表实现代码：文章来源地址https://www.toymoban.com/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;
}