Results 1 to 8 of 8

Thread: doubly linked lists

  1. #1
    Join Date
    Oct 2008
    Posts
    20
    Thanks
    0
    Thanked 2 Times in 2 Posts

    Default doubly linked lists

    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
    Code:
     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 myself the code i got should be working but it is not . Can anyone see anything i am missing?

  2. #2
    Join Date
    Jun 2005
    Location
    英国
    Posts
    11,876
    Thanks
    1
    Thanked 180 Times in 172 Posts
    Blog Entries
    2

    Default

    To refactor:
    Code:
    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
    Twey | I understand English | 日本語が分かります | mi jimpe fi le jbobau | mi esperanton komprenas | je comprends franšais | entiendo espa˝ol | t˘i Ýt hiểu tiếng Việt | ich verstehe ein bisschen Deutsch | beware XHTML | common coding mistakes | tutorials | various stuff | argh PHP!

  3. #3
    Join Date
    Oct 2008
    Posts
    20
    Thanks
    0
    Thanked 2 Times in 2 Posts

    Default

    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
    Code:
    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?

  4. #4
    Join Date
    Jun 2005
    Location
    英国
    Posts
    11,876
    Thanks
    1
    Thanked 180 Times in 172 Posts
    Blog Entries
    2

    Default

    Yes, completely. You need to swap 'next' for 'prev' and vice versa, though.
    Twey | I understand English | 日本語が分かります | mi jimpe fi le jbobau | mi esperanton komprenas | je comprends franšais | entiendo espa˝ol | t˘i Ýt hiểu tiếng Việt | ich verstehe ein bisschen Deutsch | beware XHTML | common coding mistakes | tutorials | various stuff | argh PHP!

  5. #5
    Join Date
    Dec 2008
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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


    Code:
    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");
    			}
    	}
    
    }

  6. #6
    Join Date
    Oct 2008
    Posts
    20
    Thanks
    0
    Thanked 2 Times in 2 Posts

    Default

    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.
    Code:
    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

  7. #7
    Join Date
    May 2007
    Location
    USA
    Posts
    373
    Thanks
    2
    Thanked 4 Times in 4 Posts

    Default

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

  8. #8
    Join Date
    Oct 2008
    Posts
    20
    Thanks
    0
    Thanked 2 Times in 2 Posts

    Default

    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.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •