linked lists

[monocog]

Nucleon was nice enough to provide me with the following code to help learn lists a while back. I've had a little more time to revisit lists again and would like to see what this code looks like using a linked list instead of an array..

This is NOT homework, I'm trying to learn C++ on my own. I'm just going through whatever material I can get my hands on as I have time and I like seeing how things would change with programs that I understand (like this one).

Thanks!

#include <iostream>
using namespace std;

const int MAXLEN = 20;
typedef int ITEMTYPE; 
class List
{
	public:
		List();
		
		ITEMTYPE retrieve (int pos) const;
		void insert (const ITEMTYPE input, int pos);
		void append (ITEMTYPE input);
		bool remove (int pos);
		int length () const;
		bool isEmpty ();
		void makeEmpty();
		void printlist();
		bool search(ITEMTYPE input);
		int itempos(ITEMTYPE input);
	private:
		ITEMTYPE item[MAXLEN];
		int len;
};

List::List()
{
	cout << "Creating empty list" << endl;
	len=0;
}

ITEMTYPE List::retrieve (int pos) const
{
	int index=pos-1;
	int max=length();

	ITEMTYPE temp;

	if ((index>=0)&&(pos<=max))
	{
		temp = item[index];
	}
	return temp;
}	

void List::insert (const ITEMTYPE input, int pos)
{
	int len=length();
	int index=pos-1;
	int indexOfLast=len-1;

	if ((index>=0)&&(index<len))
	{

		for(indexOfLast;indexOfLast>=index;indexOfLast--)
		{
			item[indexOfLast+1]=item[indexOfLast];
		}
		item[index]=input;
	}
	else
		cout << endl << "Position does not exist" << endl;
	
}
void List::append (ITEMTYPE input)
{
	int last=length();
	int appendpos=last;

	item[appendpos]=input;
}

bool List::remove (int pos)
{
	
	bool removed=false;
	int len=length();
	int index = pos-1;
	int indexOfLast=len-1;
	
	int counter=index;


	if ((index>= 0)&&(index < indexOfLast))
	{
		cout<< "last: " << indexOfLast<<endl;

		do
		{
			//item[index]=item[index+1];
			item[counter]=item[counter+1];
			cout<<item[index];
			//cout<<counter;
			counter++;

		}while(counter<=indexOfLast);

		item[indexOfLast]=0;
		removed=true;
		
	}
	
return removed;
}

int List::length () const
{
	int sum=0;
	for(int j=0; j<=MAXLEN; j++)
	{
		if(item[j]!=0)
			sum++;
	}
	return sum;
}

bool List::isEmpty ()
{
	bool empty=false;
	int len=length();

	for(int j=0; j<=MAXLEN; j++)
	{
		if(len==0)
			empty = true;
	}
	return empty;
}

void List::makeEmpty()
{
	for(int j=0; j<=MAXLEN; j++)
	{
		item[j]=0;
	}
}

void List::printlist()
{
	bool empty = false;
	cout << "The Available Items in the List are: " << endl;

	for (int j=0; j<=MAXLEN;j++)
	{
		if (item[j]!=0){
			cout << "Position: " << j+1 << ". " << item[j] << endl;
		}
	}

	if (empty==true)
	{
		system("cls");
		cout << endl << endl << "\t\tThe List is empty" << endl << endl;
	}

}

bool List::search(ITEMTYPE input)
{
	bool found=false;
	int max=length();

	for(int j=0; j<=max; j++)
	{
		ITEMTYPE element=retrieve(j);
		if(element== input)
			found = true;
	}
	return found;
}

int List::itempos(ITEMTYPE input)
{
	
	int max=length();
	int pos;

	for(int j=0; j<=max; j++)
	{
		ITEMTYPE element=retrieve(j);
		if(element== input){
			pos=j;
		}
	}
	return pos;
}

