和数组不同，链表的数据结构内部多了一个指针指针下一个位置，使得在链表中插入删除特定位置的元素效率很高，代码实现依旧分为三个部分，抽象类LinearList.h，模板类chain.h以及main函数源文件。
废话不多说，我们看代码，这次LinearList.h抽象类里面多了两个成员函数一个是push_back(),一个是clear():
//
// Created by djf on 2016/12/18 0018.
//
#ifndef INC_01_ARRAYLIST_LINEARLIST_H
#define INC_01_ARRAYLIST_LINEARLIST_H
#include
template
class LinearList {
public:
virtual ~LinearList() {};
virtual bool empty() const = 0;
virtual int size() const = 0;
virtual T& get(int index) const = 0;
virtual int indexof(const T& theElement) const = 0;//first pos
virtual void erase(int index) = 0;
virtual void insert(int index, const T& theElement) = 0;
virtual void output(std::ostream& out) const = 0;
//extend
virtual void clear() = 0;
virtual void push_back(const T& theElement) = 0;
};
#endif //INC_01_ARRAYLIST_LINEARLIST_H
``
然后是chain.h，单向链表的模板类：
```cpp
//
// Created by djf on 2016/12/20 0020.
//
#ifndef INC_02_CHAIN_CHAIN_H
#define INC_02_CHAIN_CHAIN_H
#include "LinearList.h"
using namespace std;
template
struct chainNode{
//data
T element;
chainNode *next;
//method
chainNode() {}
chainNode(const T& e) { this->element=e;}
chainNode(const T& e, chainNode* n) { this->element=e;this->next=n;}
};
template
class chain: public LinearList {
public:
//one direction iterator
class iterator{
public:
// typedefs required by C++ for a forward iterator
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//construct
iterator(chainNode* theNode = nullptr) { node = theNode;}
//operator
T& operator*() const { return node->element;}
T* operator&() const { return &node->element;}
iterator& operator++() { node = node->next;return *this;}
iterator operator++(int) { iterator old = *this; node = node->next; return old;}
bool operator==(const iterator rhl) const { return node == rhl.node;}
bool operator!=(const iterator rhl) const { return node != rhl.node;}
//other
protected:
chainNode* node;
};
public:
//consturct copy destory
chain(int initCapacity=10);
chain(const chain&);
~chain();
//ADT method from LinearList.h
bool empty() const override { return listSize==0;};
int size() const override { return listSize;}
T& get(int index) const override;
int indexof(const T&) const override;
void erase(int index) override;
void insert(int index,const T& theElement) override;
void output(ostream& out) const override;
void push_back(const T& theElement) override ;
void clear() override ;
//other
void removeRange(int fromIndex,int toIndex);
int lastIndexOf(const T& theElement);
T& operator[](int index) const;
void reverse();
protected:
void checkIndex(int index) const;
chainNode* headNode;
int listSize;
};
template
void chain::removeRange(int fromIndex, int toIndex)
{
checkIndex(fromIndex);checkIndex(toIndex);
if(toIndex* p = headNode;
if(fromIndex!=0)
{
chainNode* q;
for(int i = 0;inext;
else
{
q = p->next;
p->next = q->next;
delete q;
}
}
} else
{
for(int i = 0;i<=toIndex;++i)
{
headNode = headNode->next;
delete p;
p = headNode;
}
}
}
template
chain::chain(int initCapacity)
{
//chain中无capacity，这么写为了和LinearList兼容
if(initCapacity<1)
cerr << "----!initSize must be >=1 !----";
listSize = 0;
headNode = nullptr;
}
template
chain::chain(const chain & theList)
{
listSize = theList.listSize;
if(listSize==0)
{
headNode = nullptr;
return;
}
chainNode* sourceNode = theList.headNode;
headNode = new chainNode(sourceNode->element);
sourceNode = sourceNode->next;
chainNode* targetNode = headNode;
while(sourceNode!= nullptr)
{
targetNode->next = new chainNode(sourceNode->element);
sourceNode = sourceNode->next;
targetNode = targetNode->next;
}
targetNode->next = nullptr;
}
template
chain::~chain()
{
wsnippet_file_0hile(headNode!= nullptr)
{
chainNode* nextNode = headNode->next;
delete headNode;
headNode = nextNode;
}
}
template
T &chain::get(int index) const
{
checkIndex(index);
chainNode* currNode = headNode;
for(int i=0;inext;
return currNode->element;
}
template
void chain::checkIndex(int index) const
{
if(index<0 || index>=listSize)
{
cerr << "----! index outrange !----" << endl;
return;
}
}
template
int chain::indexof(const T & theElement) const
{
chainNode* currNode = headNode;
for(int i = 0;ielement==theElement)
return i;
currNode = currNode->next;
}
return -1;
}
template
void chain::erase(int index)
{
checkIndex(index);
chainNode* deleteNode;
if(index==0)
{
deleteNode = headNode;
headNode = headNode->next;
} else
{
chainNode *p = headNode;
for(int i=0;inext;
deleteNode = p->next;
p->next = p->next->next;
}
--listSize;
delete deleteNode;
}
template
void chain::insert(int index, const T &theElement)
{
if(index<0 || index>listSize)
{
cerr << "---! insert index error !----" << endl;
return;
}
if(index ==0)
{
headNode = new chainNode(theElement,headNode);
} else
{
chainNode *p = headNode;
for (int i = 0; i < index - 1; ++i)
p = p->next;
p->next = new chainNode(theElement, p->next);
}
listSize++;
}
template
void chain::output(ostream &out) const
{
for(chainNode* p = headNode;p != nullptr;p=p->next)
out << p->element << " ";
}
template
void chain::push_back(const T &theElement)
{
chainNode* currNode = headNode;
for(int i=0;inext;
currNode->next = new chainNode(theElement, nullptr);
++listSize;
}
template
void chain::clear()
{
chainNode* p;
while(headNode!= nullptr)
{
p = headNode->next;
delete headNode;
headNode = p;
}
listSize = 0;
}
template
int chain::lastIndexOf(const T& theElement)
{
int pos = -1;int i = 0;
chainNode* p = headNode;
while (p != nullptr)
{
if (p->element == theElement)
pos = i;
else
{
++i;
p = p->next;
}
}
}
template
T& chain::operator[](int index) const
{
checkIndex(index);
chainNode* currNode = headNode;
for(int i = 0;inext;
return currNode->element;
}
template
void chain::reverse()
{
if(listSize==0 || listSize==1)
return;
else if(listSize == 2)
{
chainNode* p = headNode;
headNode = headNode->next;
headNode->next = p;
p->next = nullptr;
}
else
{
chainNode* p = headNode;
chainNode* q = headNode->next;
chainNode* r = headNode->next->next;
headNode->next = nullptr;
while(r->next != nullptr)
{
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
r->next = q;
headNode = r;
}
}
template
ostream& operator<<(ostream& out, const chain &a)
{
a.output(out);
return out;
}
#endif //INC_02_CHAIN_CHAIN_H
随便写的测试：
#include <iostream>
#include "chain.h"
int main()
{
chain<int> ic;
ic.insert(0,1);ic.insert(0,2);ic.push_back(3);ic.push_back(4);
chain<int> ic1(ic);ic1.reverse();
cout << ic1 << endl;
return 0;
}
我发现写这个还是很锻炼人的，一个完善的数据结构轻轻松松几百行代码，每天一发，感觉很酸爽，C++简直写上瘾。
不废话了，我们回归头来看看链表的头文件里都定义了啥：
– chainNode类定义了节点类，包含数据成员以及指向下一个节点的指针。包含构造、拷贝以及析构函数。
– chan类继承自LinearList抽象类，包含节点类的成员变量，以及一个嵌套类iterator。
成员函数分为几个部分，首先是构造、拷贝以及析构函数，值得注意的是在构造函数中有一个参数
initCapacity,实际是无作用的，仅仅为了和之前的ArrayList一致。
– 然后是继承自抽象类的方法，和ArrayList中的区别不大。
– 最后是我做的几个习题，void removeRange(int fromIndex,int toIndex)的作用是将参数限定范围内的节点删除的操作。int lastIndexOf(const T& theElement)是返回与函数参数相等的最后一个位置的索引。T& operator[](int index) const 是对[]运算符进行重载，返回指定索引的节点的数据的引用。void reverse()是将整个链表进行反转的操作，要求不开辟多余的空间。