Another Linked List

This is a discussion on Another Linked List within the C++ Programming forums, part of the General Programming Boards category; Just tell me your ideas about it. LL.h is: Code: struct Node{ int val; Node *next; }; class LL{ public: ...

  1. #1
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231

    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;
    }
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  2. #2
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    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;
    };
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  3. #3
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    Yeah thats a good idea.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    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.
    Last edited by iMalc; 07-18-2007 at 12:01 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    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?
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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
    };
    Last edited by anon; 07-18-2007 at 02:52 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    Quote Originally Posted by siavoshkc View Post
    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.
    Last edited by iMalc; 07-18-2007 at 03:45 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    You mean structs can hold functions and have this pointer?
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  9. #9
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    Quote Originally Posted by siavoshkc View Post
    You mean structs can hold functions and have this pointer?
    Yes, and a union can as well.
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  10. #10
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by siavoshkc View Post
    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'

  11. #11
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    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.
    Last edited by siavoshkc; 07-18-2007 at 02:24 PM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  12. #12
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    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() << ' ' ;
    }

  13. #13
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    I should emphasize that there should be no branching in routines.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  14. #14
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by siavoshkc View Post
    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.

  15. #15
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    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;
    }
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21