please help me understand my linked list query!

[loveforfire33]

hi,

im currently revising linked lists for my exams - but i cant quite understand the reasoning behind using current or current.next in the following examples

in the example below we are adding to the back of a linked list

void addToBack(int value)    
{    // make a new element   
 Element newElement =new Element(value) ;
    if (myList == null)     
  // add to empty list     
   myList = newElement ;  
  else        {        // scan to end of list  ]
      Element current = myList ;       
 while ([B]current.next[/B] != null)   
         current = current.next ;     
   // add to end of list   
     current.next = newElement ; 
        }    
}  // end of addToBack method

here we are removing the last element from the linked list

int removeLastElement()  
  {    if (myList == null)      
  REPORT AN ERROR   
 else       
 {        Element current = myList ;    
    Element previous = null ;        
while ([B]current.next[/B] != null) 
           {            previous = current ;  
          current = current.next ;          
  }        
int value = current.data ;     
   if (previous == null)         
   myList = null ;     
   else         
   previous.next = null ;
        return value ;       
 } 
  } // end of removeLastElement method

in the example below we are removing the element marked X

{    Element current = myList ; 
   Element previous = null ; 
   boolean isFound = false ;
     while (([B]current[/B] != null) && (!isFound))    
    {        if (current.data == X)     
       isFound = true ;       
 else            
{            previous = current ;      
      current = current.next ;        
    }     
   }
    if (!isFound)       
 REPORT “ELEMENT NOT FOUND” 
   else if (previous == null)        
 myList = current.next ;    
else     
    previous.next = current.next ;     }

and finally the code below searches for the value X

boolean isFound = false ;
Element current = myList ;
while (([B]current [/B]!= null) && (!isFound)) 
   {    if (current.data == X)      
  isFound = true ;    
else        
current = current.next ;    }

as you can see from the code segments above some of the while loops use current and some use current.next - i have copied these codes from my lecturers slides but i am unable to contact him at the moment and would really appriciate it if anyone can tell me why in some instances current is used, and some current.next is used

thanks

[JerryShaw]

Maybe this link wil help you understand linked lists.

http://www.c-sharpcorner.com/UploadFile/jeradus/UsingLinkedListInCS11102005005525AM/UsingLinkedListInCS.aspx

Too bad they are still teaching these prehistoric methods.
Since Generics were introduced, link lists are pretty much useless in the real world.

// Jerry

[thoughtcoder]

Too bad they are still teaching these prehistoric methods.
Since Generics were introduced, link lists are pretty much useless in the real world.

This is a very wrong thing to say. Generics is a feature orthogonal to the question of what data structure to use for collections of things.

[JerryShaw]

I don't think it is a wrong thing to say at all.

LinkedList<T> is a generic replacement for the old style coded Linked List.

[thoughtcoder]

What? So you're saying something different than what you wrote -- not that linked lists are useless but that one is already written for you. Too bad it's the bad of linked list, the mutable kind.

[loveforfire33]

thanks for the replys,

outdated or not, its what i have to understand for my exams! the whole concept and ideas of linked lists i am fine with, i can programme them aswell.

but can anyone see any reason why current.next in the examples above could not be replaced with current and visa versa?

is it possible it is something to do with the programmes efficiency - as i cant seem to understand how it makes any difference if its current or current.next

[Narue]

>Since Generics were introduced, link lists are pretty much useless in the real world.
It's certainly true that you should prefer a standard library to hand-rolled code in most real world cases. However, just because there's a library that will do it for you doesn't mean you don't still need to learn how to do it manually. The understanding you acquire from implementing something is far more valuable than the thing itself.

Writing a linked list class teaches you the trade-offs that need to be made, which helps you understand the libraries better. If you've written a linked list, you're in a better position to know when to use one. And of course, if you suddenly find yourself unable to use the library for any reason, you're not caught out with your pecker flapping in the wind. You can just replace it.

>but can anyone see any reason why current.next in the
>examples above could not be replaced with current and visa versa?
Yep. In your addToBack method:

while (current.next != null)   
    current = current.next ;     

current.next = newElement ;

If the loop reaches nulll, the subsequent statement will throw a null exception. The intention of the loop is to end on the last valid node, then append to it.

In your removeLastElement method:

while (current.next != null) 
{
    previous = current ;  
    current = current.next ;          
}

Once again if the loop reaches null, it's too late. The intention of this loop is to find both the last valid node (current) and the node before it (previous). The last valid node is then removed by setting the next link in previous to null (or the whole list if there was only one node). If you wait until current is null, then current no longer points to anything in the list and previous points to the last valid node.

In the specific node removal code:

while ((current != null) && (!isFound))    
{
    if (current.data == X)     
        isFound = true ;       
    else            
    {
        previous = current ;      
        current = current.next ;        
    }     
}

In this loop, you want to go all the way to null because you're looking for a node and if current reaches null, the node doesn't exist. If you stop the loop using current.next != null , you won't check the data of the last node.

In your search code:

while ((current != null) && (!isFound)) 
{
    if (current.data == X)      
        isFound = true ;    
    else        
        current = current.next ;
}

Once again, stopping at the last node will mean it doesn't get checked. This is the easiest case as you don't need to save any data, you don't need to make any changes to the structure of the list, and the only operation is "go from beginning to end and stop if a match is found".

[loveforfire33]

absolutly amazing, thank you so much makes alot of sence now :)