linked lists vs vectors

Build a list using linked list would vectors been better

Page 1 of 1

7 Replies - 3149 Views - Last Post: 07 May 2009 - 03:57 PM Rate Topic: -----

#1 isuckatC++  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 04-May 09

linked lists vs vectors

Posted 07 May 2009 - 10:48 AM

This was meant to be a car hire system and the more i continue with it, the more i feel that vectors would have been better to use (as there seems to be alot more things u can do with the list of objects). Just wondering i haven't used vectors yet so i don't really know much about them. So would be nice to hear ppl's thoughts on them.

well heres the code
main.cpp

#include <cstdlib>
#include <iostream>
#include <string>
#include "hire.h"

using namespace std;

class node
  {  
  public:
	 string make;	// Name of up to 20 letters
	 string model;		  // D.O.B. would be better
	 int milage;	 // In metres
	 string registration;
	 node *nxt;		// Pointer to next node
  };
void set_hire_milage_charge();

int main(int argc, char *argv[])
{
node *start_ptr = NULL;
int num,user_input = 0;
cout << "\n1:Set daily hire charge and milage charge\n";
cout << "2:Add new car to fleet\n";
cout << "3:Remove car\n";
cout << "4:Hire out car to customer\n";
cout << "5:Car returned by Customer\n";
cout << "6:Produce list of all cars\n";
cout << "7:Close Program\n";

cout << "\nPlease Make a Selection between 1-7\n";	
 
do
{
cin >> user_input;

switch(user_input)
	{
	case 1:
////////////////// Set daily hire charge and milage charge ////////////////////
	set_hire_milage_charge();
	break;
	case 2:
//////////////////////////// ADD CARS TO FLEET //////////////////////////////// 
cout << "Please enter number of cars added to fleet: ";
cin >> num;
node *lastnode, *previousnode;
  for(int x=0; x<num;x++)
  {		  
	 // Temporary pointers
	 cout << "\nCar: " << x+1 << endl;
	 // Reserve space for new node and fill it with data
	 lastnode = new node;
	 cout << "Please enter make of the car: ";
	 cin >> lastnode->make;
	 cout << "Please enter model of the car: ";
	 cin >> lastnode->model;
	 cout << "Please enter the milage of the car: ";
	 cin >> lastnode->milage;
	 cout << "Please enter the milage of the car: ";
	 cin >> lastnode->registration;  
	 cout << " ";
	 lastnode->nxt = NULL;

	 // Set up link to this node
	 if (start_ptr == NULL)
		 start_ptr = lastnode;
	 else
	   { previousnode = start_ptr;
		 // We know this is not NULL - list not empty!
		 while (previousnode->nxt != NULL)
		   {  previousnode = previousnode->nxt;
			  // Move to next link in chain
		   }
		 previousnode->nxt = lastnode;
	   }
}
	break;
	case 3:
//////////////////////////////// REMOVE CAR //////////////////////////////////
	
	// node *lastnode;
	 int y;
	 int sid;
	 cout << "Enter the Car you wish to delete starting from 0: ";
	 cin >> sid;
	 cout << endl;
	 // Place pointers at start and the second element in the linked list
	 previousnode = start_ptr;
	 lastnode = previousnode -> nxt;
	 y = 0;
	 //lastnode = start_ptr;
	// for (int x = 0; x == sid; x++)
	// {3
	// previousnode = lastnode;
	// lastnode = lastnode->nxt;
	// y = y++;
	// }
	 /*else	  if (lastnode->nxt == NULL)	 // This part is new!
		  { 
		  delete lastnode;
		  start_ptr = NULL;
		  }*/
		  //int y=0;
		 // cout << "y= " << y << endl;
		 
		 
		  // major troubles deleting from a linked list as can't seemed 
		  // to be able to test whether nxt has reached null. So am not 
		  // able to delete from the bottom of the list. Also troubles 
		  // deleting more than one from the middle of the list (4 or more)
		  
		  if(sid == 0)//should compare input to 0
		  {
		  lastnode = start_ptr;
		  start_ptr = start_ptr->nxt;
		  delete lastnode;
		  }
		  else
		  {
		  previousnode -> nxt = lastnode -> nxt;
		  delete lastnode;
		  }
			
		  

		/* else if (lastnode->nxt == NULL)
		  {
		  delete lastnode;
		  start_ptr = NULL;
		  }
		
				 for (int x = 0; x == sid; x++) 
		  {
		  previousnode = previousnode -> nxt;
		  lastnode = lastnode -> nxt;
		  if ((lastnode->nxt == NULL) == NULL)	 // This part is new!
		  { 
		  delete lastnode;
		  start_ptr = NULL;
		  }
		  else
		  {
		  previousnode -> nxt = previousnode -> nxt -> nxt;
		  delete lastnode;
		  }
		  }		

		
		 else if(lastnode->nxt ==NULL)
		  {
		  if (start_ptr == NULL)
		  {
		  cout << "The list is empty!" << endl;
		  }	 
		  else
		  { 
		  lastnode = start_ptr;
		//  while (lastnode->nxt != NULL)
		//   { 
		// previousnode = lastnode;
		//lastnode = lastnode->nxt;
		//}
		  delete lastnode;
		  previousnode->nxt = NULL;
		  }
	
		  }
	 }//for statement scans the list
		  
//end of else statement  
	 lastnode = NULL;
	 previousnode = NULL;
	 
	 /* previousnode = NULL;

  *
   * Visit each node, maintaining a pointer to
   * the previous node we just visited.
   
  for (lastnode = start_ptr; lastnode != NULL; previousnode = lastnode, 
	  lastnode = lastnode->nxt, int x++) 
	  {
	
	if (lastnode->getData() == item) {  
	  if (previousnode == NULL) {
	Fix beginning pointer. 
	start_ptr = lastnode->nxt;
	  } 
	  else 
	  {
	
	 * Fix previous node's next to
	 * skip over the removed node.
	 
	previousnode->nxt;
	lastnode->nxt;
	  }
	  
	  delete lastnode;  
	  //return true;   
		  //}
  }
	lastnode = start_ptr;
	start_ptr = start_ptr->nxt;
	delete lastnode;
*/
	break;
	case 4:
///////////////////////// HIRE OUT CAR TO CUSTOMER ///////////////////////////
	break;	
	case 5:
///////////////////////// Car Returned by Customer ///////////////////////////
	break;
	case 6:
/////////////////////////////// List All Cars ///////////////////////////////
lastnode = start_ptr;
cout << "\n" << "MAKE\tMODEL\tMILAGE\tREGISTRATION\n";

do
  {  if (lastnode == NULL)
	   cout << "End of list" << endl;
	 else
	   {  // Display details for what temp points to

		  cout << lastnode->make << "\t" << lastnode->model << "\t" << lastnode->milage << "\t" << lastnode->registration << endl;

		  // Move to next node (if present)
		  lastnode = lastnode->nxt;
	   }
  } while (lastnode != NULL);
	
	break;
	case 7:
//////////////////////////////// Close Program ////////////////////////////////
	cout << "Program Closed\n";
	break;
	default:
	cout << "Please choose a number between 1 & 7\n";
	//
	break;
	}
}while(user_input !=7);

	system("PAUSE");
	return EXIT_SUCCESS;
}

