[Sythra]

I would like to reverse a DLL, but the following code of reverseList eliminates part of the string and only keeps the last string.

If you can point me to a thorough explanation of DLL that may help. I don't believe I have fully comprehended the logic in it.

Here is my code:

import java.util.*;

public class DLL<E extends Comparable<E>> {

    private class Cell {
	E value;
	Cell next, prev;

	Cell (E v, Cell n, Cell p) {
	    value=v; next=n; prev=p; //flinks and blinks
	}

	Cell () {     // used only to create header cell in a list
	              // that's initially empty
	    next=prev=this;
	}
    }

    private Cell header = new Cell();

    public boolean isEmpty() {

	return header.next == header;
    }

    private E delete(Cell p) {

	p.next.prev = p.prev;
	p.prev.next = p.next;
	return p.value;
    }

    public E deleteFirst() {

	if (isEmpty()) throw new RuntimeException("Deleting from empty list");
	return delete(header.next);
    }
	
    public E deleteLast() {

	if (isEmpty()) throw new RuntimeException("Deleting from empty list");
	return delete(header.prev);
    }

    public void addLast(E s) {
	
	addBefore(header.prev,s);
	//Cell last = new Cell(s,header,header.prev);
	//header.prev = last;
	//last.prev.next = last;
    }

    public void addFirst(E s) {

	addBefore(header.next,s);
	//Cell first = new Cell(s,header.next,header);
	//header.next = first;
	//first.next.prev = first; ???
	
    }

    public void addAfter(E s) {
       
	Cell p = header;
	while(p.next != header){
	    System.out.println("Help!");
	    p = p.next;
	}
	addBefore(p.next,s);
	

    }

    public void addBefore(Cell p, E s) {
	
	if(p==header.prev){
	    Cell last = new Cell(s,header,header.prev);
	    header.prev = last;
	    last.prev.next = last;
	} else if (p==header.next) {
	    Cell first = new Cell(s,header.next,header);
	    header.next = first;
	} else {
	    Cell after = new Cell(s,p.next,p.prev);
	    p = after;
	}
    }	

    /*
    public void addInOrder(E s) {
    
    Fill method.

    }
    */

    public void printList() {

	printList(header.next);
    }

    public void printList (Cell p) {

	if(p!=header) {
	    System.out.println(p.value);
	    printList(p.next);
	    header.next = p;
	}
    }
    
    public int listLength() {
	
	return listLength(header);
    }
    
    public int listLength(Cell p) {

	if(p.next==header){
	    return 0;
	}else {
	    return listLength(p.next) + 1;
	}
	
    }
    
    Cell reverseList() {
    	    
    	    return reverseList(header);
    }
    
    /*
    Cell (E v, Cell n, Cell p) {
	    value=v; next=n; prev=p; //flinks and blinks
	}
	*/
    
    Cell reverseList(Cell p) {
 
    	    while (p.next != header) {
    	    	    Cell t = new Cell();
    	    	    t = p.next;
    	    	    p.next = p.prev;
    	    	    p.prev = p;
    	    	    p = t;
    	    }
 
    	    return p;
    }
    

    public boolean finds(E o) {

	Cell p = header.next;
	while(p!=header) {
	    if(o.equals(p.value)){
		System.out.println("String found.");
		return true;
	    }
	    p = p.next;
	}
	System.out.println("String not found.");
	return false;
    }

    public static void main (String[] args) {

	DLL<String> list = new DLL<String>();

	for (int i=0; i<args.length; ++i) {
	    //list.addFirst(args[i]);
	    list.addLast(args[i]);
	    //list.addAfter(args[i]);
	}
	
	list.printList();
	System.out.println(list.listLength());
	list.finds("is");
	list.printList();
	list.reverseList();
	list.printList();
	
    }
}

Thank you! <3 Sythra.

[g00se]

You're not making it easy for us to help you since your code doesn't conform to accepted standards. In a linked list (double or single), you need

head (not 'header')
tail
Node (the class representing members of the list)

If you go through your code and sort that out, you'll probably find the problem suddenly becomes a whole lot easier:

// (for reversed list)

Node head = (Node)tail.clone(); // (hint)

This post has been edited by g00se: 13 May 2011 - 01:46 AM

[macosxnerd101]

I wouldn't even bother cloning the tail. I would simply manage a boolean isReversed. If isReversed is true, the treat the tail Node as the head, and treat the Node prev and next variables, as next and prev respectively. So this is a very easy O(1) solution.

[Sythra]

Thanks guys! I will have to look into tail... (I don't really know much of anything about LL or DLL).

But we'll just call this early-morning-just-woke-up-LUCK-damn-I-didn't-mean-to-fall-asleep:

    void reverseList() {
    	    Cell p = header;
    	    do {
    	    	    Cell t = p.next;
    	    	    p.next = p.prev;
    	    	    p.prev = t;
    	    	    p = t;
    	    } while(p!=header);
    }

It works! *does a victory dance...*

Know of any good tutorial or all-knowing sites around let me know! Cheers and thanks! Sythra.

[macosxnerd101]

I have a tutorial on Linked Lists you may want to check out.

[g00se]

I would simply manage a boolean isReversed. If isReversed is true, the treat the tail Node as the head...

Good idea