1. 概念及基本框架

在4.1 中我们通过 二分搜索树 实现了集合，这一节我们通过 链表 来实现集合。

集合 的基本特性依然要满足：集合内的元素 不能重复 。
注：有些集合（多重集合）中元素也可以重复。
同 4.1 一样，我们先利用一个由 纯虚函数 构成的 抽象类 作为一个接口来定义这些操作。具体代码如下：

template <class T>
class Set{
public:
	virtual int size() = 0;
	virtual bool isEmpty() = 0;
	//增加操作
	virtual void add(T num) = 0;
	//删除操作
	virtual void remove(T num) = 0;
	//查找操作
	virtual bool contains(T num) = 0;
};

下面只需要通过继承 抽象类，并且重写 纯虚函数 ，就可以完成 集合 的实现。集合类的框架如下：

template <class T>
class LinkedListSet : public Set<T>{
	...
private:
	LinkedList<T> list;
};

同样，这里为了避免重复设计就可以兼容更多数据类型，引入了 泛型 ，即 模板 的概念。（模板的关键字是 class 或 typename）
这里的 list 表示一个 链表 ，同样，为了保护数据，变量设置为 private 。
注：这里没有显式的给出构造函数，因为子类中除了链表对象之外没有特别需要初始化的东西。编译器会默认先调用 链表 类（即父类）的构造函数，再去调用 集合 类（即子类）的构造函数。
实现了前面的程序之后，接下来就是一个集合的增、删、查以及一些其他基本操作，接下来利用代码去实现。

2. 基本操作程序实现

2.1 增加操作

template <class T>
class LinkedListSet : public Set<T>{
public:
	...
	//增加操作
	void add(T num){
		if (!list.contains(num)){
			list.addFirst(num);
		}
	}
	...
};

为了减小时间复杂度，这里使用针对链表第一个元素进行操作，下面的同理。
注：这里需要进行判断，因为链表中的元素可以重复。

2.2 删除操作

template <class T>
class LinkedListSet : public Set<T>{
public:
	...
	//删除操作
	void remove(T num){
		while (list.contains(num)){
			list.removeElement(num);
		}
	}
	...
};

因为我实现的链表只能删除第一个满足条件元素，为了删除所有满足条件元素，需要循环判断。实际实现只需要遍历一遍链表即可完成删除操作。

2.3 查找操作

template <class T>
class LinkedListSet : public Set<T>{
public:
	...
	//查找操作
	bool contains(T num){
		return list.contains(num);
	}
	...
};

2.4 其他操作

集合还有一些其他的操作，包括 集合大小 的查询等操作。

template <class T>
class LinkedListSet : public Set<T>{
public:
	int size(){
		return list.size();
	}
	bool isEmpty(){
		return list.isEmpty();
	}
	...
};

3. 算法复杂度分析

3.1 增加操作

函数	最坏复杂度	平均复杂度
add	O(n)	O(n)

因为需要判断是否存在该元素，所以需要遍历一遍整个链表。

3.2 删除操作

函数	最坏复杂度	平均复杂度
remove	O(n) =	O(n)

3.3 查找操作

函数	最坏复杂度	平均复杂度
contains	O(n)	O(n/2) = O(n)

总体情况：

操作	时间复杂度
增	O(n)
删	O(n)
查	O(n)

由于链表不具有有序性，所以操作都需要 O(n) 级别的时间复杂度。

4. 完整代码

程序完整代码（这里使用了头文件的形式来实现类）如下，本节不再提供 链表 类的实现代码，如有需要，可参看 2.1 。
抽象类 接口代码：

#ifndef __SET_H__
#define __SET_H__

template <class T>
class Set{
public:
	virtual int size() = 0;
	virtual bool isEmpty() = 0;
	//增加操作
	virtual void add(T num) = 0;
	//删除操作
	virtual void remove(T num) = 0;
	//查找操作
	virtual bool contains(T num) = 0;
};

#endif

集合类 代码：

#ifndef __LINKEDLISTSET_H__
#define __LINKEDLISTSET_H__

#include "LinkedList.h"
#include "Set.h"

template <class T>
class LinkedListSet : public Set<T>{
public:
	int size(){
		return list.size();
	}
	bool isEmpty(){
		return list.isEmpty();
	}
	//增加操作
	void add(T num){
		if (!list.contains(num)){
			list.addFirst(num);
		}
	}
	//删除操作
	void remove(T num){
		while (list.contains(num)){
			list.removeElement(num);
		}
	}
	//查找操作
	bool contains(T num){
		return list.contains(num);
	}
private:
	LinkedList<T> list;
};

#endif