Pointers & Linked List

[Braindead90]

I am working on creating a linked list to connect the previous value number (or string) to another value
I asked this question before I am just guessing I did it completely wrong since no one responded. So what would be the best way to start the function.

I need to linked the list of strings together and be able to add a new name and be able to add name either a the end or middle easily

Example
[John]->[Stewart]->[Hanna}

Insert Patrica in second spot

[John]->[Patrica]->[Stewart]->[Hanna]

//Platform: C++ Win32 Console Visual Studio 2010
    #define _CRTDBG_MAP_ALLOC
    #include <iostream>
    #include <stdlib.h>
    #include <crtdbg.h>
    #include <iomanip>
    #include <windows.h>
    #include <string>
    using namespace std;
    #include "CNode.h"
     
    int main()
    {
    {
    CNode<string>* head = NULL;
    CNode<string>* ptr;
     
    string players[8] = {"Becky","Aaron","John","Magret","Susan","Andrea","Morgan Freeman","Carmelo"};
     
    for (int i=0; i<8; i++)
    {
    string playrs = players[i];
    cout<< playrs << endl;
    ptr = new CNode<string>(playrs);
    ptr->insert(head,ptr);
     
     
    }
     
     
    cout << head->ToString()<<endl;
     
    }
    _CrtDumpMemoryLeaks();
     
    cout << endl;
    system("pause");
    return 0;
    }

And the h.file is

#pragma once
#include <cstdlib>
#include <string>
#include <sstream>
using namespace std;

template <typename T>
class CNode  
{
private:
	CNode<T>* m_pNext;
	T m_value;
public:
	CNode(T value);
	virtual ~CNode();
	T& Value();
	CNode<T>* getNext();
	void setNext(CNode<T>* address);
	string ToString();
	void insert(CNode<T> head, CNode<T> item); 
};

template <typename T>
CNode<T>::CNode(T value)
{
	m_value = value;
	m_pNext = NULL;
}

template <typename T>
CNode<T>::~CNode()
{
}

template <typename T>
CNode<T>* CNode<T>::getNext()
{
	return m_pNext;
}

template <typename T>
void CNode<T>::setNext(CNode* address)
{
	m_pNext = address;
}

template <typename T>
T& CNode<T>::Value()
{
	return m_value;
}

template <typename T>
string CNode<T>::ToString()
{
	stringstream result;
	CNode<T>* ptr = this;
	while (ptr != NULL)
	{
		result << "[" <<  ptr->Value() << "]";
		ptr = ptr->getNext();
		if (ptr != NULL)
		{
			result << "->";
		}
	}
	return result.str();
}

template <typename T>
void CNode<T>::insert(CNode<T> head, CNode<T> item)
{

\\Dont fully understand what to type here...


}

Any suggestion or even links to pages that talk about linked list will be very helpful
Thanks

[sfuo]

I wrote this linked list a while ago. After reading yours for a bit I went back and modified mine to use templates and used your names.

You can take a look at this and use what you want.

It has four functions:
Add() which appends a node to the list
AddAt() which inserts a node at an index
AddAfter() which inserts a node after the named node
Print() displays the contents of the list

#include <iostream>
using namespace std;

template <typename T>
struct Node
{
	Node(){};
	Node( T n )
	{
		name = n;
		next = NULL;
	}
	T name;
	Node *next;
};

template <typename T>
class List
{
	Node<T> *first;

	public:

	List()
	{
		first = NULL;
	}

	void Add(T name) //adds a new entry to the list
	{
		Node<T> *newNode = new Node<T>(name);
		Node<T> *curNode = first;


		if( curNode == NULL )
		{
			first = newNode;
			return;
		}

		while(curNode->next != NULL)
		{
			curNode = curNode->next;
		}
		curNode->next = newNode;
	}

	void AddAt(T name, int index)
	{
		Node<T> *newNode = new Node<T>(name);
		Node<T> *curNode = first;
		Node<T> *nexNode = 0;
		Node<T> *prvNode = 0;

		if( curNode == NULL )
		{
			first = newNode;
			return;
		}

		int i = 1;
		while(curNode->next != NULL && i != index)
		{
			prvNode = curNode;
			curNode = curNode->next;
			i++;
		}

		if( i != index )
		{
			curNode->next = newNode;
			return;
		}

		if( prvNode == NULL )
		{
			nexNode = first;
			first = newNode;
			newNode->next = nexNode;
			return;
		}

		nexNode = prvNode->next;
		prvNode->next = newNode;
		newNode->next = nexNode;
	}

	void AddAfter(T name, T search)
	{
		Node<T> *curNode = first;
		Node<T> *nexNode = 0;
		bool found = false;

		while( curNode != NULL )
		{
			if( curNode->name == search )
			{
				found = true;
				break;
			}
			curNode = curNode->next;
		}

		if( found == false )
		{
			cout << "\'" << search << "\'" << " was not found!" << endl << endl;
			return;
		}

		Node<T> *newNode = new Node<T>(name);

		nexNode = curNode->next;
		curNode->next = newNode;
		newNode->next = nexNode;
	}

