[alias120]

Hello there, I had a question in regards to Linked Lists in C++. I have been learning Standard C++ for a few months now primarily using the following guides;

http://www.cprogramm...m/tutorial.html

http://www.cplusplus.com/doc/tutorial/

I have a decent understanding of data structures and classes, as well as pointers. I have begun looking into Linked Lists, and though i am understanding the concept i am having a hard time coding a working program. I was wondering if anyone has any good resources that they have used for this particular topic. I have been browsing the web, and have had difficulty finding a very basic explanation of Linked Lists. I will continue looking, and i appreciate any feedback you can provide.

-alias

[KYA]

shameless plug

[alias120]

Thank you KYA, i should have known to browse your blog for this.

-alias

[David W]

You might also like to see these:

http://developers-he...477.html#msg477

Template class List (using a plain linked-list)

http://www.dreaminco...snippet2617.htm


Modified: Template class List with front, rear and size
expanded to keep track of rear (and size also) to speed up
'push_back' or size requests ... now with merge sort and
insert sort and remove duplicates

http://www.dreaminco...snippet3448.htm


a linked list ... (with an insertion sort method that adds new
list elements by inserting them in ABC...abd... order ...

http://developers-he...257.html#msg257

This post has been edited by David W: 30 January 2010 - 07:20 PM

[athlon32]

In addition to the resources posted already, take a look at this:
http://www.dreaminco...wtopic10157.htm

The authors code is very easy to read, and explains things very clearly

[Bench]

EternallyConfuzzled has several excellent articles on a number of different kinds of data structures - http://www.eternallyconfuzzled.com/

[alias120]

Thank you all very much, all of this material combined should more than suffice. I greatly appreciate the additional resources, I will be sure to make good use of them.

-alias

[alias120]

Alright, well thanks to all of you i was able to piece together a simple Linked List. I borrowed the naming convention from your example David W, so i apologize if it looks very similar. It is not perfect, but it is a step in the right direction. I was actually disappointed in myself for not being able to create this list all in main(). Though the code i came up with is more modularized, i know i need more practice. Anyway, thank you all for your expertise. Here is the end result.

#include<iostream>
#include<string>

using namespace std;

struct Node {

	string data;
	Node *next;
};


Node *linkedList (Node *pHead);
void showList (Node *pHead);

int main() 
{
	
	Node *pHead = NULL;

	cout<<"Input 5 strings you would like to list"<<endl;
	cout<<endl;
	
	pHead = linkedList (pHead);

	

	cout<<"\nHere are the strings that you inputed"<<endl;
	cout<<endl;

	showList(pHead);
	
	cout<<endl;
	cin.get();
}

Node *linkedList (Node *pHead) {

	Node *pEnd, *pGo;
	int i = 0;
	int count = 1;
	string getLine;
	
	if( pHead != NULL ) 
	{
		for( pEnd=pHead; pEnd->next!=NULL; pEnd = pEnd->next);
	}	
	
	
	while (i < 5 ){
			cout<<count<<". ";
			cin>>getLine;
			pGo = new Node;
			pGo->data = getLine;
			pGo->next = NULL;
			if (pHead == NULL ) {
				pHead = pGo;
				pEnd = pGo;
			}
			else {
				pEnd->next = pGo;
				pEnd = pGo;
			}
			i++, count++;
		};
	return pHead;
}


void showList (Node *pList) {
	int count = 1;
	while ( pList != NULL ) {
		cout<<count<<". "<<pList->data<<"\n";
		cout<<endl;
		pList = pList->next;
		count++;
	};
}

[David W]

You might like to see this cleaned-up revision ...
(with simple input data validation) ...

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node* next;
};

// function prototypes ...
Node* addToList( Node* pList, int& num );
void showList( Node* pList );
int getInt( char prompt[] );
bool ok();


int main() /////////////////////// MAIN BEGINS /////////////////////////////////
{
    int size = 0;
    Node* pHead = NULL;
    
    pHead = addToList( pHead, size );
    cout << "\nHere are the " << size << " strings in the list ...\n";
    showList( pHead );

    cout << endl;

    pHead = addToList( pHead, size );
    cout << "\nHere are the " << size << " strings in the list ...\n";
    showList( pHead );

    cout << "\nPress 'Enter' to continue ... " << flush;
    cin.get();
} //////////////////////////////// MAIN ENDS ///////////////////////////////////


Node* addToList( Node* pList, int& size )
{
    int num = getInt( "How many strings would you like to input ? " );
    
    // now find the end ...
    Node* pEnd = pList;
    if( pEnd != NULL )
        while( pEnd->next != NULL )
            pEnd = pEnd->next;

    // and add new nodes ... to end
    Node* pNew;
    string tmpStr;
    for( int i = 0; i<num ; )
    {
        cout << (i+size+1) << ". ";
        getline( cin, tmpStr );
        if( ! ok() ) continue; // from top of for loop right now ...
        
        // ok ... add this to list ...
        ++i;
        pNew = new Node;
        pNew->data = tmpStr;
        pNew->next = NULL;
        
        if( pList != NULL )     // add to end ...
        {
            pEnd->next = pNew;  // link to new node
            pEnd = pNew;        // reset 'pEnd' to this latest new node
        }
        else
            pList = pEnd = pNew;
    };
        
    size += num; // Note: size returned by ref.
    return pList;
}

