Basic question about linked lists

[ART01]

I have got stuck with a very basic prb in Linked lists, i m familiar with array, as in array to compare two elements of the array u can simply use their position in the array since they are all positioned in a consecutive manner in memory like:
if(arr[2]<arr[3])
//do this...

how can i get the same thing with a linked list?? like
nodo* p;
for(p=List;p!=0;p++)
if(p->key > ...... // dont know what to write here to compare the key of the one node, for example the first with the key of the second node.

thanks in advance

[twomers]

Maybe something like:

nodo *p1, *p2;

p1 = List;
p2 = List->next;

if ( p1->key == p2->key ) // or p1->key == p1->next->key
 // do this...

Your problem is that you don't have a random access element for your list, i.e. the [] operator. You could probably write that if you wanted.

[ART01]

Maybe something like:

nodo *p1, *p2;

p1 = List;
p2 = List->next;

if ( p1->key == p2->key ) // or p1->key == p1->next->key
 // do this...

i made a program, using ur answer, the program reads a list from the user and then passes it to a function, which does a scan of the list and if the an element if bigger than the one ahead of it, it is put in a new list and in the end the list is returned, i believe it doesnt work... take a look at the code:
lista funzione(lista l){

lista l1=0;
nodo* p;
nodo* p1=l;
nodo* p2=l->next;
for(p=l;p!=0;p++){
if(p1->key>p2->key)
ins_coda(l1,p->key);}
return l1;
}
int main(){
cout << " insersic la lista " << endl;
lista l=leggi();
cout << " la risposta è " << funzione(l);
system("pause");
}

Your problem is that you don't have a random access element for your list, i.e. the [] operator. You could probably write that if you wanted.

indeed that is the main issue, since i dont have that feature of array,where is can access any element using the number of its position, the question is how can u compare two elements of a list.

[twomers]

Here's a very crude example which I haven't tested, but even if it doesn't work it'll show you how to go about the problem...

struct mylist {
  int num;
  mylist *next;
};

int main( void ) {
  // Setup list
  mylist *l = new mylist;;
  l->num = 42;
  l->next = new mylist;

  l->next->num = 24;
  l->next->next = NULL;

  // Print which is bigger
  mylist *iter;
  for ( iter=l; iter->next && iter!=NULL; iter=iter->next ) {
    if ( iter->num > iter->next->num )
      std::cout<< iter->num << ">" << iter->next->num << "\n";
  }

  // Delete list
  iter = l;
  do {
    l = iter->next;
    delete iter;
  } while ( iter = l->next );
}

[ART01]

Here's a very crude example which I haven't tested, but even if it doesn't work it'll show you how to go about the problem...

struct mylist {
  int num;
  mylist *next;
};

int main( void ) {
  // Setup list
  mylist *l = new mylist;;
  l->num = 42;
  l->next = new mylist;

  l->next->num = 24;
  l->next->next = NULL;

  // Print which is bigger
  mylist *iter;
  for ( iter=l; iter->next && iter!=NULL; iter=iter->next ) {
    if ( iter->num > iter->next->num )
      std::cout<< iter->num << ">" << iter->next->num << "\n";
  }

  // Delete list
  iter = l;
  do {
    l = iter->next;
    delete iter;
  } while ( iter = l->next );
}

i think u have declared two lists here and compare nodes of these lists,right? NOT comparing elements of the same list which is the issue...

[twomers]

I made one list ( mylist *l ) and added an element to it ( l->next = new mylist; ), then compared items in the same list ( iter->num > iter->next->num ). iter is simply a pointer which points to the respective 'next' elements in the list. So iter->next (in the first iteration of the for loop), is entirely equivalent to l->next , which is the only list I'm using. And in the second iterator of the for loop iter->next is the same as l->next->next . Get me? iter is a pointer whose only purpose is to iterate through all the elements of the linked list.

[ART01]

l->next = new mylist;// i was confused here
l->next->num = 24;
l->next->next = NULL;

could u tell me if ur idea put to the practice looks something like this?

lista function(lista l){

   lista t=0;
   nodo* p;
   for(p=l;p!=0;p=p->next){
   if(p->key  > p->next->key)  
   ins_coda(t,p->key);   }
   return t;
   }

int main(){
    cout << " insert the list elements " << endl;
    lista l=leggi();
    cout << " the new list after the function " << function(l);
system("pause");

bt again i have tried this, bt it doesnt work at all, i think there must be some established way to be able to compare the keys of two nodes of a list, i have been trying to find about it, bt i have been successful yet.....

[sidatra79]

Here sth might be what u r looking for:

/////////////
class CLink {    
public :
    CLink(CLink * pNext, int id) : _pNext(pNext),_id(id) {}
    int Id() const { return _id;}
    CLink * Next() const { return _pNext;}    
private:
    int _id;
    CLink* _pNext;
    
};
/////////////
class CList {    
public:
    CList() : _pHead(0) {}
    ~CList() {
    while ( _pHead != 0 ) {
    	CLink* pLink = _pHead;
    	_pHead = _pHead->Next(); // unlink pLink
        delete pLink;
      }
    }
    void Add(int id) {
    //Add in front of the list
    CLink* pLink = new CLink(_pHead,id);  
    _pHead = pLink; 
    }
    CLink const * GetHead() const { return _pHead; }   
private:
    CLink* _pHead;
    
};
/////////////
int main()  
{
CList alist;
alist.Add(5);
alist.Add(3);
alist.Add(15);
alist.Add(3);
int id = 3;

for (CLink const * pLink = alist.GetHead(); 
      pLink != 0; 
      pLink = pLink->Next())
{
	if (pLink->Id() == id)
	std::cout<<"Ups the same id already exists in the link: " <<pLink->Next ()<<std::endl;
	//break;
}  //end of for loop     

} //end of main

The output is :

Ups the same id already exists in the link: some address
Ups the same id already exists in the link: some address

I hope I helped u.

[ART01]

honestly i couldnt understand ur code, is it c++? i m new to programming and c++... could u plz write abit simple?
thanks for the reply though...

[sidatra79]

Hallo again. Of course the code I wrote for u is C++ and in fact "standard c++", therefore portable to use in linux environment too. However I forgot:

#include <iostream>
class CLink

Now I will try to explain u some things concerning the specific code and linked lists in general.

Linked Lists in general..:
1)..are "dynamic data" structures. That is they have the ability to grow and shrink according to the needs. Growing means that new areas of memory are acquired, and shrinking that areas of memory not needed any more are "recycled". For example in the code i posted, the "growing phase" takes place in line:
- 25 with the help of the "new" operator

2)..are dynamic data structures with fast prepending and appending and linear searching.

