Results 1 to 4 of 4
Thread: Joining 2 double linked list.
 04242012, 03:34 AM #1Member
 Join Date
 Mar 2011
 Posts
 12
 Rep Power
 0
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]
 04242012, 03:35 AM #2Member
 Join Date
 Mar 2011
 Posts
 12
 Rep Power
 0
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; } } }
 04242012, 04:04 AM #3Senior Member
 Join Date
 Apr 2012
 Location
 New York State of Confusion, USA
 Posts
 137
 Blog Entries
 1
 Rep Power
 0
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; } } }
 04242012, 04:27 AM #4Senior Member
 Join Date
 Apr 2012
 Location
 New York State of Confusion, USA
 Posts
 137
 Blog Entries
 1
 Rep Power
 0
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 nonempty.
When inserting, you have to deal with: empty list
 Insert at head
 nonempty 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

how to delete/search double linked list
By Thomaat1 in forum New To JavaReplies: 5Last Post: 04172011, 05:37 PM 
How to access an element of a linked list inside another linked list?
By smtwtfs in forum New To JavaReplies: 4Last Post: 02212011, 10:34 AM 
Linked list inside a linked list
By viperlasson in forum New To JavaReplies: 5Last Post: 07272010, 12:15 AM 
Java double linked list
By Clown in forum New To JavaReplies: 1Last Post: 05072010, 05:04 PM 
Circular Double Linked List
By theonly in forum Advanced JavaReplies: 3Last Post: 12062009, 06:10 PM
Bookmarks