DaniWeb Forum Index > Software Development > C++

C++ RSS

Basic question about linked lists

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Sep 2008

Posts: 12

Reputation: ART01 is an unknown quantity at this point

Solved Threads: 0

ART01

Offline

Newbie Poster

Basic question about linked lists

Sep 28th, 2008

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

•

Join Date: May 2007

Posts: 1,859

Reputation: twomers has a spectacular aura about

Solved Threads: 55

twomers

Online

Posting Virtuoso

Re: Basic question about linked lists

Sep 28th, 2008

Maybe something like:

 Help with Code Tags 
 cpp Syntax (Toggle Plain Text) 
nodo *p1, *p2;
 
p1 = List;
p2 = List->next;
 
if ( p1->key == p2->key ) // or p1->key == p1->next->key
 // do this...
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.

I blag!?
"Mr Kitty, you have to live in the attic now. Here, write a diary."
I am the Walrus!

•

Join Date: Sep 2008

Posts: 12

Reputation: ART01 is an unknown quantity at this point

Solved Threads: 0

ART01

Offline

Newbie Poster

Re: Basic question about linked lists

Sep 28th, 2008

•

Originally Posted by twomers

Maybe something like:
Help with Code Tags

cpp Syntax (Toggle Plain Text)
nodo *p1, *p2;
 
p1 = List;
p2 = List->next;
 
if ( p1->key == p2->key ) // or p1->key == p1->next->key
 // do this...
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.

•

Join Date: May 2007

Posts: 1,859

Reputation: twomers has a spectacular aura about

Solved Threads: 55

twomers

Online

Posting Virtuoso

Re: Basic question about linked lists

Sep 28th, 2008

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...

 Help with Code Tags 
 cpp Syntax (Toggle Plain Text) 
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 );
}
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 blag!?
"Mr Kitty, you have to live in the attic now. Here, write a diary."
I am the Walrus!

•

Join Date: Sep 2008

Posts: 12

Reputation: ART01 is an unknown quantity at this point

Solved Threads: 0

ART01

Offline

Newbie Poster

Re: Basic question about linked lists

Sep 28th, 2008

•

Originally Posted by 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...
Help with Code Tags

cpp Syntax (Toggle Plain Text)
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 );
}
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...

•

Join Date: May 2007

Posts: 1,859

Reputation: twomers has a spectacular aura about

Solved Threads: 55

twomers

Online

Posting Virtuoso

Re: Basic question about linked lists

Sep 28th, 2008

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.

Last edited by twomers; Sep 28th, 2008 at 12:51 pm. Reason: Semantics error

I blag!?
"Mr Kitty, you have to live in the attic now. Here, write a diary."
I am the Walrus!

•

Join Date: Sep 2008

Posts: 12

Reputation: ART01 is an unknown quantity at this point

Solved Threads: 0

ART01

Offline

Newbie Poster

Re: Basic question about linked lists

Sep 28th, 2008

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.....

•

Join Date: Feb 2008

Posts: 114

Reputation: sidatra79 is an unknown quantity at this point

Solved Threads: 8

sidatra79

Offline

Junior Poster

Re: Basic question about linked lists

Sep 28th, 2008

Here sth might be what u r looking for:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
/////////////
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
/////////////
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.

•

Join Date: Sep 2008

Posts: 12

Reputation: ART01 is an unknown quantity at this point

Solved Threads: 0

ART01

Offline

Newbie Poster

Re: Basic question about linked lists

Sep 28th, 2008

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...

Success is not final, failure is not fatal: it is the courage to continue that counts.

•

Join Date: Feb 2008

Posts: 114

Reputation: sidatra79 is an unknown quantity at this point

Solved Threads: 8

sidatra79

Offline

Junior Poster

Re: Basic question about linked lists

#10

Sep 29th, 2008

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:

Help with Code Tags

c++ Syntax (Toggle Plain Text)

#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:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
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
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:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
for (CLink const * pLink = alist.GetHead();...
for (CLink const * pLink = alist.GetHead();...

is like

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
for (int i=0;...
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):

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
...
#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();
}
...
#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:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
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
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