链表的实现

本程序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;
}

双向链表实现代码：

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