9 Replies - 1385 Views - Last Post: 17 April 2013 - 07:46 PM Rate Topic: -----

#1 dale1314   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 07-April 13

Question: Singly linked list

Posted 14 April 2013 - 01:20 AM

I have a question about linked list, how do I arrange my list(the list contains names with average score) from highest to lowest then display it? Then display the name with the highest score. e.g(Highest score: "name here").
Is This A Good Question/Topic? 0
  • +

Replies To: Question: Singly linked list

#2 Plasticcaz   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 16
  • Joined: 14-April 13

Re: Question: Singly linked list

Posted 14 April 2013 - 06:28 AM

Good question... I think you'll have to think about it! :wink:
Was This Post Helpful? 0
  • +
  • -

#3 phlegmatic   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 12
  • Joined: 15-March 10

Re: Question: Singly linked list

Posted 14 April 2013 - 07:03 AM

You'll want to sort your list based on the value you want to order by. If this is an assignment for class, I'm willing to bet that your book mentions sorting methods somewhere close by. If that isn't the case, here is some psuedo code for a quicksort algorithm from wikipedia:

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls



You will need to make some modifications to have the algorithm work with your code, namely the 'append' and the 'concatenate', and swapping array for linked list, but I trust you will be able to figure it out :)/>

After they are sorted, you can do a for loop to print it all out in order.

for(int i = linkedList.size(), i > 0, i--) {
    //print out the value from the last object
    //down to the first object
}


Was This Post Helpful? 0
  • +
  • -

#4 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8379
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Question: Singly linked list

Posted 14 April 2013 - 10:05 PM

No need to re-invent the wheel
The Collections class has a static sort() method that will sort any class that implements Collections as the LinkedList class
Was This Post Helpful? 0
  • +
  • -

#5 darek9576   User is offline

  • D.I.C Lover

Reputation: 203
  • View blog
  • Posts: 1,734
  • Joined: 13-March 10

Re: Question: Singly linked list

Posted 15 April 2013 - 01:42 AM

He is talking about a Singly Linked List and java.util.LinkedList is based on Doubly Linked List, therefore we can assume he is talking about a custom singly linked list.

@OP: you should also check out 2 interfaces: Comparable and Comparator.
Was This Post Helpful? 0
  • +
  • -

#6 dale1314   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 07-April 13

Re: Question: Singly linked list

Posted 17 April 2013 - 05:57 AM

Im thinking of swapping like this
temp = curr.next;
curr.next = temp.next;
temp.next = curr;

but i cant get the right codes.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11223
  • View blog
  • Posts: 19,242
  • Joined: 19-March 11

Re: Question: Singly linked list

Posted 17 April 2013 - 06:27 AM

View Postpbl, on 15 April 2013 - 12:05 AM, said:

No need to re-invent the wheel



Unless you're trying to learn to make wheels....

@OP: I'd suggest you start with a simple bubble sort. That should work for a linked list scenario, and it's easy enough to implement. The idea is, you repeatedly iterate through the list, and check whether one pair of items is out of order. If they are out of order, swap them. This is terribly inefficient, but it's a good way to get started thinking about sorting.

Your swap idea would be fine for elements of an array, but it's not going to work for a list. Remember that a list is based on its links: each node "knows" its position in the list. Suppose you have the SLL (a, c, b, d), where a is the head. You'd like to swap the middle two items to get the list into correct order. What nodes are you going to have to touch in order to do this? Describe what's going to have to change about each of them.
Was This Post Helpful? 0
  • +
  • -

#8 dale1314   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 07-April 13

Re: Question: Singly linked list

Posted 17 April 2013 - 06:44 AM

Like I have 5 elements in my list. Then im gonna swap my head to my 3rd element, like that.
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11223
  • View blog
  • Posts: 19,242
  • Joined: 19-March 11

Re: Question: Singly linked list

Posted 17 April 2013 - 06:58 AM

Your swap isn't going to work in that case or any other.

Think about it for a minute. You have nodes a, b, c, and d in a singly linked list. What is it that makes them be in that order? If they were in an array, it would be a fact about the array: the fact that array[0] points to a, array[1] points to b, etc. In a linked list, the order is determined by facts within the nodes, so your array swap isn't going to work.
Was This Post Helpful? 1
  • +
  • -

#10 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8379
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Question: Singly linked list

Posted 17 April 2013 - 07:46 PM

View Postdale1314, on 17 April 2013 - 08:57 AM, said:

Im thinking of swapping like this
temp = curr.next;
curr.next = temp.next;
temp.next = curr;

but i cant get the right codes.

That would screw up your backward/forward pointers
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1