/*
* 節(jié)點(diǎn)類型。三個(gè)成員分別是：指向前一個(gè)節(jié)點(diǎn)的指針，元素本身，指向后一個(gè)節(jié)點(diǎn)的指針。
*/
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 <iostream>
using std::cout;
/*
* 構(gòu)造方法。
* 生成一個(gè)空的節(jié)點(diǎn)介于表頭和表尾之間，初始前后指針都指向自己。
*/
LinkedList::LinkedList() {
    header = new Node(NULL, NULL, NULL);
    header->next = header;
    header->previous = header;
    size = 0;
}
/*
* 在鏈表頭部添加一個(gè)元素。
* 生成一個(gè)新的節(jié)點(diǎn)，向前指向空節(jié)點(diǎn)，向后指向原來空節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即原來的第一個(gè)節(jié)點(diǎn)。
* 空節(jié)點(diǎn)向后指向此節(jié)點(diǎn)，原來的第一個(gè)節(jié)點(diǎn)向前指向此節(jié)點(diǎn)。
*/
void LinkedList::addFirst(int i) {
    header->next = new Node(i, header->next, header);
    header->next->next->previous = header->next;
    ++size;
}
/*
* 在鏈表最后添加一個(gè)元素。
* 生成一個(gè)新的節(jié)點(diǎn)，向前指向原來空節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，即原來的最后一個(gè)節(jié)點(diǎn)，向后指向空節(jié)點(diǎn)。
* 原來的最后一個(gè)節(jié)點(diǎn)向后指向此節(jié)點(diǎn)，空節(jié)點(diǎn)向前指向此節(jié)點(diǎn)。
*/
void LinkedList::addLast(int i) {
    header->previous = new Node(i, header, header->previous);
    header->previous->previous->next = header->previous;
    ++size;
}
/*
* 在指定的索引前插入一個(gè)元素。0 <= 索引 <= 鏈表長度。
* 如果索引值小于鏈表長度的一半，向后（正向）迭代獲取索引值位置的節(jié)點(diǎn)，反之則向前（反向）。
* 生成一個(gè)新的節(jié)點(diǎn)，向前指向原來這個(gè)位置的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，向后指向原來這個(gè)位置的節(jié)點(diǎn)。
* 原來這個(gè)位置的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)向后指向此節(jié)點(diǎn)，原來這個(gè)位置的節(jié)點(diǎn)向前指向此節(jié)點(diǎn)。
* （在指定的索引刪除一個(gè)元素實(shí)現(xiàn)方法類似）
*/
void LinkedList::add(int index, int i) {
    if(index > size || index < 0) {
        cout << "Exception in add(): Index out of bound." << '\n';
    return;
    }
    Node *entry;
    if(index < size / 2) {
        entry = header->next;
        for(int i = 0; i < index; ++i)
            entry = entry->next;
    }
    else {
        entry = header;
        for(int i = size; i > index; --i)
            entry = entry->previous;
    }
    entry->previous->next = new Node(i, entry, entry->previous);
    entry->previous = entry->previous->next;
    ++size;
}
/*
* 獲取鏈表第一個(gè)元素。
* 空節(jié)點(diǎn)向后指向的節(jié)點(diǎn)即是第一個(gè)元素。
*/
int LinkedList::getFirst() {
    if(!size)
        cout << "Exception in getFirst(): List is empty." << '\n';
    return header->next->element;
}
/*
* 獲取鏈表最后一個(gè)元素。
* 空節(jié)點(diǎn)向前指向的節(jié)點(diǎn)即是最后一個(gè)元素。
*/
int LinkedList::getLast() {
    if(!size)
        cout << "Exception in getLast(): List is empty." << '\n';
    return header->previous->element;
}
/*
* 刪除并返回鏈表第一個(gè)元素。
* 鏈表第二個(gè)節(jié)點(diǎn)向前指向空節(jié)點(diǎn)，空節(jié)點(diǎn)向后指向第二個(gè)節(jié)點(diǎn)。
*/
int LinkedList::removeFirst() {
    int remove = header->next->element;
    header->next->next->previous = header;
    header->next = header->next->next;
    --size;
    return remove;
}
/*
* 刪除并返回鏈表最后一個(gè)元素。
* 鏈表倒數(shù)第二個(gè)節(jié)點(diǎn)向后指向空節(jié)點(diǎn)，空節(jié)點(diǎn)向前指向倒數(shù)第二個(gè)節(jié)點(diǎn)。
*/
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 << "Exception in iterate(): List is empty." << '\n';
        return;
    }
    for(Node *entry = header->next; entry != header; entry = entry->next)
        cout << entry->element << " ";
    cout << '\n';
}