-
April 28th, 2012, 05:23 PM
#1
Linked List question
Ok, so this is a standard linked list. The output is shown at the bottom. How to I access the input and sort it by, let's say, ISBN number? So that it's going to display it.
I have no idea how to do this.
Code:
class LinkedList1
{
private class Node
{
String value;
Node next;
Node(String val, Node n)
{
value = val;
next = n;
}
Node(String val)
{
// Call the other (sister) constructor.
this(val, null);
}
}
private Node first; // list head
private Node last; // last element in list
/**
Constructor.
*/
public LinkedList1()
{
first = null;
last = null;
}
/**
The isEmpty method checks to see
if the list is empty.
@return true if list is empty,
false otherwise.
*/
public boolean isEmpty()
{
return first == null;
}
public int size()
{
int count = 0;
Node p = first;
while (p != null)
{
// There is an element at p
count ++;
p = p.next;
}
return count;
}
public void add(String e)
{
if (isEmpty())
{
first = new Node(e);
last = first;
}
else
{
// Add to end of existing list
last.next = new Node(e);
last = last.next;
}
}
public void add(int index, String e)
{
if (index < 0 || index > size())
{
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}
// Index is at least 0
if (index == 0)
{
// New element goes at beginning
first = new Node(e, first);
if (last == null)
last = first;
return;
}
// Set a reference pred to point to the node that
// will be the predecessor of the new node
Node pred = first;
for (int k = 1; k <= index - 1; k++)
{
pred = pred.next;
}
// Splice in a node containing the new element
pred.next = new Node(e, pred.next);
// Is there a new last element ?
if (pred.next.next == null)
last = pred.next;
}
public String toString()
{
StringBuilder strBuilder = new StringBuilder();
// Use p to walk down the linked list
Node p = first;
while (p != null)
{
strBuilder.append(p.value + "\n");
p = p.next;
}
return strBuilder.toString();
}
public String remove(int index)
{
if (index < 0 || index >= size())
{
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}
String element; // The element to return
if (index == 0)
{
// Removal of first item in the list
element = first.value;
first = first.next;
if (first == null)
last = null;
}
else
{
// To remove an element other than the first,
// find the predecessor of the element to
// be removed.
Node pred = first;
// Move pred forward index - 1 times
for (int k = 1; k <= index -1; k++)
pred = pred.next;
// Store the value to return
element = pred.next.value;
// Route link around the node to be removed
pred.next = pred.next.next;
// Check if pred is now last
if (pred.next == null)
last = pred;
}
return element;
}
public boolean remove(String element)
{
if (isEmpty())
return false;
if (element.equals(first.value))
{
// Removal of first item in the list
first = first.next;
if (first == null)
last = null;
return true;
}
// Find the predecessor of the element to remove
Node pred = first;
while (pred.next != null &&
!pred.next.value.equals(element))
{
pred = pred.next;
}
// pred.next == null OR pred.next.value is element
if (pred.next == null)
return false;
// pred.next.value is element
pred.next = pred.next.next;
// Check if pred is now last
if (pred.next == null)
last = pred;
return true;
}
public static void main(String [] args)
{
LinkedList1 ll = new LinkedList1();
ll.add("Book1, ISBN12345");
ll.add("Book2, ISBN28439");
ll.add("Book3, ISBN39482");
ll.add("Book4, ISBN38372");
ll.add("Book5, ISNN93827");
System.out.println("The members of the list are:");
System.out.print(ll);
}
}
-
April 29th, 2012, 03:29 AM
#2
Re: Linked List question
A easy way is to convert your LinkedList to an array (or ArrayList) and the use the java.util.Arrays.sort() method (or java.util.Collections.sort() method) to do the sort and then convert the sorted array (or ArrayList) back to your LinkedList.
The best way is to get your class to implement the java.util.List interface and then use java.util.Collections.sort() method to do the sort.
The hard way is to write your own sort class that can work with your LinkedList class.
-
April 29th, 2012, 04:23 PM
#3
Re: Linked List question
Originally Posted by keang
A easy way is to convert your LinkedList to an array (or ArrayList) and the use the java.util.Arrays.sort() method (or java.util.Collections.sort() method) to do the sort and then convert the sorted array (or ArrayList) back to your LinkedList.
The best way is to get your class to implement the java.util.List interface and then use java.util.Collections.sort() method to do the sort.
The hard way is to write your own sort class that can work with your LinkedList class.
Ok, Collections.sort sounds better. I want to do it using a linked list.
Like this?
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class MainClass {
public static void main(String args[]) throws Exception {
List list = Arrays.asList("a","c","b");
Collections.sort(list);
for (int i = 0, n = list.size(); i < n; i++) {
if (i != 0)
System.out.print(", ");
System.out.print(list.get(i));
}
System.out.println();
}
}
I have several things in the nodes, though. How does it know what is what? It needs to sort the ISBN only.
Last edited by XodoX; April 29th, 2012 at 04:41 PM.
-
April 30th, 2012, 07:10 AM
#4
Re: Linked List question
You use the 2 parameter sort method and pass in a Comparator that defines the ordering you require.
-
May 5th, 2012, 05:53 PM
#5
Re: Linked List question
No, never-mind about that. I need a list interface then for collections.sort. I'm teaching this myself and it's the linked list chapter, so I can't use anything else. I have some books and it needs to display them. The sorting can be added later. So that's a simple linked list then, is it not? I don't need add or remove because the input is already in there.
Code:
public class Node
{
Books book;
Node next;
public Node( Books bookA)
{
book = bookA;
}
}
public class MyLinkedList()
{
private Node head;
public MyLinkedList(Books bookA)
{
head = new Node(bookA);
}
public add(Books bookA)
{
MyLinkedList current = this;
// here
while ( current.next != NULL )
{
current = current.next;
}
current.next = new Node(bookA);
}
}
That's the short version. So that's one book. I'm not sure about the adding of additional books. How would I do this? But this would require user input. Or should I just remove the add/remove etc. from the list in #1 and use that instead? ughh, this is confusing.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|