Another Linked List

Just tell me your ideas about it.

LL.h is:

Code:

---

struct Node{
        int val;
        Node *next;
};


class LL{
public:
        LL();
        void PushFront(int aVal);
        void PushBack(int aVal);
        int PopFront();
        int PopBack();
        int ReadFront() const;
        int ReadBack() const;
        bool IsEmpty();
        ~LL();
private:
        Node *back;
        Node *front;
};

---

LL.cpp is:

Code:

---

#include "LL.h"
#include "stdafx.h"


LL::LL()
{
        front = back = new Node;
}

void LL::PushFront(int aVal)
{
        front->next = new Node;
        front = front->next;
        front->val = aVal;       
}

void LL::PushBack(int aVal)
{
        Node *t;
        back->val = aVal;
        t = new Node;
        t->next = back;
        back = t;
}

int LL::PopFront()
{       
        int temp = front->val;
        delete front;
        Node* it = back;
        while(it->next  != front) it = it->next;
        front = it;
        return temp;
}

int LL::PopBack()
{
        int temp = back->next->val;
        Node *it = back->next;
        delete back;
        back = it;
        return temp;

}

int LL::ReadFront() const
{
        return front->val;
}

int LL::ReadBack() const
{
        return back->val;
}

bool LL::IsEmpty()
{
        return (back == front);
}

LL::~LL()
{
        while(back != front)
        {
                Node *temp = back->next;
                delete back;
                back = temp;
        }
        delete front;

}

---

stdafx.h is:

Code:

---

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//

#pragma once


#define WIN32_LEAN_AND_MEAN                // Exclude rarely-used stuff from Windows headers
#include <stdio.h>
#include <windows.h>
#include <list>
#include <iostream>
#include "LL.h"
using namespace std;

---

And there is test program that runs only on Windows.

Code:

---


#include "stdafx.h"


int main(int argc, char* argv[])
{

        using namespace std;
        LL ll;
        list <int> v;
        LARGE_INTEGER fp, fp2;
       
        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                ll.PushFront(i);
        QueryPerformanceCounter(&fp2 );
        cout  <<"PushFront: "<< fp2.LowPart - fp.LowPart << endl;

        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                v.push_front(i);
        QueryPerformanceCounter(&fp2 );
        cout  <<"push_front: "<< fp2.LowPart - fp.LowPart << endl;

        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                ll.PushBack(i);
        QueryPerformanceCounter(&fp2 );
        cout  <<"PushBack: "<< fp2.LowPart - fp.LowPart << endl;

        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                v.push_back(i);
        QueryPerformanceCounter(&fp2 );
        cout  <<"push_back: "<< fp2.LowPart - fp.LowPart << endl;

        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                ll.PopFront();
        QueryPerformanceCounter(&fp2 );
        cout  <<"PopFront: "<< fp2.LowPart - fp.LowPart << endl;

        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                v.pop_front();
        QueryPerformanceCounter(&fp2 );
        cout  <<"pop_front: "<< fp2.LowPart - fp.LowPart << endl;
       
        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                ll.PopBack();
        QueryPerformanceCounter(&fp2 );
        cout  <<"PopBack: "<< fp2.LowPart - fp.LowPart << endl;

        QueryPerformanceCounter(&fp );
        for(int i = 0 ; i < 1000 ; i++)
                v.pop_back();
        QueryPerformanceCounter(&fp2 );
        cout  <<"pop_back: "<< fp2.LowPart - fp.LowPart << endl;



        return 0;
}

---

Since Node is an implementation detail of LL, I would make it a private datatype of LL.

Code:

---

class LL
{
/* stuff */
private:
    struct Node
    {
        int val;
        Node *next;
    };

    Node *back;
    Node *front;
};

---

Yeah thats a good idea.

You've reversed the terms 'back' and 'front'. Best switch the names back around.
Then, you should drop PopBack altogether. It does not make sense for the container to implement this because it is only a singly-linked-list, making the operation O(n). Thats not good considering the interface to this class does not make that obvious.
Just remove the function with the loop and call the container a deque or slist instead.

You should find an implementation of an slist class if you want to do more meaningful speed tests. std::list is doubly-linked and therefore have bidirectional access, so this is not an apples-to-apples test.

Some more food for thought:

Why make an empty list contain one node?

Are you supposed to be able to screw up your list entirely by using PopBack/Front one too many times? Needs more robustness.

You could be more thorough with your usage of const. IsEmpty for instance.

Wouldn't a constructor for Node be useful as well? It would probably simplify things a bit.

Why would you not make it a template class?

What are the exception guarantees on your class? What about thread saftey?

btw, You can still use an initialiser list for LL, just not for both member variables if you're going to assign them a dummy node.

Thank you iMalc. I switched the terms and added const to IsEmpty(). I changed the class name to SList.

Quote:

---

Why make an empty list contain one node?

---

I will try to solve this problem.

Quote:

---

Are you supposed to be able to screw up your list entirely by using PopBack/Front one too many times? Needs more robustness.

---

Why? I think they are fast routines. Aren't they?

Quote:

---

Wouldn't a constructor for Node be useful as well? It would probably simplify things a bit.

---

How can a struct has a constructor? You may mean making a class for Node. Don't you?

Quote:

---

You can still use an initialiser list for LL, just not for both member variables if you're going to assign them a dummy node.

---

What initialiser list?

Quote:

---

How can a struct has a constructor? You may mean making a class for Node. Don't you?

---

In C++ the only difference between struct and class is the default visibility level. If you use private and public keywords to set visibility yourself, they are equivalent. Except that structs are conventionally used just for storing public related data without member functions, but a constructor is still useful to initialize the data nicely.

Code:

---

class A
{
    //defaults to private
};
struct B
{
    //defaults to public
};

---

Quote:

---

Originally Posted by siavoshkc

Thank you iMalc. I switched the terms and added const to IsEmpty(). I changed the class name to SList.

I will try to solve this problem.

---

Okay, you're main options are using NULL at the end (and possibly doing extra work for certain cases), or using a statically declared node as a sentinel.

Quote:

---

Why? I think they are fast routines. Aren't they?

---

They are certainly pretty low on instruction counts I'd say. And if speed is by far your primary goal, then I'd suggest simply adding comments or whatever to document the behaviour in special cases such as an empty list. If your goals are somewhat more user-friendly, then you'd be better to make the functions cope with it.

Quote:

---

How can a struct has a constructor? You may mean making a class for Node. Don't you?

---

anon has it right. struct and class are almost exactly the same in C++. structs have public members by default, classes have private by default. I was suggesting something like this:

Code:

---

    struct Node
    {
        Node (int val, Node *next) : val(val), next(next) {}
        int val;
        Node *next;
    };

---

Quote:

---

What initialiser list?

---

The constructor I added just used a "constructor inisialization list"
http://www.google.com/search?hl=en&q...+list%22&meta=

I was thinking something along the lines of:

Code:

---

LL::LL() : front(new Node)
{
        back = front;
}

---

Not a hell of a lot of advantage in this case though.

You mean structs can hold functions and have this pointer?

Quote:

---

Originally Posted by siavoshkc

You mean structs can hold functions and have this pointer?

---

Yes, and a union can as well.

Quote:

---

Originally Posted by siavoshkc

You mean structs can hold functions and have this pointer?

---

In C++, a class and a struct are technically exactly the same thing, with the caveat that a struct defaults to 'public' as its access specifier, and a class defaults to 'private'

About structs:
Strange, I didn't know that (or maybe forgotten!).

