I am having difficulty understanding linked lists basics, especially adding to a list. I can loop thru a list to print all the values contained in the list, but I *do not* understand how to add an element to an existing list. I have looked at several previous posts on the subject, and followed some links, but neither were very useful. I would appreciate if someone could post some code on this. I am very good a looking at code and seeing what is trying to be accomplished. Any help would be appreciated. Thanks.

#define Jesus 1

OK, in order to add an element to the end of a link list, you must step through the link list till the current element''s "next" pointer is invalid. Then initialize the data for the element, set the next pointer to NULL, and set the current last element''s next pointer to the new node.

In order to add anywhere, do the same thing, except step to the place where you want to insert it, then set the element that''s before the place you want to insert it ''s "next pointer to the new data node, and set the new data node''s next pointer to the node that comes after
Inserting ''A'' in the middle of the list:
B->C->D->E
set ''C'' ''s ''->'' to the ''A'' node and ''A'' ''s ''->'' to the ''D'' node.

To put it at the beginning of the list:
B->C->D
set the new node''s ''->'' to B, and set the head of the list to ''A''.

I don´t know how much you know, but the easiest wat is to use the list classes in standard template library (STL).

Here is a quick example how to use the vector class:

#include <vector>struct MY_STRUCT{ int x,y;};std::vector <MY_STRUCT> g_vObjects;void Add(){ MY_STRUCT object = { 5, 3 }; g_vObjects.push_back(object);}int FindPoint(int x, int y){ int i=0; std::vector <MY_STRUCT> :: const iterator ob = g_vObjects.begin(); while(ob!=g_vObjects.end()) { if(ob->x == x && ob->y == y) return i; else i++; ob++; } return -1;}

It´s not hard to write your own list class either.

Good Luck,

Thanks for the replies. Here is a sample program i put together. It doesn''t work right though (the AddNode() function). Any help would be appreciated.

#include <iostream.h>class Node{ public: Node() { nData = 0; ndNextNode = NULL; } ~Node() {} Node* ndNextNode; int nData;};//// PrintNodeList//void PrintNodeList(Node* n){ Node* list = n; int num = 0; while (list != NULL ) { cout << "\n#" << num << ": " << list->nData; num++; list = list->ndNextNode; } cout << "\n";}//// AddNode//void AddNode(Node* list, int data){ Node* newNode = new Node(); newNode->nData = data; newNode->ndNextNode = NULL; Node* lstptr = list; while (lstptr != NULL) { lstptr = lstptr->ndNextNode; if (lstptr == NULL) // end of list { lstptr = newNode; break; } } list = lstptr;}//// Menu//void Menu(Node* list){ int done=0, choice, data; while (!done) { cout << "\n========================"; cout << "\n MENU "; cout << "\n========================"; cout << "\n(1) Add Node"; cout << "\n(2) Print list"; cout << "\n(3) Quit"; cout << "\nYour choice: "; cin >> choice; switch (choice) { case 1: cout << "\nEntry data: "; cin >> data; AddNode(list, data); break; case 2: PrintNodeList(list); break; case 3: done = 1; break; default: cout << "\nInvalid option."; break; } }}//// main// int main(void){ Node* NodePtr = new Node(); Menu(NodePtr); return 0;}

Hiya,

Here''s just a simple C example of a really simple list, if you were interested in writing your own link list implementation.

/*-------------------------------------------------------The linked list structure-------------------------------------------------------*/struct list_s{	int data;	struct list_s *next;};/*-------------------------------------------------------A global list, for simplicity in this example-------------------------------------------------------*/struct list_s *main_list = NULL;/*-------------------------------------------------------insert to_add into the global list.-------------------------------------------------------*/void AddToList(struct list_s *to_add){	to_add->next = main_list;	main_list = to_add;}/*-------------------------------------------------------remove to_remove from global list (if it can find it there)assumes to_remove is non-null-------------------------------------------------------*/void RemoveFromList(struct list_s *to_remove){struct list_s *node;	if (to_remove == main_list)	{		main_list = main_list->next;	}	else	{		for (node = main_list; node && node->next != to_remove; node = node->next);	// (note the semicolon)		if (node && node->next)		{			node->next = to_remove->next;		}	}	to_remove->next = NULL;}/*-------------------------------------------------------allocate and insert a new list element into the main list.Return a pointer to that newly allocated element.-------------------------------------------------------*/struct list_s *CreateAndInsertNewElement(void){struct list_s *new_element;	new_element = (struct list_s *) malloc(sizeof(struct list_s));	new_element->data = 0;	new_element->next = NULL;	AddToList(new_element);	return new_element;}/*-------------------------------------------------------find and remove the given element from the main list (if itcan find it).deallocate the memory for that element.assumes to_delete is non-null.-------------------------------------------------------*/voidFindAndFreeElement(struct list_s *to_delete){	RemoveFromList(to_delete);	free(to_delete);} 

STL is alot better than this, but if you were trying to get to the internals of linked lists, this will hopefully give you an idea : )



-ns-

Hi again,

The way you have it, you''d want to change your add function to something more like:

// ---------------------------------------------------------------// Add a new node (to the end of the list), return a pointer to it.// Input: **list = pointer to the pointer to the start of the list.// we need this because the actual start of the list might change// (for example, if it starts out as being NULL, when we add the first// element, the list will not be NULL anymore!)// ---------------------------------------------------------------Node *AddNode(Node **list, int data){Node* newNode = new Node();	newNode->nData = data;	newNode->ndNextNode = NULL;	if (*list == NULL)	{	// list was empty. list becomes newNode. Real easy to hook up 		*list = newNode;	}		else	{	// list wasn''t empty. find the last element of it, and hook newNode to it''s next pointer.		Node* lstptr = *list;		while (lstptr->ndNextNode != NULL)			{			lstptr = lstptr->ndNextNode;		}		// at this point, lstptr points to the _last_ element of the list.		lstptr->ndNextNode = newNode;	}	return newNode;} 

-ns-

I used NightShade''s code, but it still didn''t work. I''m beginning to wonder if linked lists are worth the trouble...

Hahaha, it put a smiley in my code.

Thanks NightShade. Got it working. In case you''re interested, here''s the code for the AddNode() function:

//// AddNode//void AddNode(Node* list, int data){ Node* newNode = new Node(); newNode->nData = data; newNode->ndNextNode = NULL; Node* lstptr = list; if (lstptr == NULL) lstptr = newNode; else { while (lstptr->ndNextNode != NULL) { lstptr = lstptr->ndNextNode; } lstptr->ndNextNode = newNode; }}

Hmmmmm.. I just tested the code, works OK here.

The items don''t remain in order when you add them with my C source (they get reversed). Your way keeps them in order, if thats what you were looking to do.

(Here''s the code I used to test that code, more or less)

	struct list_s *s;int i;char str[200];	for (i = 0; i < 28; ++i)	{		s = CreateAndInsertNewElement();		s->data = i + 100;		sprintf(str, "Adding a new element. Data is %d\n", s->data);		OutputDebugString(str);	}	for (i = 0, s = main_list; s; ++i, s = s->next)	{		sprintf(str, "Element %d has a value of %d\n", i, s->data);		OutputDebugString(str);	}	while (main_list)	{		sprintf(str, "Deleting element with data %d\n",main_list->data);		FindAndFreeElement(main_list);		OutputDebugString(str);	} 

-ns-