3)..are available through the c++ standard library too (see STL list)

In the posted code (valid in general I would say too)..:
1)..A list (CList) consists of links (CLinks). I use the big C in front, to imply a class notation.

2)..A Link contains 2 data members:
-A pointer to the next link of the list (line 9)
-A field of an integer Id which is stored in the actuall link. (line 8)
NOTE1: If u would like that your list is a list of some other kind of data instead of integers, a list of strings
for example u could replace this line with:
string _mystringId; (The underscore notation implies a class data member)

3)..A List object "owns-a"(in UML: agragation relationship) a Link object, which in terms of code is expressed by declaring a link as pointer data member of the list (line 30)

4)..When a new id is added to the list, this is done by allocating a new link and initializing it:
- with the id and
- the pointer to the next item.
The next item is the link that was previously at the beginning of the list. (It was pointed to by _pHead.) The new link becomes the head of the list and _pHead is pointed to it (pointer assignment). (prepending)

see lines 37 to 40:

alist.Add(5);  ==> CList: _pHead(5)->0

alist.Add(3);  ==> CList: _pHead(5)->pLink(3)->0

alist.Add(15); ==> CList: _pHead(5)->pLink(15)->pLink(3)->0

alist.Add(3);  ==> CList: _pHead(5)->pLink(3)->pLink(15)->pLink(3)->0

5)..In 4) is obvious that the integer 3 is contained in the list twice. I THOUGHT THAT U WANTED TO NOW HOW TO COMPARE THE LIST ELEMENTS WITH
SOME SPECIFIC KEY.
if we suppose the key is the integer 3 in this case THEN THE COMPARISON CAN BE DONE as in lines: 43 to 50

In line 43 the expression:

for (CLink const * pLink = alist.GetHead();...

is like

for (int i=0;...

pLink is a pointer to a constant Clink like i is a integer and like i has as its initial value 0, pLink has as its initial value the_pHead which is the head link that has as Id the value 5 in our example case. So the for loop begins from the head link and goes through all the other links checking if there is a link that has a value id equal to 3. Of course u can compare with any key u wish.

6) BUT I SEE THAT WHAT U WANTED IS TO COMPARE THE LINKS OF A LIST WITH EACH OTHER. For this u need to change the main function according to the following code (Lines 18 to 41 are important):

...
#include <cassert>
...
CList alist;
alist.Add(5);
alist.Add(3);
alist.Add(15);
alist.Add(3);
alist.Add(15);
int id = 3;

//Here we search if there is a link in the list containing the specific id which is the integer 3
for (CLink const * pLink = alist.GetHead(); pLink != 0; pLink = pLink->Next())
{
	if (pLink->Id() == id)
	std::cout<<"Ups an id value equal to: "<<id<<" already exists in the link: " <<pLink<<" of the list."<<std::endl;
	//break;
}      


//Here we check if within the list, there are any duplicates links: links that have the same Id value
CLink const * pLink1 = alist.GetHead();
CLink const * pLink2;

assert(pLink1 != NULL); // check if the list is empty 

while(pLink1!= NULL)
{ 
    pLink2 = pLink1->Next();   
	while(pLink2!= NULL)
	{ 
    	if(pLink1->Id() == pLink2->Id())
		{
			std::cout<<"UPS the data at adress "<<pLink1<<" of the simple linked list is the same as the data at adress: "<<pLink2<<" and both of them are equal to: " <<pLink2->Id()<<std::endl;
			break;	
		}
		else
		{
			pLink2 = pLink2->Next();
		}
	}
	pLink1 = pLink1->Next();
}

Now as u can see, I add on purpose to 2 links of the list the same value (twice 15 , twice 3) in order to see if the code can really find these duplicates links of the list. And the output of the program is the following:

Ups an id value equal to: 3 already exists in the link: 0x35810 of the list.
Ups an id value equal to: 3 already exists in the link: 0x32998 of the list.
UPS the data at adress 0x32928 of the simple linked list is the same as the data at adress: 0x358b0 and both of them are equal to: 15
UPS the data at adress 0x35810 of the simple linked list is the same as the data at adress: 0x32998 and both of them are equal to: 3

Sorry for writing so much, I hope I helped u get the idea now. :D

[ART01]

i wrote something like the following what i got from ur code and instructions, what i did is that a list is recieved by the function with declares two lists, the first list points to the next node of the list recieved and the other is used to insert nodes in it which suits the condition:

lista funzione(lista &l){
nodo* p;
lista t=0;


for(p=l;p!=0;p=p->next){
lista l1=p->next;
if(p->key>l1->key)
ins_coda(t,p->key);
delete l1;
}
return t;
}


int main(){


cout << " insersici la lista " << endl;
lista l=leggi();
lista t=funzione(l);
stampa(t);


system("pause");

bt it doesnt work as it is supposed to :(
if i m not clear enough in my reply, i can perhaps give u my yahoo messenger or MSN ID so we can talk about it right now.. or u can give me urs, whatever u prefer... we will post the results once we are done there.
plz help me coz i have exam very near and am stuck in this single prb for days now!! :((

[sidatra79]

Sorry but u kind of confused me....

Could you post a detailed description of the task, which you are supposed to code.
I would like you to describe it with words, and please only ...in English.
I need to understand what is the GOAL of your program!!!! Is it supposed to be part of a bigger problem or stand alone?
Are there any files as inputs involved??
Should its solution be object oriented?
Are there any constraints?
Do u have maybe a flow diagram?
Do u have a formal specification from your teachers/professors?
Could the goal be to MERGE 2 EXISTING LINKED LISTS AND DELETE ANY DUPLICATE LINKS(NODES) OF THESE LISTS?

Please clarify these.

Then I will have a look and I will try to help you.

Tu kapisti???? :icon_cheesygrin:

[ART01]

atlast! its working perfectly!!!
lemme make it clear for u;

i was supposed to write a program, which will read a unidirectional list from the user,will give this list as a parameter to the function which will scan the list, comparing every node with the one ahead of it, IF the node key is bigger than the one ahead of it, THEN this node will be inserted into a NEW list, and the function will give NEW list as the result...

the prb was actually with the For cycle i was using, i was thinking there might be some prb with the way i compare the nodes...the code i have used is as follows and works perfectly fine:

list function(list &l){
      nodo* p;
      list t=0;

      for(p=l;p->next!=0;p=p->next)/*this is where the error was, i had written,
for(p=l;p!=0;p=p->next)
making in to go into infinite loop*/

{

      if(p->key>p->next->key)*i thought the prb was here*/
      ins_tail(t,p->key);

     }
       return t;
      }

int main(){
      cout << " insert the list elements" << endl;
    list l=read();
    list t=function(l);
   print(t);    
    system("pause");
       }

i know its a silly prb bt im new to programming,
BTW sidarta79, the way u write codes, shows u are an excellent programmer, r u working, or a student if yes which year and country?

its said "capisic?" :D

[sidatra79]

mi capivo :D
I was in sicely for holidays this summer... :D

I am happy u found the problem!!!
Good luck in your exam.

I am a student(in Germany ma soi greco :D ) and I am writing my thesis at the moment, where I have to use C++ effectively..., that's why I am trying to improve my code continuously. However I learn all the time too beacause I am not so excellent :)

P.s. don't forget to close thread by marking it as solved :)