/////////////////// SET MILAGE & HIRE CHARGE ///////////////////////////////////
void set_hire_milage_charge()
{
int milage_charge,daily_charge;
cout << "Set Milage Charge\n";
cin >> milage_charge;
cout << "Set Daily Hire Charge\n";
cin >> daily_charge;
Hire hire_charges(milage_charge,daily_charge);
cout << "Charges Set\n\n" << "Milage Charge\tDaily Hire Charge\n";
cout << hire_charges.display_charges();
}



hire.h
#ifndef HIRE_H
#define HIRE_H
#include <string>
 
class Hire
{
		private:
			// string owner;
   //		   Day * today;
			 //Car * listing;
			  int milage_charge,daily_charge;
		 //	  Car * listings;							  
		public:
			   //Hire(string owner);
			   Hire(int daily_charge,int milage_charge);
			   ~Hire();
	   //		bool add_car_list(Car * listings);
	  // bool addcar(Car * listing);
	  // string display();
	  // Day * getDay();
				   std::string display_charges() const;
		   //	void num_of_cars(int car_numbers);
};

#endif



hire.cpp
#include "hire.h"
#include <string>
#include <cstdlib>
#include <sstream>
#include <time.h>

using namespace std;
Hire::Hire(int daily_charge,int milage_charge)
{
this->daily_charge = daily_charge;
this->milage_charge = milage_charge;
}

/*
Hire::Hire(string owner)
{
this->owner = owner;
listing = NULL;

tm *thisDate;
time_t now;
time(&now);
thisDate = localtime(&now);
thisDate->tm_year = 2007 - 1900;
thisDate->tm_mon = 6 - 1;
thisDate->tm_mday = 12;

today = new Day(thisDate);

}*/

Hire::~Hire()
{
}
/*
bool Hire::addcar(Car * listing)
{
this->listing = listing;

}

	 
	 string Hire::display()
	 {
			return listing->display();
	 }
	 
	 Day * Hire::getDay()
	 {
		 return today;
	 }
	 if(listing)
	 {
	 return listing->display();
	 }
	 else
	 {
	 return "No car in list\n";
	 }
	 }
	 
*/
string Hire::display_charges() const
{
	 ostringstream charges;
	  charges << milage_charge << "\t\t" << daily_charge << "\n";
	 return  charges.str();
}


This post has been edited by isuckatC++: 07 May 2009 - 11:05 AM


Is This A Good Question/Topic? 0
  • +

Replies To: linked lists vs vectors

#2 Jubb  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 88
  • Joined: 06-May 09

Re: linked lists vs vectors

Posted 07 May 2009 - 10:57 AM

Vectors can be very useful, if you haven't used them yet I suggest looking them up on wikipedia or www.cplusplus.com
Was This Post Helpful? 0
  • +
  • -

#3 isuckatC++  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 04-May 09

Re: linked lists vs vectors

Posted 07 May 2009 - 11:00 AM

yea thats where i got this idea from in the first place. I was shocked they seemed to be so much more powerful (yet it wasn't even in the book i had). So is there ever really any use for linked lists ? Could u do a linked list of vectors of objects (lol thats a scary concept for a newbie)?

This post has been edited by isuckatC++: 07 May 2009 - 11:03 AM

Was This Post Helpful? 0
  • +
  • -

#4 Jubb  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 88
  • Joined: 06-May 09

Re: linked lists vs vectors

Posted 07 May 2009 - 11:09 AM

Yes you could do that. I like your username.
Was This Post Helpful? 0
  • +
  • -

#5 isuckatC++  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 04-May 09

Re: linked lists vs vectors

Posted 07 May 2009 - 11:13 AM

yea I thought It was appropriate and it will be more ironic when i know my shit :D.
Was This Post Helpful? 0
  • +
  • -

#6 polymath  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 52
  • View blog
  • Posts: 670
  • Joined: 04-April 08

Re: linked lists vs vectors

Posted 07 May 2009 - 11:54 AM

Linked lists are better than vectors for large numbers of larger objects. A linked list doesn't have to reallocate memory each time it is filled to capacity. A vector's reallocation code is roughly just building a new block and copying everything over. The STL makes it slightly more efficient by statistically analyzing how much space will be needed and allocating more than the actual object holds, but when you exceed this limit, you're reallocating the size of the array and copying everything over.

Vectors:
-more efficient access of elements (just adding an offset to a pointer, and dereference)
-less efficient allocation (reallocate the WHOLE array)
-more efficient memory usage (just the sum of its parts).

Linked List (and it's variants):
-less efficient access of elements (have to start at front, sometimes can start at back)
-more efficient allocation (allocate just enough space for one element)
-less efficient memory usage (each link in the list takes 4 bytes, so a double linked list of chars takes 9 bytes vs 1 byte in a vector)

Overall, vectors are better general-purpose, as todays machines have enough processing power and ram to quickly allocate the required memory. Lists are better if you know you're going to be dealing with a HUGE amount of memory or are going to add elements frequently. Again, the power of today's computers makes the difference to the end user almost negligible, except in extreme cases.

Hope this clears some up.
Was This Post Helpful? 1
  • +
  • -

#7 isuckatC++  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 04-May 09

Re: linked lists vs vectors

Posted 07 May 2009 - 03:39 PM

awesome answer man cheers
Was This Post Helpful? 0
  • +
  • -

#8 polymath  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 52
  • View blog
  • Posts: 670
  • Joined: 04-April 08

Re: linked lists vs vectors

Posted 07 May 2009 - 03:57 PM

welcome :) glad i could help.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1