doubly linked lists

[scarface]

hi people, i am have trouble with one method that should delete an element from a doubly linked list.

thats what i got so far

public void delete(Object info) {
DLNode node1 = head,tail;
if(node1.info==info){
if(node1.prev!=null){

node1.prev.next=node1.next;
node1.next.prev = node1.prev;
}else
head = node1.next;

if(node1.next !=null)
node1.next.prev = node1.prev;

else tail =node1.prev;

}
}

I can delete the head of the list(the first element) but cant delete the middle element or the last one(considering i have 3 elements in the list). I have no idea why this is. I have tried changing the code is many ways but no luck. I have drawn little "nodes" and "links" between them on paper and when i follow the "links" between the "nodes" i convince :confused: myself the code i got should be working but it is not :eek:. Can anyone see anything i am missing?

[Twey]

To refactor:
public void delete(Object info) {
DLNode node1 = head,
tail;

if (node1.info == info) {
if (node1.prev != null) {
node1.prev.next = node1.next;
node1.next.prev = node1.prev;
} else
head = node1.next;

if(node1.next != null)
node1.next.prev = node1.prev;
else
tail = node1.prev;
}
}Now, there's a fairly obvious flaw here, and it's not in the data structure. Follow the flow of your code. What happens if you call delete(foo) on a list in which foo is the third element? As a solution, I would suggest a loop starting with while (node1.info != info). Additionally, why do you define and assign to tail, when it's never used?

No code this time, lest your professor for this module hunts me down :p

[scarface]

say that i only wanted to remove either the head or tail of a list. I got this code for removing the head and it works

if(head.info==info)
{

head=head.next;
head.prev=null;

}

now shouldn't the code for removing the tail be exactly the same except for the pointers?Isn't is pretty much the same procedure?

[Twey]

Yes, completely. You need to swap 'next' for 'prev' and vice versa, though.

[KRISPY]

i have the same problem as scarface and tried a while loop but could not get it to work this is a tutorial excercise set but our lecturers have said that it may be questioned in the final exam so i want to get ahead of the game and understand how it works the *** is where the code needs to be implemented any coding to help me understand would be appreciated as my java is very bad thanks




import java.util.Iterator;

/**
* search for <i>*** to be implemented ***</i>.
*
*/
public class DLList implements Iterable {

/**
* Inner class for doubly linked list nodes.
*/
class DLNode {

Object info; // the data element
DLNode next; // the next node
DLNode prev; // the previous node

DLNode(Object argInfo) {
info = argInfo;
}
}

private DLNode head, tail;
int count;

/**
* Appends an object at the tail of this list.
* @param argOb The object to append.
*/
public void appendAtTail(Object argOb) {
// *** to be implemented ***
}

/**
* Finds the first element containing <code>obj</code> and removes it using <code>delete(DLNode)</code>.
* @param obj The object to remove.
*/
public void delete(Object obj) {
// *** to be implemented ***
}

/**
* Removes the given node maintaining the list structure.
* @param node The node to delete.
*/
private void delete(DLNode node) {
if (node.prev != null)
node.prev.next = node.next;
else {
head = node.next;
}
if (node.next != null)
node.next.prev = node.prev;
else
tail = node.prev;
if (count > 0)
count--;
}


/**
* Reverses this lists nodes (i.e. after a call to this method, the iterator
* outputs the list elements in reverse order).
*/
public void reverse() {
// *** to be implemented ***
}


/**
* Removes all multiple occurrences of elements, leaving only one occurrence
* of each unique element, using only constant memory.
*/
public void removeDuplicates() {
// *** to be implemented ***
}

/**
* Creates an iterator to traverse this list
* @return The iterator.
*/
public Iterator iterator() {
return new Iterator() {

DLNode current = DLList.this.head;
DLNode previous = null;

public boolean hasNext() {
return current != null;
}

public Object next() {
if(current == null)
return null;
Object tmp = current.info;
previous = current;
current = current.next;
return tmp;
}

public void remove() {
DLList.this.delete(previous);
}

};
}

/**
* Prints the list elements to System.out
*/
public void printList() {
Iterator iter = iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}

/**
* Just for testing.
*
* @param args ignored
*/
public static void main(String[] args) {
boolean manualTest = true;


{ // Test append at Tail
// set up
DLList list = new DLList();
list.appendAtTail("1");
list.appendAtTail("2");
list.appendAtTail("3");
// now test
if(manualTest)
list.printList();
Iterator iter = list.iterator();
if(iter.next().equals("1") && iter.next().equals("2") && iter.next().equals("3") && iter.hasNext() == false)
System.out.println("appendAtTail OK");
else
System.out.println("appendAtTail ERROR");
}

System.out.println();

{ // Test delete(Object)
// set up
DLList list = new DLList();
list.appendAtTail("A");
list.appendAtTail("B");
list.appendAtTail("C");
list.delete("B");
// now test
if(manualTest)
list.printList();
Iterator iter = list.iterator();
if(iter.next().equals("A") && iter.next().equals("C") && iter.hasNext() == false)
System.out.println("delete OK");
else
System.out.println("delete ERROR");
}

System.out.println();

{ // Test reverse
// set up
DLList list = new DLList();
list.appendAtTail(1);
list.appendAtTail(2);
list.appendAtTail(3);
list.reverse();
// now test
if(manualTest)
list.printList();
Iterator iter = list.iterator();
if(iter.next().equals(3) && iter.next().equals(2) && iter.next().equals(1))// && iter.hasNext() == false)
System.out.println("reverse OK");
else
System.out.println("reverse ERROR");
}


{// Test deleteDoubles
// set up
DLList list = new DLList();
list.appendAtTail(1);
list.appendAtTail(2);
list.appendAtTail(1);
list.appendAtTail(3);
list.appendAtTail(2);
list.appendAtTail(3);
list.removeDuplicates();
// now test
if(manualTest)
list.printList();
Iterator iter = list.iterator();
if(iter.next().equals(1) && iter.next().equals(2) && iter.next().equals(3) && iter.hasNext() == false)
System.out.println("deleteDoubles OK");
else
System.out.println("deleteDoubles ERROR");
}
}

}

[scarface]

funny thing is Twey, i tried that code for removal of tail and it does not work. I did it exactly as i did the one for head(assigning the links for tail this time) but it didnt remove my last item.

if(tail.info==info)
{
tail=tail.prev;
tail.next=null;

}

this is what i used and i cant explain why it didnt work.Just doesnt seem right

[Trinithis]

If you want, here's the source code for java.util.LinkedList:
http://www.docjar.com/html/api/java/util/LinkedList.java.html

[scarface]

thanx trinithis i will have a look at that later. And people, stop uploading whole courseworks on here waiting for answers. What i do is i try the exercises my self, search the web if i cant get it done or i am missing some functionality that should be there and if i dont find something useful i ask questions on here but i dont upload courseworks on here.