PDA

View Full Version : Linked List Help




Caster
Mar 10, 2008, 12:48 AM
Hey everyone, I'm working on a constructor for an assignment for class, and I've ran into a little bit of trouble. I'm working on a copy constructor, and this is what I have so far...
public CharList(CharList l) {
CharNode pt = head;
CharNode pt2 = l.head;
while(pt2.getNext() != null) {
pt.setNext(new CharNode(pt2.getCharacter(), null));
pt = pt.getNext();
pt2 = pt2.getNext();
}

head = pt;
}

Although I thought this was correct, unfortunately, it is not. I'm getting a null pointer exception because after the setNext() line, I'm trying to access the next, which is null, and I haven't thought of a way to get around this yet. So while trying to figure a way around it, I've tried to work on it recursively, but I'm getting an error when trying to print it, and this is what I've tried recursively...

public CharList(CharList l) {
CharNode pt = l.head;
CharNode pt2 = head;
if(pt == null) {
pt2.setNext(new CharNode(pt.getCharacter(), null));
} else {
pt = pt.getNext();
}
head = pt2;
}

And thats where I'm stuck, lol..Any suggestions to either of the two codes posted above would be helpful, thanks! (Although I would prefer a solution to the iterative solution, a recursive solution wouldn't bother me either..

Thanks!



SC68Cal
Mar 10, 2008, 01:36 AM
Let's start from scratch.

Constructors


public class IntegerCollection{

private ListItem head;

public IntegerCollection(){
head = new ListItem(); // Create the first link, null termination
}


That will hold all your actual nodes. An inner class defines the nodes.


public class ListItem{

private int val;
private ListItem link;

//Empty constructor
public ListItem(){
val = 0;
link = null;
}

//Constructor with parameters
public ListItem(int newData, ListItem newLink){
val = newData;
link = newLink;
}


Traversing the list

The print method is a method of the IntegerCollection class.


public void print(){
ListItem position = head;
while(position != null){
System.out.println(position.val);
position = position.link;
}
}


That'll give you the basics of a linked list, as well as the technique for iterating through it. I purposely left out a insert method. I think that will be your challenge. I'll give you a hint though. When you insert a new node into a list, it will take the first slot (the head) and create a link to the old head node.

To make a copy of a list, you'll destroy the old list by breaking the chain (hint: If this was a C program you'd have to go and deallocate all the nodes, rather than having garbage collection notice that there are no active references to any of the other nodes and automatically reclaiming the memory) and then insert all the values from the other list.

Caster
Mar 10, 2008, 12:42 PM
Sorry if I came off a little naive and noob like, I have most of that done (an insert head, delete tail, add tail, reverse, toString, removeChar). I realized the problem I was having when trying to access the next item when creating a new linked list because I was setting it to null, and I haven't been able to get around that just yet, but I'm still working on some ideas. A friend suggest creating a copy constructor in the Node class, which would copy a node from a pointer, so I might try that suggestion, but any other suggestions to this problem are welcomed.

Thanks!

Edit:
Had an idea, got it to work! =]