Java实现ArrayList和LinkedList的方式采用的是数组和链表。以下是用C++代码的模拟：
声明Collection接口：
#ifndef COLLECTION_H_
#define COLLECTION_H_
template<class T>
class Collection {
public:
virtual ~Collection() {
}
virtual bool add(T* e) = ;
virtual int contains(T* e) = ;
virtual bool isEmpty() = ;
virtual bool remove(T* e) = ;
virtual int size() = ;
}; #endif /* COLLECTION_H_ */
声明List接口
#ifndef LIST_H_
#define LIST_H_
#include "Collection.h"
template<class T>
class List: public Collection<T> {
public:
virtual ~List() {
}
virtual void add(int index, T* e) = ;
virtual T* get(int index) = ;
virtual T* remove(int index) = ;
}; #endif /* LIST_H_ */
接口声明完成以后就是具体实现。通过C++的模板来模拟Java中的泛型机制，通过嵌套Iterator类实现各自的迭代器。由于在Java中Iterator最常用的方法是hasNext()和next()。因此本文只做了这两个方法的实现。
ArrayList.h
#ifndef ARRAYLIST_H_
#define ARRAYLIST_H_
#include "List.h"
template<class T, int bsz = > // bsz代表每次扩展数组的步长
class ArrayList: public List<T> { // 继承List和Collection
int len; // 已使用量
int max; // 最大长度
T** items;
void inflate(); // 扩充数组
ArrayList(const ArrayList&); // 处于使用习惯隐藏拷贝函数，用户只能通过引用或指针
public:
ArrayList() :
len(), max(bsz), items(new T*[bsz]) {
}
virtual ~ArrayList();
bool add(T* e); // 增加元素
int contains(T* e); // 判断是否包含
bool isEmpty(); // 判断容器是否为空
bool remove(T* e); // 移除元素
int size(); // 获取容器容量
void add(int index, T* e); // 增加元素
T* get(int index); // 获取元素
T* remove(int index); // 删除元素
class Iterator;
friend class Iterator;
class Iterator { // 创建迭代器
ArrayList& al;
int index;
public:
Iterator(ArrayList& list) :
al(list), index() {
}
bool hasNext() {
if (index < al.len) {
return true;
}
return false;
}
T* next() {
if (hasNext()) {
return al.items[index++];
}
return ;
}
};
};
/**
* 以下是实现，如果处于效率考虑。有些函数可以增加inline。
*/
template<class T, int bsz>
ArrayList<T, bsz>::~ArrayList() {
for (int i = ; i < len; i++) {
delete items[i];
items[i] = ; // 清理对象
}
delete items; // 清空数组
}
template<class T, int bsz>
void ArrayList<T, bsz>::inflate() {
if (len == max) {
max += bsz; // 数组增加并且赋值保存的指针
T** newItems = new T*[max];
for (int i = ; i < len; i++)
newItems[i] = items[i];
delete[] items; // 清空原始数组：这里很重要！如果不清理会多出很多匿名数组占用内存。
items = newItems;
}
}
template<class T, int bsz>
bool ArrayList<T, bsz>::add(T* e) {
inflate();
items[len++] = e;
return true;
}
template<class T, int bsz>
int ArrayList<T, bsz>::contains(T* e) { // 判断是否包含：判断是否相同的标准是两个对象指针是否指向同一块内存。
for (int i = ; i < len; i++) {
if (get(i) == e) {
return i; // 返回下标
}
}
return -;
}
template<class T, int bsz>
int ArrayList<T, bsz>::size() { // 获取容器容量
return len;
}
template<class T, int bsz>
bool ArrayList<T, bsz>::remove(T* e) { // 调用内部的两个函数组合作为实现
int index = contains(e);
if (index != -) {
remove(index);
return true;
}
return false;
}
template<class T, int bsz>
bool ArrayList<T, bsz>::isEmpty() { // 判断容器是否为空
if (len == ) {
return true;
} else {
return false;
}
}
template<class T, int bsz>
void ArrayList<T, bsz>::add(int index, T* e) { // 增加元素：插入
inflate();
T* newItems[++len];
index--; // 下标
for (int i = ; i < len; i++) {
if (i < index) {
newItems[i] = items[i];
}
if (i == index) {
newItems[i] = e;
}
if (i > index) {
newItems[i] = items[i - ];
}
}
items = newItems;
}
template<class T, int bsz>
T* ArrayList<T, bsz>::get(int index) { // 获取元素
if (index < || index >= len) {
return ;
}
return items[index];
}
template<class T, int bsz>
T* ArrayList<T, bsz>::remove(int index) { // 删除元素
if (index < || index >= len) {
return ;
}
T* result = get(index);
T* newItems[len - ];
for (int i = ; i < len; i++) {
if (i < index) {
newItems[i] = items[i];
}
if (i > index) {
newItems[i - ] = items[i];
}
}
delete items;
items = newItems;
len--;
return result;
}
#endif /* ARRAYLIST_H_ */
很明显，和Java中的ArrayList实现一样。进行插入的代价是很高的。
LinkedList.h
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "List.h"
#include <iostream>
using namespace std;
template<class T>
class LinkedList: public List<T> {
struct Item { // 链表结构
Item(T* d, Item* nxt = , Item* pre = ) : // d:保存数据，nxt:指向前一个链表结构，pre:指向下一个链表结构。
data(d), next(nxt), prev(pre) {
}
T* data;
Item* next;
Item* prev;
};
int len; // 长度
Item* head; // 链表的头指针
Item* tail; // 链表的尾指针
LinkedList(const LinkedList&); // 隐藏拷贝函数
public:
LinkedList() :
len(), head(), tail() {
}
virtual ~LinkedList() {
if (len != ) {
while (head->next != ) {
Item* item = head;
head = item->next;
delete item;
item = ;
}
}
}
bool add(T* e); // 增加元素
int contains(T* e); // 判断是否包含
bool isEmpty(); // 判断容器是否为空
bool remove(T* e); // 删除元素
int size(); // 获取容器容量
void add(int index, T* e); // 增加元素
T* get(int index); // 获取元素
T* remove(int index); // 删除元素
class Iterator;
friend class Iterator;
class Iterator {
LinkedList& ll;
int index;
public:
Iterator(LinkedList& list) :
ll(list), index() {
}
bool hasNext() {
if (index < ll.len) {
return true;
}
return false;
}
T* next() {
if (hasNext()) {
return ll.get(index++);
}
return ;
}
};
};
/**
* 以下为实现
*/
template<class T>
bool LinkedList<T>::add(T* e) { // 入栈操作
add(len, e);
return true;
}
template<class T>
int LinkedList<T>::contains(T* e) {
Item* temp = head;
for (int i = ; i < len; i++) {
if (temp->data == e) {
return i;
}
temp = temp->next;
}
return -;
}
template<class T>
bool LinkedList<T>::isEmpty() {
if (len == ) {
return true;
} else {
return false;
}
}
template<class T>
bool LinkedList<T>::remove(T* e) {
int index = contains(e);
if (index != -) {
remove(index);
return true;
}
return false;
}
template<class T>
int LinkedList<T>::size() {
return len;
}
template<class T>
void LinkedList<T>::add(int index, T* e) { // 插入
if (index > || index <= len) {
if (len == ) { // 第一个对象加入的时候，head引用和tail引用指向同一个
Item* first = new Item(e);
head = first;
tail = first;
} else if (index == ) { // 如何插入第一个位置，则更新head引用
Item* temp = new Item(e, head, );
head->prev = temp;
head = temp;
} else if (index == len) { // 如果插入最后一个位置，则更新tail引用
Item* temp = new Item(e, , tail);
tail->next = temp;
tail = temp;
} else { // 更新中间元素
Item* itemPrev = head;
for (int i = ; i < index; i++) {
itemPrev = itemPrev->next;
}
Item* itemNext = itemPrev->next;
Item* newItem = new Item(e, itemNext, itemPrev);
itemPrev->next = newItem;
itemNext->prev = newItem;
}
len++;
}
}
template<class T>
T* LinkedList<T>::get(int index) { //
if (index >= || index < len) {
Item* result = head;
for (int i = ; i < index; i++) {
result = result->next;
}
return result->data;
}
return ;
}
template<class T>
T* LinkedList<T>::remove(int index) {
if (index > || index <= len) {
if (index == ) { // 删除head引用
Item* temp = head;
head = temp->next;
head->prev = ;
T* result = temp->data; // 建立指向返回值的指针。
delete item;
item = ;
return result;
} else if (index == len) { // 删除tail引用
Item* temp = tail;
tail = temp->prev;
tail->next = ;
T* result = temp->data;
delete item;
item = ;
return result;
} else {
Item* item = head;
for (int i = ; i < index; i++) { // 通过迭代获取目标指针
item = item->next;
}
Item* itemPrev = item->prev;
Item* itemNext = item->next;
itemPrev->next = itemNext;
itemNext->prev = itemPrev;
T* result = item->data;
delete item;
item = ;
return result;
}
len--;
}
return ;
} #endif /* LINKEDLIST_H_ */
LinkedList中所有的查询都必须依赖迭代完成，代价较高。但是插入的代价却比较低。这一点与JDK中的表现一致。
总结：
（1）C++的内存模型比Java复杂，因此可选择的余地也更多。本例程采用完全使用指针实现，基本等同于Java的实现方式。当然你也可以使用位拷贝的方式或&引用来做。有兴趣的可以自己摸索。
（2）C++中的垃圾清理需要手动完成，没有Java来的方便。虽然也提供了析构函数可以自行调用，但是通过观察例程很明显并非所有的工作都可以交给析构函数。更典型的做法是在函数内部随时清理。
如何使用：一个简单测试例程
#include "ArrayList.h"
#include "LinkedList.h"
#include <iostream>
#include <fstream>
using namespace std;
int main() {
// 测试ArrayList<int>
ArrayList<int> ia;
for (int i = ; i < ; i++) {
int* v = new int(i);
ia.add(v);
}
cout << ia.size() << endl;
for (int i = ; i < ia.size(); i++)
cout << *ia.get(i) << endl; // 测试ArrayList<string>
ArrayList<string> sa;
fstream in;
in.open("Main.cpp");
string line;
while (getline(in, line)) {
sa.add(new string(line));
}
for (int i = ; i < sa.size(); i++) {
cout << *sa.get(i) << endl;
}
in.close(); // 测试LinkedList<int>
LinkedList<int> il;
for (int i = ; i < ; i++) {
il.add(new int(i));
}
for (int i = ; i < il.size(); i++) {
cout << *il.get(i) << endl;
} // 测试LinkedList<string>
LinkedList<string> sl;
in.open("Main.cpp");
while (getline(in, line)) {
sl.add(new string(line));
}
for (int i = ; i < sl.size(); i++) {
cout << *sl.get(i) << endl;
}
in.close(); // 测试ArrayList<int>的迭代
ArrayList<int>::Iterator iat(ia);
while (iat.hasNext()) {
cout << *iat.next() << endl;
} // 测试ArrayList<string>的迭代
ArrayList<string>::Iterator ist(sa);
while (ist.hasNext()) {
cout << *ist.next() << endl;
} // 测试LinkedList<int>的迭代
LinkedList<int>::Iterator ilt(il);
while (ilt.hasNext()) {
cout << *ilt.next() << endl;
} // 测试LinkedList<string>的迭代
LinkedList<string>::Iterator slt(sl);
while (slt.hasNext()) {
cout << *slt.next() << endl;
}
}