list

#include <iostream>
using namespace std;

template <class T> class List;

template<class T>
class Node
 {
    T data;
    Node<T> * next, * prev;
 public:
    Node(const T & d, Node<T> * n = 0, Node<T> * p = 0);
    ~Node();

    void setData(const T & d){data = d;};
    void setNext(Node<T> * n){next = n; if (n != 0) n->prev = this;};
    void setPrev(Node<T> * n){prev = n; if (n != 0) n->next = this;};

    T getData() const {return data;};
    Node<T> * getNext() const {return next;};
    Node<T> * getPrev() const {return prev;};

    friend List<T>;
 };

 template <class T>
 class List
 {
    Node<T> * head, * tail;

    int increment(long inc[], long size);
 public:
    List(){head = 0; tail = 0;};
    ~List();
    void show() const;
    void addFront(const T & d);
    void addBack(const T & d);
    Node<T> * cutFront();
    Node<T> * cutBack();
    void delFront(){delete cutFront();};
    void delBack(){delete cutBack();};

    int size() const;
    Node<T> * getHead() const {return head;};
    Node<T> * getTail() const {return tail;};
    Node<T> * get(int) const;
    Node<T> * operator [](int i) const {return get(i);};
    void shellSort();
 };

 int main()
 {
    List<int> l;
    for(int i = 0; i < 10; l.addFront(i++));
    l.show();
    l.shellSort();
    l.show();
 }

template <class T>
int List<T>::increment(long inc[], long N)
{
  int p1, p2, p3, s;

  p1 = p2 = p3 = 1;
  s = -1;
  do
  {
        if (++s % 2)
            inc[s] = 8*p1 - 6*p2 + 1;
    else
    {
      inc[s] = 9*p1 - 9*p3 + 1;
      p2 *= 2;
      p3 *= 2;
    }
        p1 *= 2;
  } while (3*inc[s] < N);

  return s > 0 ? --s : 0;
}

template<class T>
void List<T>::shellSort()
{
  long k, i, j, seq[40], N = size();
  int s;

  // вычисление последовательности приращений
  s = increment(seq, N);
  while (s >= 0) {
    // сортировка вставками с инкрементами inc[]
    k = seq[s--];

    for (i = k; i < N; i++) {
      T temp = get(i) -> data;
      for (j = i-k; (j >= 0) && (get(j) -> data > temp); j -= k)
        get(j+k) -> setData(get(j) -> getData());
      get(j+k) -> setData(temp);
    }
  }
}

 template<class T>
 Node<T>::Node(const T & d, Node<T> * n, Node<T> * p)
 {
    data = d;

    next = n;
    if (n != 0)
        n -> prev = this;

    prev = p;
    if(p != 0)
        p -> next = this;
 }

 template<class T>
 Node<T>::~Node()
 {
//  cout << "Node destructor start"<< endl;

    if (next != 0)
    {
//      cout << "Node destructor: next" << endl;
        Node<T> * temp = next;
        next = 0;
        temp -> prev = 0;
        delete temp;
    }

//  cout << "Node destructor continue" << endl;

    if (prev != 0)
    {
//      cout << "Node destructor: prev" << endl;
        Node<T> * temp = prev;
        prev = 0;
        temp -> next = 0;
        delete temp;
    }

//  cout << "Node destructor final" << endl;
 }

template <class T>
int List<T>::size() const
{
    Node<T> * node = head;
    int count = 0;
    while (node != 0)
    {
        node = node -> next;
        ++count;
    }
    return count;
}
template <class T>
Node<T> * List<T>::get(int i) const
{
    if (i < 0) i = 0;
    Node<T> * node = head;
    for(int j = 0; j < i && node -> next != 0; ++j)
        node = node -> next;
    return node;
}

template <class T>
void List<T>::show() const
{
    for (Node<T> * node = head; node != 0; node = node -> next)
        cout << node -> data << " ";
    cout << endl;
}

template <class T>
List<T>::~List()
{
//  cout << "List destructor start" << endl;

    if (head != 0){
//      cout << "List destructor: head" << endl;
        Node<T> * temp = head;
        head = 0;
        delete temp;
    }

//  cout << "List destructor continue" << endl;

    if (tail != 0)
    {
//      cout << "List destructor: tail" << endl;
        Node<T> * temp = tail;
        tail = 0;
        delete temp;
    }

//  cout << "List destructor final" << endl;
}

template<class T>
void List<T>::addFront(const T & d)
{
    head = new Node<T>(d, head, 0);
    if (tail == 0)
        tail = head;
}

template<class T>
void List<T>::addBack(const T & d)
{
    tail = new Node<T>(d, 0, tail);
    if (head == 0)
        head = tail;
}


template<class T>
Node<T> * List<T>::cutFront()
{
    Node<T> * node = head;
    if (node != 0)
    {
        head = head -> next;
        node -> next = 0;
        head -> prev = 0;
    }
    return node;
}

template<class T>
Node<T> * List<T>::cutBack()
{
    Node<T> * node = tail;
    if (node != 0)
    {
        tail = tail -> prev;
        node -> prev = 0;
        tail -> next = 0;
    }
    return node;
}