3 Replies - 5148 Views - Last Post: 01 December 2007 - 10:58 AM Rate Topic: -----

#1 jreibe3000  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 65
  • Joined: 08-June 07

Java singly linked lists

Post icon  Posted 30 November 2007 - 04:12 PM

Hello coders,

I have a test Monday in my Java class. On the test topics my professor lists the following under the topic of singly linked lists:

o search for a node

return pointer to Node where found

return Boolean true if found, false otherwise

We have done very little on linked lists in class, so I don't know what these will encompass. Could anyone out there provide a bit of expertise or guidance? Much appreciated as always.

Thank you,
Jake

Is This A Good Question/Topic? 0
  • +

Replies To: Java singly linked lists

#2 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 204
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Java singly linked lists

Posted 30 November 2007 - 04:52 PM

is this for Java or C/C++? Java does not have pointers, the way that the term is meant to be used.

Do you understand the concept of a linked list?
Was This Post Helpful? 0
  • +
  • -

#3 lifeRoot  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 23
  • Joined: 01-April 07

Re: Java singly linked lists

Posted 30 November 2007 - 06:34 PM

Well, a linked list is just a list of "objects" that are linked together somehow (simple eh?)... In Java, linked lists are usually represented by objects of a class that represents a node:

class node {
  
	int value;
	node next;
 
	...
}



The value "next" just stores address (in memory) of the next object, so you could call it a "pointer"... notice how "next" is the same type as the class...
Lets make two nodes:

node n1 = new node();
node n2 = new node();



Now, lets make the list in this order: n1 --> n2 --> null
(Generally, the end of linked list is reached when next=null)

n1.next = n2;
n2.next = null;



Now, you wouldn't want to give each and every node a name (like I just did) because sometimes you will have 1000's of nodes!! I just wanted to show you how it works without confusing you :). You will probably be creating nodes this way:

PSUEDO-CODE
// Set everything up...
node head = new node(); // points to the beginning of the list... lets just add a node here.
node end = head; // points to the end of the list, which is head in this case.

// add nodes loop
loop {

	// this makes end.next point to a new node instead of null
	end.next = new node(); 
	
	// now we set end to that new node, which is the end :)
	end = end.next;

	// give the node a value
	end.int = someValue;

	// make sure we set the last "pointer" to null!!
	end.next = null;
}



Once you have a list set up, searching is easy! Just start at the head, and see if that node's value is what you want, if not, move to the next node. You are done when you find what you want or hit a null!

ex.
// make a temporary node
// we do this so we won't change the head
node current = head;

// loop through the linked list...
while ( current != null ) {

   // check the value of the current node...
   if ( current.value == target )
	  // WE FOUND ARE NUMBER! "current" is a pointer to that node
	  // we can return "current" or "true"

   // else, we have to try the next node...
   else
	  current = current.next;

}

// If we are out of the loop and still didn't find our target,
// then it wasn't in the list...
return false;



There are many ways to create, search, and traverse linked lists, but hopefully I have presented you with the most simple perspective.

That's about it! Hope this helps :)

~ Chris

This post has been edited by lifeRoot: 30 November 2007 - 06:34 PM

Was This Post Helpful? 0
  • +
  • -

#4 jreibe3000  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 65
  • Joined: 08-June 07

Re: Java singly linked lists

Posted 01 December 2007 - 10:58 AM

Okay I think I'm starting to get a grasp on this data structure. However, I'm still not sure what the teacher means by "return pointer to Node where found" after searching. I see how your saying to just return true if the target is found or false if it's not in the linked list, but what does this whole return pointer deal mean? thank you in advance.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1