Link List

[ed81]

Hi all, It has been a long time since I came to the site .. I am taking my last java class at school and i have a final project. As always I would like to thank you for all your help to us the "Java" learners for your cooperation in our path to succees. In this ocassion I have a problem with my last project, They want me to create two lists (DONE), to delete one list(DONE), to re-create the first list(DONE) and then put LIST2 into LIST1 right in the middle..(STUCK HERE), I have tried everything I could possibly think of and i cant get it.. This is what I have so far,, I would appreciate if you could help me with some hints , because its not working the way i want.. did i put something wrong.. (I bet i did) ... Thanks a million once again.. and best regards to Khali :)



public class Link {

public long dData; // data item
public Link next; // next link in list
public Link previous;// previous link in list
// -------------------------------------------------------------
public Link(long d) // constructor
{ dData = d; }
// -------------------------------------------------------------
public void displayLink() // display this link
{ System.out.print(dData + " "); }
// -------------------------------------------------------------
} // end class Link
////////////////////////////////////////////////////////////// //
class FirstLastList
{
private Link first; // ref to first link
private Link last;
private Link middle;
private int listlength;
// -------------------------------------------------------------
public FirstLastList() // constructor
{
first = null; // no links on list yet
last = null;
middle = null;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if no links
{ return first==null; }
// -------------------------------------------------------------
public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link

if( isEmpty() ) // if empty list,
last = newLink; // newLink <-- last
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}
// -------------------------------------------------------------
public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
first = newLink; // first --> newLink
else
last.next = newLink; // old last --> newLink
last = newLink; // newLink <-- last
}
// -------------------------------------------------------------
public long deleteFirst() // delete first link
{ // (assumes non-empty list)
long temp = first.dData;
if(first.next == null) // if only one item
last = null; // null <-- last
first = first.next; // first --> old next
return temp;
}
// -------------------------------------------------------------
public void displayList()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while(current != null) // until end of list,
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
//---------------------------------------------------------------
public void listLength(){
Link current = first;
int num =0;
while(current != null)
{
current.displayLink();
current = current.next;
num++;

}
System.out.println("The count is"+" "+num);
//displayList();
}
public void deleteList(){
Link current = first;

while(current != null)
{
first = current.next;
current = first;


}
}

private Link getLeftOfMiddle() {

Link left = first;
for ( int i = 0; i <listlength/2 ; i++ ) {
left = left.next;
}
return left;
}


public void insertIntoMiddle(FirstLastList newList) {
Link leftOfMiddle = getLeftOfMiddle();
Link rightOfMiddle = leftOfMiddle.next;
leftOfMiddle.next = newList.first;
newList.first = leftOfMiddle;
rightOfMiddle.previous =newList.last;
newList.last = rightOfMiddle;


}

//-------------------------------------------------------------
} // end class FirstLastList
////////////////////////////////////////////////////////////// //



//THIS IS THE MAIN..


//import java.util.Scanner;
public class FirstLastApp {

public static void main(String[] args)
{ // make a new list


FirstLastList List1 = new FirstLastList();
FirstLastList List2 = new FirstLastList();
FirstLastList List1a = new FirstLastList();


//Scanner input = new Scanner(System.in);


List2.insertFirst(100);
List2.insertFirst(200);
List2.insertFirst(300);


List1.insertFirst(10); // insert at front
List1.insertFirst(20);
List1.insertFirst(30);
List1.insertFirst(40);
List1.insertFirst(50);
List1.insertFirst(60);


System.out.println("THE FIRST LIST");
List1.displayList();
List1.listLength();
List1.deleteList();
System.out.println("Deleting..");
System.out.println("");
System.out.println("this is the FIRST list after deletion:");
List1.displayList();
System.out.println("");
System.out.println("THE SECOND LIST");
List2.displayList();
List2.listLength();
System.out.println("");
System.out.println("Reconstructing List1 Elements:...");
System.out.println("");
List1a.insertFirst(10); // insert at front
List1a.insertFirst(20);
List1a.insertFirst(30);
List1a.insertFirst(40);
List1a.insertFirst(50);
List1a.insertFirst(60);
List1a.displayList();
List1a.listLength();
System.out.println("");
System.out.println("MERGING ITEMS FROM LIST 2 INTO LIST 1 ELEMENTS..");
List1a.insertIntoMiddle(List2);
List1a.displayList();


} // end main()
} // end class FirstLastApp

[chazzy]

shouldn't you be able to use the list length, divide it by 2 ( to get the middle) and then put all of the items there, moving the ones after as next of the insertion?

[ed81]

thats what i am trying to do as you can see in my code, I tried it.. but of course there is something wrong..Reason why I came to show my work and see if someone is able to tell me where it is failing..

Regards

[chazzy]

Ok, well what's the current behavior of it? The way I see it, you're getting a reference to the middle. You might need to use a clone.

[ed81]

I dont know, right now it dsiplays the following

THE FIRST LIST
List (first-->last): 60 50 40 30 20 10
60 50 40 30 20 10 The count is 6
Deleting..

this is the FIRST list after deletion:
List (first-->last):

THE SECOND LIST
List (first-->last): 300 200 100
300 200 100 The count is 3

Reconstructing List1 Elements:...

List (first-->last): 60 50 40 30 20 10
60 50 40 30 20 10 The count is 6

MERGING ITEMS FROM LIST 2 INTO LIST 1 ELEMENTS..
List (first-->last): 60 50 40 30 300 200 100

The problem is in the last line, I want the list to show 60 50 40 300 200 100 30 20 10. I just cant get it right :(

[mdjo]

The key problem is that you never set "next" on the last entry in newlist.

You need something like:


Link leftOfMiddle=getLeftOfMiddle();
Link rightOfMiddle=leftOfMiddle.next;
leftOfMiddle.next=newlist.first;
newlist.first.prev=leftOfMiddle;
newlist.last.next=rightOfMiddle;
rightOfMiddle.prev=newlist.last;


I included code here to update the prev pointers, but note that you are not actually setting your "prev" pointer most of the time, so this is rarely valid.

Once you've linked list 2 into the middle of list 1, list 2 is no longer valid as a self-contained list: It's last entry isn't really last anymore but points to something in list 1. Updating any first or last pointers in list 2 is therefore pretty meaningless. If the intent was that list 2 continues to exist as a separate list, you would have to copy all the entries.

Side note: On your deleteList, why do you in effect remove entries one by one? You could just say "first=last=null" and you're done with one statement.

Just a suggestion: Instead of maintaining separate first and last pointers, a handy trick is to create a "sentinel" entry whose "next" pointer is the first entry and whose "prev" pointer is the last entry, where the sentinel is initialized with both pointers going back to itself. This really simplifies insert and delete logic. Like:


public LinkList()
{
Link sentinel=new Link();
sentinel.prev=sentinel.next=sentinel;
}
public void insertAfter(Link after,Link newbie)
{
Link before=after.next;
before.next=newbie;
newbie.prev=before;
newbie.next=after;
after.prev=newbie;
}
public void delete(Link victim)
{
victim.prev.next=victim.next;
victim.next.prev=victim.prev;
}
public void insertFirst(Link newbie)
{
insertAfter(sentinel,newbie);
}
public void insertLast(Link newbie)
{
insertAfter(sentinel.prev,newbie);
}


To loop through all entries you write something like:


for (Link entry=sentinel.next;entry!=sentinel;entry=entry.next)
{
... whatever ...
}


Of course you could always write a getFirst() function that just returns sentinel.next, etc.

[ed81]

It Works Perfectly Thank You Very Much.. .. :).