I have a Linked List and I'm trying to create a copy of another Linked List and this copy is a deep copy because the element type is char. Due to the complexity of linked lists, I've tried not to use the add method. My code is shown below. Also I want to recursively add all the elements from some list to my original list but the problem with my implementation is that it only adds the first element in the list and not all of it. Why is this so?
public class CharLinkedList {
private static class Node {
private char info;
private Node next;
public Node(char d) {
this.data = d;
this.next = null;
}
}
private int size;
private Node head;
public CharLinkedList() {
this.size = 0;
this.head = null;
}
public CharLinkedList(CharLinkedList some) {
this.size = some.size;
Node node = some.head;
this.head = new Node(other.head.info);
if(node.next != null)
{
this.head.next = new Node(node.next.info);
node = node.next;
this.head.next.next = new Node(node.next.info);
}
}
public void addAll(CharLinkedList some) {
if(some == null){
return;
}
if (this.size == 0) {
Node someNode = new Node(some.get(0));
this.head = someNode;
}
else {
CharLinkedList.addAll(some, this.head.next);
}
this.size++;
}
private static void addAll(CharLinkedList some, Node node) {
if(node.next == null)
{
Node someNode = new Node(some.get(0));
node.next = someNode;
}
else {
CharLinkedList.addAll(some, node.next);
}
}
public static void main(String[] args) {
CharLinkedList l = new CharLinkedList();
l.add('z');
l.add('o');
l.add('m');
CharLinkedList some = new CharLinkedList(l);
some.add('b');
some.add('i');
some.add('e');
System.out.println(l);
System.out.println(some);
// now i change the state of l and append all of some
l.set(1, 'p');
l.addAll(some);
System.out.println(l);
This seems like an academic exercise to me (otherwise I would expect you to be using a LinkedList<Character> from the Java Collections Framework), so I'm not going to post a completed method for you. Instead I'll try and steer you towards you creating a working deep copy implementation for yourself.
First off - I wouldn't use recursion to copy your list. If you do, you're likely to run into a StackOverflowError as your list gets larger and larger (admittedly, it won't be a problem for a three-element list). Secondly, rather than having a constructor that returns a deep copy of the CharLinkedList that you give it, I would instead override Object's clone() method (that's what it's for after all).
How would you copy each element into your cloned list?
Well, you already know how large your list is, you're storing that in in your size attribute. You can use this value as the upper bound of a for loop, in which you would copy each list element in sequence.
Because your CharLinkedList class only maintains a reference to your head element, you would need to maintain a reference to the current Node outside of your loop, otherwise you'd lose your reference to the next element after each iteration.
In essence, you want something like this pseudo-code:
CharLinkedList newList = new CharLinkedList();
Node currentNode = head;
// There are plenty of other ways to do this, you could also use a while loop
// checking that next is not null.
for (each element up until size) {
// You may need to implement getData()
Node newNode = new Node(currentNode.getData());
newList.add(newNode);
// You may need to implement getNextNode()
currentNode = currentNode.getNextNode();
}
Once you're done, return newList, and don't forget to document that your clone() method returns a deep clone instead of a shallow clone. Why? Because it's a good habit to get into.
Finally, don't forget to take a look at the Java Collections Framework, which already contains an implementation of LinkedList that you can read through the source code for.
In your constructor for CharLinkedList that accepts another CharLinkedList, you are only using an if statement to check if the other linked list has another element, and if it does, it will add it as this.head.next . However, if there are multiple elements, you would need to make that if statement into a while and use the temp variable node as an "iterator" of sorts.
Something like this should do:
Node node = some.head;
this.head = new Node(some.head.info);
Node adder = this.head; // keep track of the adding nodes
node = node.next; // advance the pointer to the next node
while(node.next != null) // keep adding to the linked list while there are things to add
{
adder.next = new Node(node.info);
node = node.next; // advance the pointer to the next node
}
That code will traverse the some linked list and make a copy of each of its elements into the linked list currently being constructed.
There are several flaws in your addAll scheme. The most clear way to add all the elements would be to implement a solution similar to what I've wrote above, modifying where to start adding,etc. However, addressing your current style, the addAll that only takes a CharLinkedList is good, and correctly calls the recursive addAll with the additional parameters, however in that other addAll you are checking
if(node.next == null)
Even though you are passing it node.next from the previous functionm, which is expected to be null anyways. Also, you cannot be so sure to always add the 0th element, since this could be a deep recursive call several links into the chain. To continue with this implementation, you can add an additional int parameter keeping track of where you are in the list, or an additonal Node parameter specifying what to add next -- the choice/stye is yours.
Hope this helps
