Thread: 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.

Why make an empty list contain one node?

I will try to solve this problem.

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?

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?

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?

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
};

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.

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.

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;
    };

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?

Originally Posted by siavoshkc

You mean structs can hold functions and have this pointer?

Yes, and a union can as well.

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.

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

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;
}