list

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>

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()
{
    srand(time(0));
//  Creating English alphabet:
    string alp;
    for(char ch = 'A'-1; ch++ < 'Z'; alp += ch);

//  Creating List of random strings length 3-4:
    List<string> l;
    int a = 3, b = 4, N = 10;
    for(int i = 0; i < N; ++i)
    {
        string temp;
        for(int j = 0, l = rand()%(b-a+1)+a; j < l; ++j)
            temp = temp + alp[rand() % alp.length()];
        l.addFront(temp);
    }

    cout << "Before shellSort: ";
    l.show();

//  Sorting:
    l.shellSort();

    cout << " After 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 = increment(seq, N);
    while (s >= 0)
    {
        for (i = k = seq[s--]; 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;
    prev = p;

    if (n != 0) n->prev = this;
    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;
        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;
}