Results 1 to 4 of 4
  1. #1
    syle_q is offline Member
    Join Date
    Mar 2011
    Posts
    12
    Rep Power
    0

    Default Joining 2 double linked list.

    I have an assignment to write several methods that do work on a doubly linked list. The list contains nodes that have "textbook" objects as data points. Our list must always be in alphabetical order based on the textbook names. One of the methods that I am having trouble with is, [code]public void join(DLinkedList other)[code] , which combines two linked textbook lists into one larger list that is also in alphabetical order. I am having trouble wrapping my head around how to do this with just called insert on every node of the second list. Below is my insert method. Can anyone give me some advice on how to do so? Thanks in advance

    [code]
    public void insert(Textbook a) {

    Node insert = new Node(a);

    if (isEmpty()) {
    head = tail = insert;
    return;
    }

    if (contains(a) > 0) {
    System.out.println("This already exist in the list");
    }

    for (Node temp = head; temp != null; temp = temp.fpointer) {
    if (a.compareTo(temp.data) < 0) {
    if (temp == head) {
    insert.fpointer = head;
    head.bpointer = insert;
    head = insert;
    return;
    }

    insert.fpointer = temp;
    insert.bpointer = temp.bpointer;
    temp.bpointer = insert;
    insert.bpointer.fpointer = insert;
    return;
    }

    if(tail.data.compareTo(a) < 0 ){
    tail.fpointer = insert;
    insert.bpointer = tail;
    tail = insert;
    }

    }
    }
    [code]

  2. #2
    syle_q is offline Member
    Join Date
    Mar 2011
    Posts
    12
    Rep Power
    0

    Default Re: Joining 2 double linked list.

    I have an assignment to write several methods that do work on a doubly linked list. The list contains nodes that have "textbook" objects as data points. Our list must always be in alphabetical order based on the textbook names. One of the methods that I am having trouble with is, [code]public void join(DLinkedList other)[code] , which combines two linked textbook lists into one larger list that is also in alphabetical order. I am having trouble wrapping my head around how to do this with just called insert on every node of the second list. Below is my insert method. Can anyone give me some advice on how to do so? Thanks in advance

    Java Code:
    public void insert(Textbook a) {
    
    Node insert = new Node(a);
    
    if (isEmpty()) {
    head = tail = insert;
    return;
    }
    
    if (contains(a) > 0) {
    System.out.println("This already exist in the list");
    }
    
    for (Node temp = head; temp != null; temp = temp.fpointer) {
    if (a.compareTo(temp.data) < 0) {
    if (temp == head) {
    insert.fpointer = head;
    head.bpointer = insert;
    head = insert;
    return;
    }
    
    insert.fpointer = temp;
    insert.bpointer = temp.bpointer;
    temp.bpointer = insert;
    insert.bpointer.fpointer = insert;
    return;
    }
    
    if(tail.data.compareTo(a) < 0 ){
    tail.fpointer = insert;
    insert.bpointer = tail;
    tail = insert;
    }
    
    }
    }

  3. #3
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: Joining 2 double linked list.

    This is much easier for use to digest:
    Java Code:
    public void insert(Textbook a) {
    
    	Node insert = new Node(a);
    
    	if (isEmpty()) {
    		head = tail = insert;
    		return;
    	}
    
    	if (contains(a) > 0) {
    		System.out.println("This already exist in the list");
    	}
    
    	for (Node temp = head; temp != null; temp = temp.fpointer) {
    		if (a.compareTo(temp.data) < 0) {
    			if (temp == head) {
    				insert.fpointer = head;
    				head.bpointer = insert;
    				head = insert;
    				return;
    			}
    
    			insert.fpointer = temp;
    			insert.bpointer = temp.bpointer;
    			temp.bpointer = insert;
    			insert.bpointer.fpointer = insert;
    			return;
    		}
    
    		if(tail.data.compareTo(a) < 0 ){
    			tail.fpointer = insert;
    			insert.bpointer = tail;
    			tail = insert;
    		}
    
    	}
    }

  4. #4
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: Joining 2 double linked list.

    Link lists are an easy construct to understand and a pain in the butt to write from scratch, but a necessary evil when learning basic data structures.

    There are two basic list states to handle: empty and non-empty.
    When inserting, you have to deal with:
    • empty list
      • Insert at head

    • non-empty list
      • Insert at head
      • Insert in middle
      • Insert at tail


      So really you have the three insertion variations to handle depending on the state of the list and where you are inserting. Each of the three is different. You haven't mentioned the need to remove any nodes, so I won't make things more complicated by considering what needs to be done for node removal, although it is not terribly different from insertion. For both, you have to be careful about your forward and backward references to maintain the integrity of the list.

      Look at your insert method and see if you've covered all three forms of insertion that must be handled.

      Also, if your assumption is that both lists are already sorted, do you think you need to do anything special to ensure your final list is sorted correctly once you've done all your insertions?

Similar Threads

  1. how to delete/search double linked list
    By Thomaat1 in forum New To Java
    Replies: 5
    Last Post: 04-17-2011, 04:37 PM
  2. Replies: 4
    Last Post: 02-21-2011, 09:34 AM
  3. Linked list inside a linked list
    By viperlasson in forum New To Java
    Replies: 5
    Last Post: 07-26-2010, 11:15 PM
  4. Java double linked list
    By Clown in forum New To Java
    Replies: 1
    Last Post: 05-07-2010, 04:04 PM
  5. Circular Double Linked List
    By theonly in forum Advanced Java
    Replies: 3
    Last Post: 12-06-2009, 05:10 PM

Posting Permissions

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