6 Replies - 615 Views - Last Post: 02 April 2013 - 07:52 PM Rate Topic: -----

#1 Midi_  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 109
  • Joined: 22-May 12

link list/ help

Posted 23 March 2013 - 12:40 PM

Hey everyone,

I need help with an assignment. Im pretty sure ill be ok when I get the ball rolling, I just need a little push.

My assignment is a pre-made menu driven program that adds integers into a link list, deletes numbers, deletes the entire list, etc. it does a bunch of stuff to say the least. That part was given. I now need to add to this program. I need to make a function that will create a new node for the linked list, then add it to the back of the link list(before the NULL node obviously). Now here is the catch, It needs to be in the O(1) time complexity, so no loops. What I think so far is a good way of going with this is to capture the address of the first node that is created. once Ive done that I know where to put the new node. I just dont get where to go from there. any help would be appreciated.

thanks guys!

Is This A Good Question/Topic? 0
  • +

Replies To: link list/ help

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1362
  • View blog
  • Posts: 4,715
  • Joined: 19-February 09

Re: link list/ help

Posted 23 March 2013 - 02:43 PM

Hi, you could have a pointer to the rear/tail as well as the front/head.
Was This Post Helpful? 1
  • +
  • -

#3 Midi_  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 109
  • Joined: 22-May 12

Re: link list/ help

Posted 23 March 2013 - 03:28 PM

View Post#define, on 23 March 2013 - 02:43 PM, said:

Hi, you could have a pointer to the rear/tail as well as the front/head.

I have been trying to do that. I created a "head" object and I created a "lastNodeAddress" object. What I dont understand is how to assign the 1st node created to "lastNodeAddress"

this is what is going on

template <class Object>
void cs20::List<Object>::insert( const Object& data ) {
	// insert after the header node
	ListNode<Object>* newnode = new ListNode<Object>( data, head->getNext() );
	head->setNext( newnode );
  
    if(findLastNode == true){
     lastNodeAddress = newnode;//this is where I am running into trouble
     findLastNode = false;
     }
   // std::cout << lastNodeAddress << std::endl;
    
}



Was This Post Helpful? 0
  • +
  • -

#4 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: link list/ help

Posted 23 March 2013 - 08:26 PM

This is in C ... tracking pointers to both the head and tail
i.e. has both

push_front
push_back

functions


May give you an idea or two ...

http://developers-heaven.net/forum/index.php?topic=2582.msg2877#msg2877



I had several C and C++ snippets demonstrating this up in the Snippet Section of DIC but I think that section is still 'down' :(
I'll see if I can find an other link and get back if I can.

Found one ... :)

http://developers-heaven.net/forum/index.php?topic=310.0

This post has been edited by David W: 23 March 2013 - 08:37 PM

Was This Post Helpful? 1
  • +
  • -

#5 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1086
  • View blog
  • Posts: 4,556
  • Joined: 09-June 09

Re: link list/ help

Posted 23 March 2013 - 10:31 PM

Another option is to read in the numbers as string, then parse the string into individual integers.

i.e.
#include <iostream>
#include <sstream>
#include <vector>
#include <numeric>

void parseStr(std::string str, std::vector<int> &vec) {
   std::stringstream ss(str);
   int temp;
   
   while(ss >> temp)
      vec.push_back(temp);
}


int main() {
   std::string input;
   std::vector<int>vec;
   
   getline(std::cin, input);
   parseStr(input, vec);
   std::cout<<"Sum = "<<std::accumulate(vec.begin(), vec.end(), 0)<<std::endl;
   
   return 0;
}


This post has been edited by jjl: 23 March 2013 - 10:31 PM

Was This Post Helpful? 1
  • +
  • -

#6 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: link list/ help

Posted 23 March 2013 - 11:05 PM

View PostMidi_, on 23 March 2013 - 05:28 PM, said:

View Post#define, on 23 March 2013 - 02:43 PM, said:

Hi, you could have a pointer to the rear/tail as well as the front/head.

I have been trying to do that. I created a "head" object and I created a "lastNodeAddress" object. What I dont understand is how to assign the 1st node created to "lastNodeAddress"

this is what is going on

template <class Object>
void cs20::List<Object>::insert( const Object& data ) {
	// insert after the header node
	ListNode<Object>* newnode = new ListNode<Object>( data, head->getNext() );
	head->setNext( newnode );
  
    if(findLastNode == true){
     lastNodeAddress = newnode;//this is where I am running into trouble
     findLastNode = false;
     }
   // std::cout << lastNodeAddress << std::endl;
    
}





You might like to compare your code above to this below working snippet I just 'lifted' from some working code (of a single-link linked list) I had linked to above for you ...

template< class T >
void List< T >::push_back( const T& e ) // inserts e with type T at end of List
{
    // firstly ... get new Node memory and data 
    Node* n = new Node;
    n->data = e;
    n->next = NULL;

    // if NOT first element in list ...
    if( pFront != NULL )
    {
        pRear->next = n; // add to rear
        pRear = n;       // Now update pRear pointer
    }
    else // IS first element ... so ...
        pRear = pFront = n;
    
    ++size;
}



And for a double-link linked list ...

template < typename T >
void List< T >::push_back( const T& val )
{
    Node* n = new Node;
    n->value = val;
    n->next = 0;
    n->prev = tail;

    if( head ) tail->next = n;
    else head = n;
    
    tail = n;
    ++len;
}

This post has been edited by David W: 23 March 2013 - 11:49 PM

Was This Post Helpful? 1
  • +
  • -

#7 Midi_  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 109
  • Joined: 22-May 12

Re: link list/ help

Posted 02 April 2013 - 07:52 PM

Thanks man this helped a lot I got it figured out. Sorry I didnt get back sooner!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1