单向链表：基本链表；
单向循环链表：不同于单向链表以 NULL 判断链表的尾部，单向循环链表的尾部链接到表头，因此当迭代操作到表头前即是尾部；
双向链表：比单向链表多出指向前一个节点的指针，但实际上使用双向链表时很少使用不循环的；
双向循环链表：相对于单向循环链表，双向循环链表可从头部反向迭代，这在链表长度很大且需要获取、插入或删除靠近链表尾部元素的时候十分高效。单向循环列表只能从表头正向迭代，执行的时间大于从反向迭代。
node.h
代码如下:
/*
* 节点类型。三个成员分别是：指向前一个节点的指针，元素本身，指向后一个节点的指针。
*/
class Node {
public:
int element;
Node *next;
Node *previous;
Node(int element, Node *next, Node *previous) {
this->element = element;
this->next = next;
this->previous = previous;
}
};
linkedlist.h:
#include "node.h“
struct LinkedList {
LinkedList();
void addFirst(int);
void addLast(int);
void add(int index, int element);
int getFirst();
int getLast();
int get(int);
int removeFirst();
int removeLast();
int remove(int);
void iterate();
private:
Node *header;
int size;
};
linkedlist.cpp:
#include "linkedlist.h"
#include
using std::cout;
/*
* 构造方法。
* 生成一个空的节点介于表头和表尾之间，初始前后指针都指向自己。
*/
LinkedList::LinkedList() {
header = new Node(NULL, NULL, NULL);
header->next = header;
header->previous = header;
size = 0;
}
/*
* 在链表头部添加一个元素。
* 生成一个新的节点，向前指向空节点，向后指向原来空节点的下一个节点，即原来的第一个节点。
* 空节点向后指向此节点，原来的第一个节点向前指向此节点。
*/
void LinkedList::addFirst(int i) {
header->next = new Node(i, header->next, header);
header->next->next->previous = header->next;
++size;
}
/*
* 在链表最后添加一个元素。
* 生成一个新的节点，向前指向原来空节点的前一个节点，即原来的最后一个节点，向后指向空节点。
* 原来的最后一个节点向后指向此节点，空节点向前指向此节点。
*/
void LinkedList::addLast(int i) {
header->previous = new Node(i, header, header->previous);
header->previous->previous->next = header->previous;
++size;
}
/*
* 在指定的索引前插入一个元素。0 index; --i)
entry = entry->previous;
}
entry->previous->next = new Node(i, entry, entry->previous);
entry->previous = entry->previous->next;
++size;
}
/*
* 获取链表第一个元素。
* 空节点向后指向的节点即是第一个元素。
*/
int LinkedList::getFirst() {
if(!size)
cout element;
}
/*
* 获取链表最后一个元素。
* 空节点向前指向的节点即是最后一个元素。
*/
int LinkedList::getLast() {
if(!size)
cout element;
}
/*
* 删除并返回链表第一个元素。
* 链表第二个节点向前指向空节点，空节点向后指向第二个节点。
*/
int LinkedList::removeFirst() {
int remove = header->next->element;
header->next->next->previous = header;
header->next = header->next->next;
--size;
return remove;
}
/*
* 删除并返回链表最后一个元素。
* 链表倒数第二个节点向后指向空节点，空节点向前指向倒数第二个节点。
*/
int LinkedList::removeLast() {
int remove = header->previous->element;
header->previous->previous->next = header;
header->previous = header->previous->previous;
--size;
return remove;
}
/*
* 用来输出所有元素的迭代方法。
*/
void LinkedList::iterate() {
if(!size) {
cout next)
cout element