I used constructor inisialization list (I didn't know such thing even exists, maybe because I am in the middle of the book):

Code:

---

SList::SList()
{
        back = front = new Node(516, NULL);
}

void SList::PushBack(int aVal)
{
        back->next = new Node(aVal, NULL);
        back = back->next;
}

void SList::PushFront(int aVal)
{
        front->val = aVal;
        front = new Node(0, front);
}

int SList::PopBack()
{       
        int temp = back->val;
        delete back;
        Node* it = front;
        while(it->next != back) it = it->next;
        back = it;
        return temp;
}

int SList::PopFront()
{
        int temp = front->next->val;
        Node *it = front->next;
        delete front;
        front = it;
        return temp;

}

int SList::ReadBack() const
{
        return back->val;
}

int SList::ReadFront() const
{
        return front->val;
}

bool SList::IsEmpty() const
{
        return (front == back);
}

SList::~SList()
{
        while(front != back)
        {
                Node *temp = front->next;
                delete front;
                front = temp;
        }
        delete back;

}

---

I didn't place any condition in routines. I think it speeds up operations a lot. But I can't avoid using one dummy Node.

You don't need a dummy node, Your last node should always point to null - this is enough information to be able to tell when you are at the end of your list. In the special case when the list is empty, your 'front' and 'back' pointers will be null. You will need to test for the special case, so that you can update these accordingly, when push'ing or pop'ing nodes.

here's a quick example which has no need for a dummy node

Code:

---

#include <iostream>

class linked
{
    struct node
    {
        int data;
        node* next;
        node(int i, node * n) : data(i), next(n) {}
    };
    node* head;
public:
    linked() : head(NULL) {}
    bool is_empty() { return !head; }
    void push_front(int);
    int pop_front();
    ~linked()
    {
        while( head )
        {
            node* temp(head);
            head = head->next;
            delete temp;
        }
    }
};

void linked::push_front(int i)
{
    head = new node(i, head);
}

int linked::pop_front()
{
    if(!head)
        throw("Error: List empty");
    int data( head->data );
    node* temp(head);
    head = head->next;
    delete temp;
    return data;
}

int main()
{
    linked list;
    list.push_front(5);
    list.push_front(32);
    list.push_front(-234);
    while( ! list.is_empty() )
        std::cout << list.pop_front() << ' ' ;
}

---

I should emphasize that there should be no branching in routines.

Quote:

---

Originally Posted by siavoshkc

I should emphasize that there should be no branching in routines.

---

To what purpose? Conditional statements don't impact performance in the way you seem to think they do. Although, somewhere along the line you have to deal with special cases - whether it be a null pointer, or a dummy node.

Quote:

---

Conditional statements don't impact performance in the way you seem to think they do.

---

They have notable performance impact. I think 4 byte of memory costs less than their impact.

I added some functionalities:

Code:

---

//High speed singly linked list
//There is no error control in routines, use them carefully
class SList{
public:
        SList();
        void PushFront(int aVal);  //A--->O--->O
        void PushBack(int aVal);        //O--->O--->A
        int PopFront();                //X--->O--->O       
        int PopBack();                //O--->O--->X       
        int ReadFront() const;        //R--->O--->O
        int ReadBack() const;        //O--->O--->R
        unsigned int CountItems() const;
        int operator[] (unsigned int) const;        //Acts like array
        void DeleteItem(unsigned int);
        bool IsEmpty() const;                //Returns true if list is empty
        ~SList();                                //Frees allocated memory
private:
        struct Node{
                Node(int val,Node* next) : val(val), next(next) {}; //Each node keeps a value and an address of another node
                int val;
                Node *next;
        };
        Node *back;                //O--->O--->>O<<
        Node *front;        //>>O<<--->O--->O
};

---

CPP:

Code:

---

#include "SList.h"
#include "stdafx.h"


SList::SList()
{
        back = front = new Node(516, NULL);
}

void SList::PushBack(int aVal)
{
        back->next = new Node(aVal, NULL);
        back = back->next;
}

void SList::PushFront(int aVal)
{
        front->val = aVal;
        front = new Node(0, front);
}

int SList::PopBack()
{       
        int temp = back->val;
        delete back;
        Node* it = front;
        while(it->next != back) it = it->next;
        back = it;
        return temp;
}

int SList::PopFront()
{
        int temp = front->next->val;
        Node *it = front->next;
        delete front;
        front = it;
        return temp;
}

int SList::ReadBack() const
{
        return back->val;
}

int SList::ReadFront() const
{
        return front->val;
}

bool SList::IsEmpty() const
{
        return (front == back);
}

unsigned int SList::CountItems() const
{
        Node* tItem = front;
        unsigned int count = 0;
        while(tItem != back)
        {
                count++;
                tItem = tItem->next;
        }
        return count;
}

int SList::operator[] (unsigned int idx) const
{
        Node* tItem = front;
        for(unsigned int i = 0; i <= idx; ++i)  tItem = tItem->next;
        return tItem->val;
}

void SList::DeleteItem(unsigned int idx)
{
        Node* pItem = front;
        for(unsigned int i = 1; i <= idx; ++i)  pItem = pItem->next;
        Node* dItem = pItem->next;
        pItem->next = dItem->next;
        delete dItem;
}
SList::~SList()
{
        while(front != back)
        {
                Node *temp = front->next;
                delete front;
                front = temp;
        }
        delete back;
}

---

Quote:

---

Originally Posted by siavoshkc

They have notable performance impact.

---

Justify this claim or stop making it.

Though condition performance impact is not something new, I opened a new thread for it as it not relevant to list.

Nice usage of the Node constructor!

I consider the function PopBack and the [] operator for this class fundamentally wrong.
If the purpose of this class is speed, as evidenced by not wanting a branch statement, providing O(n) operations is far worse than a single if statement.
These two things conflict and contradict in a major way. There's a reason that the standard C++ library doesn't provide an [] operator for a list container.
Furthurmore, where a [] operator is supplied (and it shouldn't be here), it really needs to have a const and non-const version.

You could say that insertion and deletion from the middle are perhaps a necessary O(n) evil, when it comes to a singly-linked list. But I would perhaps still discourage the user of your class from doing such things by forcing them to have to implement these themselves if they so insist.

Quote:

---

Quote:

---

Conditional statements don't impact performance in the way you seem to think they do.

---

They have notable performance impact. I think 4 byte of memory costs less than their impact.

---

Firstly, it's not 4 bytes, it's the size of a node which is the size of a pointer plus the size of an int. 8 bytes on a standard PC.
Secondly, this is not a straight out "trade and in statement for 8 bytes" here because using an if-statement prevents users from screwing up the list via one too many pops, but the extra node does not.
Thirdly, in a number of circumstances, the lack of this saftey 'if statment' will cause the code using the class to need to implement this 'if statement' instead. At the very least that's a little unnecessary code bloat for something that should be only in one place.

I know you're having fun with this and are learning a lot, but be careful not to make the mistake many people make in assuming that they can design and write a better linked-list than a committee of experts can.

This list is only for practice. It may not be used anywhere. We consider that code using the class is carefully written and will not Pop more than its Push or at least has checks where it is needed. So it is not a important case for me. Of course for a practical program I would use standard library. But that 8 byte of dummy Node (4 of it is completely wasted) is the thing that bothers me.

Quote:

---

I consider the function PopBack and the [] operator for this class fundamentally wrong.

---

When user needs random access she/he should not use linked list. OK. But I am not sure if I should implement the code for it or not. If I do user can decide whether to use them or not. We can note the O(n) in header file.