	void Print() //displays contents of the list
	{
		Node<T> *curNode = first;

		if( curNode == NULL )
			return;
		while(curNode != NULL)
		{
			cout << "[" << curNode->name << "]";
			curNode = curNode->next;
			if( curNode != NULL )
				cout << " -> ";
		}
		cout << endl;
	}
};


int main()
{
	List<string> people;
	people.Add("John");
	people.Add("Stewart");
	people.Add("Hanna");
	people.Print();
	people.AddAt("Patrica", 2);
	people.Print();


    return 0;
}

[sundip]

Why you don't try with STL list STL::LIST

[Braindead90]

Why you don't try with STL list STL::LIST

This is for a class and it just has to be done this way...

[Braindead90]

I wrote this linked list a while ago. After reading yours for a bit I went back and modified mine to use templates and used your names.

You can take a look at this and use what you want.

It has four functions:
Add() which appends a node to the list
AddAt() which inserts a node at an index
AddAfter() which inserts a node after the named node
Print() displays the contents of the list

#include <iostream>
using namespace std;

template <typename T>
struct Node
{
	Node(){};
	Node( T n )
	{
		name = n;
		next = NULL;
	}
	T name;
	Node *next;
};

template <typename T>
class List
{
	Node<T> *first;

	public:

	List()
	{
		first = NULL;
	}

	void Add(T name) //adds a new entry to the list
	{
		Node<T> *newNode = new Node<T>(name);
		Node<T> *curNode = first;


		if( curNode == NULL )
		{
			first = newNode;
			return;
		}

		while(curNode->next != NULL)
		{
			curNode = curNode->next;
		}
		curNode->next = newNode;
	}

	void AddAt(T name, int index)
	{
		Node<T> *newNode = new Node<T>(name);
		Node<T> *curNode = first;
		Node<T> *nexNode = 0;
		Node<T> *prvNode = 0;

		if( curNode == NULL )
		{
			first = newNode;
			return;
		}

		int i = 1;
		while(curNode->next != NULL && i != index)
		{
			prvNode = curNode;
			curNode = curNode->next;
			i++;
		}

		if( i != index )
		{
			curNode->next = newNode;
			return;
		}

		if( prvNode == NULL )
		{
			nexNode = first;
			first = newNode;
			newNode->next = nexNode;
			return;
		}

		nexNode = prvNode->next;
		prvNode->next = newNode;
		newNode->next = nexNode;
	}

	void AddAfter(T name, T search)
	{
		Node<T> *curNode = first;
		Node<T> *nexNode = 0;
		bool found = false;

		while( curNode != NULL )
		{
			if( curNode->name == search )
			{
				found = true;
				break;
			}
			curNode = curNode->next;
		}

		if( found == false )
		{
			cout << "\'" << search << "\'" << " was not found!" << endl << endl;
			return;
		}

		Node<T> *newNode = new Node<T>(name);

		nexNode = curNode->next;
		curNode->next = newNode;
		newNode->next = nexNode;
	}

	void Print() //displays contents of the list
	{
		Node<T> *curNode = first;

		if( curNode == NULL )
			return;
		while(curNode != NULL)
		{
			cout << "[" << curNode->name << "]";
			curNode = curNode->next;
			if( curNode != NULL )
				cout << " -> ";
		}
		cout << endl;
	}
};


int main()
{
	List<string> people;
	people.Add("John");
	people.Add("Stewart");
	people.Add("Hanna");
	people.Print();
	people.AddAt("Patrica", 2);
	people.Print();


    return 0;
}

I tried running your code and it did build in visual studio but it crashed when i ran while debugging...
"Unhandled exception at 0x77e115ee in Lab05.exe: 0xC0000005: Access violation writing location 0x00000020."
no idea why though

[sfuo]

I tossed it into Visual Studio C++ and it gave me a bunch of errors saying that you cannot do

cout << "[" << curNode->name << "]";

So I changed the Print() function to return a string and use a stringstream to create that string.

within the class

string Print() //displays contents of the list
{
	Node<T> *curNode = first;
	stringstream strm;
	if( curNode == NULL )
		return "";
	while(curNode != NULL)
	{
		strm << "[" << curNode->name << "]";
		curNode = curNode->next;
		if( curNode != NULL )
			strm << " -> ";
	}
	return strm.str();
}

new main

int main()
{
	List<string> people;
	people.Add("John");
	people.Add("Stewart");
	people.Add("Hanna");
	cout << people.Print() << endl;
	people.AddAt("Patrica", 2);
	cout << people.Print() << endl;

	return 0;
}

EDIT: You also have to include <sstream> at the top

Is the error that you got a run-time error?