void showList(Node* pList)
{
    for( int count = 0; pList != NULL; pList = pList->next )
        cout << ++count << ". " << pList->data << endl;
}

int getInt( char prompt[] )
{
    int num;
    for( ; ; ) // loop forever ... until return if good 'num'
    {
        cout << prompt << flush;
        cin >> num;
        if( cin.good() && num > 0 )
        {
            cin.sync();
            return num;
        }
        // else
        cin.clear();
        cin.sync();
        cout << "Error! Enter an integer > 0 \n";
    }
}

bool ok() // defaults to NO ...
{
    cout << "Ok ... (y/n) ? " << flush;
    int reply = cin.get();
    cin.sync();
    return reply == 'y' || reply == 'Y';
}

This post has been edited by David W: 29 January 2010 - 06:32 PM

[David W]

And note how ... 'adding to the end of a list' ... can be made so much easier ... just by keeping track of the address of the last node in the list.

// using typedef and pTail (to make adding at the end very easy)

#include<iostream>
#include<string>

using namespace std;

struct Node
{
    string data;
    Node* next;
};

typedef Node* pNode; // so NOW can code ... pNode ... instead of ... Node*

// function prototypes ...
void addToList( pNode& pList, pNode& pEnd, int& num ); // NOTE pass by reference
void showList( pNode pList );
int getInt( char prompt[] );
bool ok();


int main() /////////////////////// MAIN BEGINS /////////////////////////////////
{
    int size = 0;
    pNode pHead = NULL;
    pNode pTail = pHead;
    
    addToList( pHead, pTail, size );
    cout << "\nHere are the " << size << " strings in the list ...\n";
    showList( pHead );

    cout << endl;

    addToList( pHead, pTail, size );
    cout << "\nHere are the " << size << " strings in the list ...\n";
    showList( pHead );

    cout << "\nPress 'Enter' to continue ... " << flush;
    cin.get();
} //////////////////////////////// MAIN ENDS ///////////////////////////////////


void addToList( pNode& pList, pNode& pEnd, int& size )
{
    int num = getInt( "How many strings would you like to input ? " );
    
    // and add new nodes ... to end
    pNode pNew;
    string tmpStr;
    for( int i = 0; i<num ; )
    {
        cout << (i+size+1) << ". ";
        getline( cin, tmpStr );
        if( ! ok() ) continue; // from top of for loop right now ...
        
        // ok ... add this to list ...
        ++i;
        pNew = new Node;
        pNew->data = tmpStr;
        pNew->next = NULL;
        
        if( pList != NULL )     // add to end ...
        {
            pEnd->next = pNew;  // link to new node
            pEnd = pNew;        // reset 'pEnd' to this latest new node
        }
        else
            pList = pEnd = pNew;
    };
        
    size += num; // Note: size also returned by ref.
}

void showList( pNode pList )
{
    for( int count = 0; pList != NULL; pList = pList->next )
        cout << ++count << ". " << pList->data << endl;
}

int getInt( char prompt[] )
{
    int num;
    for( ; ; ) // loop forever ... until return if good 'num'
    {
        cout << prompt << flush;
        cin >> num;
        if( cin.good() && num > 0 )
        {
            cin.sync();
            return num;
        }
        // else
        cin.clear();
        cin.sync();
        cout << "Error! Enter an integer > 0 \n";
    }
}

bool ok() // defaults to NO ...
{
    cout << "Ok ... (y/n) ? " << flush;
    int reply = cin.get();
    cin.sync();
    return reply == 'y' || reply == 'Y';
}

This post has been edited by David W: 29 January 2010 - 06:34 PM

[alias120]

Thank you for the additional examples David, i did leave out any form of error checking in my code which i know is not good practice. I've been taking baby steps with this concept and wanted to ensure i could at least get it working.
I like the implementation of typedef to clean up reference to the node. I'll be creating a more sound product now that i have a better idea of how the linked list itself works.

-alias

[alias120]

I like the error checking you added to the program, there is some syntax in there i haven't come across yet so it gives me something new to research. Thanks for keeping me busy lol.

-alias

[David W]

alias120, on 30 Jan, 2010 - 02:53 PM, said:

I like the error checking you added to the program, there is some syntax in there i haven't come across yet so it gives me something new to research. Thanks for keeping me busy lol.

-alias

And thanks for keeping me ... 'busy' also ... I enjoy the work while preparing for the big event just past the looming horizon of all this difficult economic, and other ... troubles ...

But be encouraged ...

http://sites.google....eyeshallseehim/

Shalom shalom,

David
http://developers-he...index.php/topic,46.0.html