int main()
{
	List ListArray;
	int Input;
	int pos;
	ITEMTYPE output;
	bool removed=false,found=false,loop;
	char choice;

	ListArray.makeEmpty();


	int menu;
	do
	{
		loop=false;

		do
		{
			cout << "\t\t\t Menu Choices" << endl << endl;
			cout << "\t\t1 - Insert Item " << endl;
			cout << "\t\t2 - Edit Item" << endl;
			cout << "\t\t3 - Retrieve Item" << endl;
			cout << "\t\t4 - Delete an Item" << endl;
			cout << "\t\t5 - Previous Item" << endl;
			cout << "\t\t6 - Next Item" << endl;
			cout << "\t\t7 - Search" << endl;
			cout << "\t\t8 - Print List Items" << endl;
			cout << "\t\t9 - Clear List" << endl;
			cout << "\t\t0 - Quit" << endl << endl;
			cout << "\tEnter your choice: ";
			cin >>menu;

		} while ((menu <=1) && (menu >= 10));
		switch(menu)
		{
		case 1:
			system("cls");
			cout << "Value to insert:" << endl;
			cin >> Input;
			cout << "Position to insert at:" << endl;
			cin >> pos;			
			ListArray.insert(Input,pos);			
			loop=true;
			break;
		case 2:
			system("cls");
			cout << "Value to edit:" << endl;
			cin >> Input;
			ListArray.append(Input);
			loop=true;
			break;
		case 3:
			system("cls");
			cout << "Position of the value to retrieve:" << endl;
			cin >> pos;
			output = ListArray.retrieve(pos);
			cout << endl << "The value at position: " << pos << " is " << output;
			loop = true;
			break;
		case 4:
			system("cls");
			cout << "Position of the item to delete:" << endl;
			cin >> pos;
			removed = ListArray.remove(pos);
			if (removed=true)
				cout << endl << "The Item has been Successfully Deleted" << endl;
			else
				cerr << endl << "Error deleting the Item" << endl;
			loop=true;
			break;
		case 5:
			system("cls");
			if (pos > 0) pos--;
			break;
		case 6:
			system("cls");
			if (pos < MAXLEN - 1) pos++;
			break;
		case 7:
			system("cls");
			cout << "Value to find" << endl;
			cin >> Input;
			found=ListArray.search(Input);
			pos=ListArray.itempos(Input);
			cout << endl << "The Item " << Input << " is found at position: " << pos << endl << endl;
			loop=true;
			break;
		case 8:
			system("cls");
			ListArray.printlist();
			loop=true;
			break;
		case 9:
			system("cls");
			cout << endl << "Are you Sure you want to empty the List?(y/n)" << endl;
			cin >> choice;
			if (choice=='y')
				ListArray.makeEmpty();
			loop=true;
			break;
		case 0:
			loop=false;
			break;
		default:
			cerr << "Invalid Entry";
			loop=true;
			break;
		}
	}while (loop==true);
	
	

return 0;
}

[Lerner]

You are welcome to do what you want with your compiler and you machine. You should be aware however that there is a jargon associated programming in C++ just like there is in most other areas of life. One of the traditional assumptions (jargon) when talking about lists in C++ is that you will be dealing with a structure that consists of a series of discrete data chunks that linked together by pointers and residing in memory that need not be contiguous. Furthermore, the -> operator will traditionally be used much more than the [] operator would be. If you wish to try to convert the code posted into a more traditional C++ type list, that is certainly doable. If you want to give it a try post relevant information when you get stuck. As posted, though, I can't find a question to assist you with.

[monocog]

So there is no quick and easy (or even dirty) way to modify this to use a linked list? Just something I can see to kind of gain a little bit of and understanding as to how a linked list works?

[Lerner]

IMO the best way is to hop in. Tackle one method at a time. DON'T attempt to write everything and then try to compile!! Here's a start.

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

struct pList
{
   Node * head;
   pList() : head(NULL) {}

   void insert(int d)
   {
       Node * newNode = new Node;
       newNode->data = d;
       newNode->next = NULL;
       if(head == NULL)
         head = temp;
   }

   void display()
   {
      Node * temp;
      temp = head;
      while(temp)
      {
         cout << temp->data;
         temp = temp->next;
      }
   }

   ~pList()
   {
      Node * temp;
      while(head)
      {
         temp = head;
         head = head->next;
         delete temp;
       }
   }
}; 

int main()
{
    pList  myList;
    myList.insert(4);
    myList.display();
    cin.get();
    return 0;
}

This code declares a node type to build the list with. The list class has a default constructor which just sets head to NULL, an insertion function to actually store stuff in a list (although it's limited to building a list with just a single node at this time and will need to be modified to do more), a display() function to see what's in the list, and a destructor to release dynamic memory used in the list associated. There's even a driver program to get it to actually do all that. But, I've not compiled and run it to confirm it actually works. You can do that and then modify it to get just the bare essentials working. Then you can modify the bare bones to match the same tasks done in your current code using all the bells and whistles. Only then would I proceed beyond the very basics as outlined above.