This week's book giveaway is in the OCPJP forum.
We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Reversing a Linked List Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Reversing a Linked List" Watch "Reversing a Linked List" New topic
Author

Reversing a Linked List

Teri Fisher
Ranch Hand

Joined: Jan 07, 2008
Posts: 52
I need to use a linked list to create a list, make a copy of the list, then reverse the list and pull out any duplications. I am having trouble reversing my list and not sure how to pull out the duplicates. Do I need more methods and should I use an array? If I add an array I am not sure how to implement that. Thanks in advance for any help.

public class ListElement2
{
private ListElement2 next;
private Object data;

//default constructor
public ListElement2()
{
next = null;
data = null;
}

//parameterized constructors
public ListElement2(Object d)
{
next = null;
data = d;
}

public ListElement2(Object d, ListElement2 lnk)
{
next = lnk;
data = d;
}

//setter
public void setData(Object d)
{
data = d;
}

public void setNext(ListElement2 lnk)
{
next = lnk;
}

//getters
public Object getData()
{
return data;
}

public ListElement2 getNext()
{
return next;
}

//display list method
public void displayList()
{
ListElement2 lnk = this;//keep this head reference
while(lnk!= null)//this is the end of the list
{
System.out.print(lnk.getData()+ " ");
lnk = lnk.getNext();//increment list
}
}

public int count(ListElement2 head)
{
int numNodes = 0;

ListElement2 lnk = head;

while(lnk!=null)
{
numNodes++;
lnk=lnk.getNext();
}

return numNodes;
}//end count

public void addNodeAfter(Object element)
{
next = new ListElement2(element, next);
}

public static ListElement2 listCopy(ListElement2 source)
{
ListElement2 copyHead;
ListElement2 copyTail;

//Handle special case of an empty list
if (source == null)
return null;

//make the first node for the new list
copyHead = new ListElement2(source.data, null);
copyTail = copyHead;

//make the rest of the nodes for the list
while (source.next != null)
{
source = source.next;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.next;
}

//return head reference for new list
return copyHead;
}
____________________________________________________

public class ListElementDemo2 {

public static void main(String args[])
{ //Data list
ListElement2 head = new ListElement2(2);
ListElement2 one = new ListElement2(4);
ListElement2 two = new ListElement2(6);
ListElement2 three = new ListElement2(8);
ListElement2 four = new ListElement2(6);
ListElement2 five = new ListElement2(8);

ListElement2 current = head;//put head in a safe
current.setNext(one);
current = current.getNext();
current.setNext(two);
current = current.getNext();
current.setNext(three);
current = current.getNext();
current.setNext(four);
current = current.getNext();
current.setNext(five);

//display contents of the list
head.displayList();
System.out.println();
int num=head.count(head);
System.out.println("---------------");
//display how many nodes in the list
System.out.println("Number of nodes: "+num);
System.out.println("---------------");

//making a copy of the list
ListElement2 newList;
newList = ListElement2.listCopy(head);
System.out.println("Results of the copy method: ");
newList.displayList();
System.out.println();
System.out.println("---------------");


}


}
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

Take a look at your listCopy() method. Notice how your are using a loop to cycle through the first list, creating a new node for each source, and then, connecting the tails correctly.

Now imagine if you didn't do the last part. Instead of connecting it to the tail, you connect the new node to point to the head node (copyhead), and then change the copyhead variable to the new node. What will that do with the new list?

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39478
    
  28
Please use code tags round quoted code.

Sounds like homework . . .

If you go through the Collections class and look for the sort method, you find that it actually gets the List into an array, sorts the array, and then re-creates the List from the array. You could do that, but it is probably simpler to pull out the first member of your existing List, add it as the first member of a new List, and delete it from the old List.
Then you pull out the first member of the existing List, add it as the first member of the new List, and delete it from the old List.
Then you pull out the first member of the existing List, add it as the first member of the new List, and delete it from the old List.
Then you pull out the first member of the existing List, add it as the first member of the new List, and delete it from the old List.
etc.

You can get rid of duplicates by checking whether the List already contains that particular member (or more precisely a member which returns true on the equals() method), and then not adding it. You could create a second List for duplicates only.
Teri Fisher
Ranch Hand

Joined: Jan 07, 2008
Posts: 52
Henry,
I thought I would try your approach first since we are supposed to take the quickest approach with what we have in our code now but I guess I am still confused with rearranging my listCopy method. Here is what I have started with. Do I need to add an array in main to do this?
Thanks!

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Reversing a Linked List