• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Linked Lists, Nodes, Quicksort

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi everyone,

I am using the above for the first time and I am getting quite lost.

We've been given the following line...

public Node less (int n, Node l)

We have to use recursion to write a method which takes as input a linked list and a number and return a list of elements smaller than that number.

Can anyone help, even with the next line?

If only it was like Filter in Haskell.

Any pointers on linked lists, nodes or quicksort would be great.
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Fixed.

 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

We've been given the following line...

public Node less (int n, Node l)

We have to use recursion to write a method which takes as input a linked list and a number and return a list of elements smaller than that number.



I really hate homework assignments that does this. When the instructor gives you part of the code, it tends to cause more confusion than actually help.

You need to understand what the line is. The paragraph is asking you for "a method which takes as input a linked list and a number and return a list of elements". So, based on the line given, and the description, what part of it defines a method, and what defines a linked list?

Henry
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Charlie Jackpot:
Fixed.




No offense, but if you are going to provide a fake name... at least, make a decent attempt at creating one. Please fix your screen name, obviously fake names are not allowed.

Henry
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think "Node l" refers to the linked list.
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Charlie Jackpot:
I think "Node l" refers to the linked list.



Okay good. And n is referring to the number to be compared to. With this you can form the method.

Now, did your instructor teach you the algorithm for the quick sort? Can you form the body of the method, from what you were taught?

Henry
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Henry Wong:


Okay good. And n is referring to the number to be compared to. With this you can form the method.

Now, did your instructor teach you the algorithm for the quick sort? Can you form the body of the method, from what you were taught?

Henry



Well, he gave us the quicksort method but used it on an Array.

I am not sure how to use it with Linked Lists.

EDIT:

I found this....

public static void Quicksort(int A[], int f, int l)
{
if (f >= l) return;
int pivot_index = partition(A, f, l);
Quicksort(A, f, pivot_index);
Quicksort(A, pivot_index+1, l);
}
[ November 13, 2008: Message edited by: Charlie Jackson ]
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Charlie Jackson:


Well, he gave us the quicksort method but used it on an Array.

I am not sure how to use it with Linked Lists.



Well, it is the technique that is important. If you understood how it worked with an array, it is easily translated to a linked list. Just take a shot at it, provide the code here, and we can give you hints in the right direction.

Now... Did your instructor provide you with the implementation for Node? Or are you expected to implement your own linked list too?

Henry
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Henry Wong:


Well, it is the technique that is important. If you understood how it worked with an array, it is easily translated to a linked list. Just take a shot at it, provide the code here, and we can give you hints in the right direction.

Now... Did your instructor provide you with the implementation for Node? Or are you expected to implement your own linked list too?

Henry



I don't understand it for Array either

public static void main(String argv[])
{
int A[] = new int[argv.length];
for (int i=0 ; i < argv.length ; i++)
A[i] = Integer.parseInt(argv[i]);
Quicksort(A, 0, argv.length-1);
for (int i=0 ; i < argv.length ; i++)
System.out.print(A[i] + " ");
System.out.println();
}
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

I don't understand it for Array either



Well, does any of your textbooks go through it? Obviously, you can't code something, if you don't understand the algorithm. There is no black magic here -- you have to understand first.

Henry
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have my Node implementation.

Can you not talk me through it?

I don't want solutions, maybe just a push in the right direction.
 
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There appear to be problems about sorting LinkedLists; the Collections class copies the list into an array.
The Node reference presumably points to the first node in the linked list which has the specified value.
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Node Class:



Sort Class:


This is what I have so far, fairly happy with "less" and "more".

"join" is joining the two lists, any ideas?
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Campbell Ritchie:
There appear to be problems about sorting LinkedLists; the Collections class copies the list into an array.



There aren't problems sorting a LinkedList, the problem is that the algorithm used in Collections.sort() depends on a random access data structure. That's not an issue if a different algorithm is chosen.
 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Aha! So that only applies to that one algorithm?
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I've finished my "sort" class.

I'll post up my final results and my "test" class today.

 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Charlie Jackson:
I've finished my "sort" class.

Well done
 
Charlie Jackson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, the solution:


NODE



SORT







Did I post this in the right thread, is this Beginner Java?
[edit]Add code tags. CR[/edit]
[ November 19, 2008: Message edited by: Campbell Ritchie ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic