5 Replies - 1070 Views - Last Post: 13 May 2011 - 04:57 AM Rate Topic: -----

#1 Sythra  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 13-May 11

how does one reverse a DLL double linked list ?

Posted 13 May 2011 - 12:22 AM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: how does one reverse a DLL double linked list ?

#2 g00se  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2685
  • View blog
  • Posts: 11,345
  • Joined: 20-September 08

Re: how does one reverse a DLL double linked list ?

Posted 13 May 2011 - 01:46 AM

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

Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10464
  • View blog
  • Posts: 38,781
  • Joined: 27-December 08

Re: how does one reverse a DLL double linked list ?

Posted 13 May 2011 - 04:31 AM

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.
Was This Post Helpful? 0
  • +
  • -

#4 Sythra  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 13-May 11

Re: how does one reverse a DLL double linked list ?

Posted 13 May 2011 - 04:35 AM

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.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10464
  • View blog
  • Posts: 38,781
  • Joined: 27-December 08

Re: how does one reverse a DLL double linked list ?

Posted 13 May 2011 - 04:36 AM

I have a tutorial on Linked Lists you may want to check out. :)
Was This Post Helpful? 0
  • +
  • -

#6 g00se  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2685
  • View blog
  • Posts: 11,345
  • Joined: 20-September 08

Re: how does one reverse a DLL double linked list ?

Posted 13 May 2011 - 04:57 AM

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


Good idea ;)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1