Joining 2 double linked list.

[syle_q]

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]

[syle_q]

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

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;
}

}
}

[jlczuk]

This is much easier for use to digest:

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;
		}

	}
}

[jlczuk]

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?