Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Sorting Doubly Linked Lists
New Posts  All Forums:Forum Nav:

Sorting Doubly Linked Lists

post #1 of 4
Thread Starter 
import java.io.*;

public class A2Q1 {

static String inputFile = "unsorted.txt";
static String outputFile = "sorted.txt";

public static void main(String[] args){
DoubleLinkedList list = new DoubleLinkedList();
getInput(list);

System.out.println("Original List Forwards");
list.displayForward();

System.out.println("\
Original List Reversed");
list.displayReverse();

System.out.println();

list.sort();

}// end main

public static void getInput(DoubleLinkedList list){
String line;

try{
BufferedReader input = new BufferedReader(new FileReader(inputFile));

line = input.readLine();

while(line!=null){

list.add(Integer.parseInt(line));

line = input.readLine();

}// end while
}catch(IOException ioe){
System.out.println(ioe.getMessage());
}
}// end getInput()
}

public class DoubleLinkedList {
private Node first, last;

public DoubleLinkedList(){
first = null;
last = null;
}

public boolean isEmpty(){
return (first == null);
}

public void add(int num){

Node newNode = new Node(num, null);
if(isEmpty())
last = newNode;
else
first.setPrev(newNode);
newNode.setNext(first);
first = newNode;
}

public void sort(){
Node current = first;
Node previous = null;

while(current != null ){
System.out.println(current.getData());
previous = current;
current = current.getNext();
}


}

public void displayForward(){
Node current = first;
//System.out.println(current);
while(current!=null){
System.out.print(current.getData() + " ");
current = current.getNext();
}
}

public void displayReverse(){
Node current = last;
while(current!=null){
System.out.print(current.getData() + " ");
current = current.getPrev();
}
}

public String toString(){
String result = "";
Node current = first;

while(current != null){
result += current.getData() + " ";
current = current.getNext();
}
return result;
}
}

public class Node {

private Node next;
private Node previous;
private int data;

public Node(int data, Node next){
this.data = data;
this.next = next;
}

public int getData(){
return data;
}

public Node getPrev(){
return previous;
}

public Node getNext(){
return next;
}

public void setPrev(Node previous){
this.previous = previous;
}

public void setNext(Node next){
this.next = next;
}
}

So this is my code im reading in a list of ints which must be stored first then sorted in the same list. the sort method must be called from main like list.sort() and can not have any parameters. Im sure i can figure out how to rearrange the links but im stuck on the while look in my sort method.
ive tried
while(current!=null && current.getData()<current.getnext().getData())
ive tried current.getData() <last.getData() i think ive tried all ways of testing which entry is larger or smaller than the next but nothing iterates all the way through the list. If i can figure that out then the links should be no problem.
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #2 of 4
ok, this one is a little more complex than the other one I helped you on. This will also work with a linear-linked list. I am merely using a bubble sort for sorting the list, which is fine for relatively small arrays or lists or whatever you are sorting. I used a piece of paper for this code...let me know if you need me to work this out using a compiler.

Code:
ListNode p;
 
if(list != null)
     p = list.getFirstNode();    //get the first node of the list

while(p != null){
       
      int temp = p.getInfo();
      ListNode c = p;

      while(c != null){     
             if (c.getNext() != null)               
                    ListNode t = c.getNext();                          
             if(t.getInfo() < temp){            //comparison here
                    p.setInfo(t.getInfo());        //swap here
                    t.setInfo(temp);             //swap here
                    temp = p.getInfo();
              }       
             c = c.getNext();
            }
        p = p.getNext();
}

Edited by surfbumb - 5/28/11 at 1:58pm
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
post #3 of 4
Quote:
Originally Posted by surfbumb View Post
ok, this one is a little more complex than the other one I helped you on. This will also work with a linear-linked list. I am merely using a bubble sort for sorting the list, which is fine for relatively small arrays or lists or whatever you are sorting. I used a piece of paper for this code...let me know if you need me to work this out using a compiler.

Code:
ListNode p;
 
if(list != null)
     p = list.getFirstNode();    //get the first node of the list

while(p != null){
       
      int temp = p.getInfo();
      ListNode c = p;

      while(c != null){     
             if (c.getNext() != null)               
                    ListNode t = c.getNext();                          
             if(t.getInfo() < temp){            //comparison here
                    p.setInfo(t.getInfo());        //swap here
                    t.setInfo(temp);             //swap here
                    temp = p.getInfo();
              }       
             c = c.getNext();
            }
        p = p.getNext();
}
That code would likely crash with an access violation if c.getNext() == NULL, because T would never get set, although that's not really possible because the getNext() function isn't returning a pointer, but rather a copy of a node.
So, there's no point in checking p or c against null if you're not using pointers, as an instance of an object will never be null.

The problem I'm seeing with both the original code in the OP, and sample above is mostly that this link list is really just pointing around copies of everything. There needs to be pointers and references being used in most of these cases, and I see almost none of that.
Edited by lordikon - 5/28/11 at 9:53pm
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
post #4 of 4
lordikon, yeah this was on a piece of paper...I later did it on my compiler and changed the code around a bit last night as I was getting errors...it is working now.
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Sorting Doubly Linked Lists