LinkedList.cpp

#include "LinkedList.h"


LinkedList::LinkedList()
{
    start = end = NULL;
    size = 0;
}


LinkedList::~LinkedList()
{
    while (start != NULL){
        node* n = start;
        start = start->next;
        delete n;
    }
}

ostream& operator<<(ostream& out, const LinkedList& l){
    LinkedList::node* s = l.start;
    out << "[";
    if (s == NULL){
        out << "]";
        return out;
    }
    while (s->next != NULL){
        out << s->x << ",";
        s = s->next;
    }
    out << s->x << "]";
    return out;
}

int LinkedList::push(int x){
    if (end != NULL){
        node* n = new node;
        n->x = x;
        n->next = NULL;
        n->prev = end;
        end->next = n;
        end = n;
    }
    else{
        node* n = new node;
        n->x = x;
        n->next = NULL;
        n->prev = NULL;
        start = end = n;
    }
    /*cout << "start, end = " << start << "," << end << endl;
    if (start!=NULL)
        cout << "startx = " << start->x;
    if (end != NULL)
        cout << ", endx = " << end->x << endl;
    else
        cout << endl;*/
    return ++size;
}
int LinkedList::pop(){
    if (size == 0)
        return NULL;
    if (size == 1){
        int n = end->x;
        delete end;
        end = start = NULL;
        size--;
        return n;
    }
    int n = end->x;
    node* tmp = end;
    end = end->prev;
    size--;
    delete tmp;
    end->next = NULL;
    return n;
}
int LinkedList::unshift(int x){
    if (end != NULL){
        node* n = new node;
        n->x = x;
        n->next = start;
        n->prev = NULL;
        start->prev = n;
        start = n;
    }
    else{
        node* n = new node;
        n->x = x;
        n->next = NULL;
        n->prev = NULL;
        start = end = n;
    }
    return ++size;
}
int LinkedList::shift(){
    if (size == 0)
        return NULL;
    if (size == 1){
        int n = end->x;
        delete end;
        end = start = NULL;
        size--;
        return n;
    }
    int n = start->x;
    node* tmp = start;
    start = start->next;
    size--;
    delete tmp;
    start->prev = NULL;
    return n;
}

int LinkedList::find(int x){
    int r = 0;
    node* s = start;
    while (s != NULL){
        if (s->x == x){
            return r;
        }
        r++;
        s = s->next;
    }
    return -1;
}
LinkedList* LinkedList::copy(int s, int e){
    LinkedList* r = new LinkedList;
    int i = 0;
    node* st = start;
    while (st != NULL && i < s){
        st = st->next;
        i++;
    }
    if (st == NULL)
        return r;
    while (st != NULL && i < e){
        r->push(st->x);
        st = st->next;
        i++;
    }
    return r;
}
LinkedList* LinkedList::splice(int s, int e){
    LinkedList* r = new LinkedList;
    int i = 0;
    node* st = start;
    while (st != NULL && i < s){
        st = st->next;
        i++;
    }
    if (st == NULL)
        return r;
    node* tm = st;
    while (st != NULL && i < e){
        r->push(st->x);
        node* tmp = st;
        if (st == start){
            start = st = st->next;
            delete tmp;
            start->prev = NULL;
        }
        else if (st == end){
            node* tn = st->prev;
            st = NULL;
            delete tmp;
            tn->next = NULL;
        }
        else{
            st->next->prev = st->prev;
            st->prev->next = st->next;
            st = st->next;
            delete tmp;
        }
        i++;
        size--;
    }
    return r;
}

LinkedList::node* LinkedList::_sort(node* r, int n){ //return the first node
    if (n == 0)
        return NULL;
    if (n == 1)
        return r;
    if (n == 2){
        if (r->x > r->next->x)
            _swap(r, r->next);
        return r;
    }

    bool s1 = true, s2 = true;
    int i = 0;
    node *tr = r, *f, *p;
    while (i<(n - 1) / 2){
        if (tr->x > tr->next->x)
            s1 = false;
        tr = tr->next;
        i++;
    }
    tr = tr->next;
    i++;
    int ti = i;
    node* r2 = tr;
    while (ti<n - 1){
        if (tr->x > tr->next->x){
            s2 = false;
            break;
        }
        tr = tr->next;
        ti++;
    }
    if (!s1)
        r = _sort(r, i);
    if (!s2)
        r2 = _sort(r2, n - i);

    node* first = r;
    f = r;
    p = r2->prev;

    ti = i;
    int k = 0;
    while (i < n && k<ti){
        if (r->x > r2->x){
            p->next = r2->next;
            if (r2->next != NULL)
                r2->next->prev = p;
            r2->next = r;
            r2->prev = r->prev;
            r->prev = r2;

            if (f != r){
                f->next = r2;
                f = f->next;
            }
            else{
                first = r2;
                f = r2;
            }
            r2 = p->next;
            i++;
        }
        else{
            if (r != f)
                f = f->next;
            r = r->next;
            k++;
        }
    }
    return first;
}