• 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

Reversing a Linked List

 
Ranch Hand
Posts: 52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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("---------------");


}


}
 
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
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
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!

 
reply
    Bookmark Topic Watch Topic
  • New Topic