Problems in implementing code for linked list

Question

In my implementation of a linked list, there are two methods. When I call one method, it affects the results of the other method. One method is concatenateLL() to concatenate two list and one method is getNumberOfNodes() which returns number of nodes in linked list. For my method concatenate, I am supposed to return a new list which is a concatenation of two lists. But in my code, the resulting new list affect the list in the first parameter. Lets say I pass list l and m and parameters and I return a new list.

The problem is that the new is just list l which now includes elements of list m (due to concatenation). And because of this, when I call getNumberOfNodes() on list l and m, I get the wrong value.

Here is my code:

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
    LinkedList a = l;
    Node l_last = a.getTailNode();
    Node m_first = m.getHeadNode();
    l_last.setNext(m_first);
    a.tail = m.getTailNode();
    return a;
}

public int getNumberOfNodes(Node h) {
    if(h == null)
        return 0;
    return 1 + getNumberOfNodes(h.getNext());
}

public static void print(LinkedList l) {
    Node v = l.getHeadNode();
    while(v != null) {
        System.out.print(v.getElement()+" ");
        v = v.getNext();
    }
    System.out.println();
}

public static void main(String[] args) throws IndexOutOfBoundsException {
    // TODO Auto-generated method stub
    LinkedList l = new LinkedList();
    LinkedList m = new LinkedList();
    l.insertFirst(5);
    l.insertFirst(7);
    l.insertFirst(3);
    l.insertFirst(6);
    print(l);
    m.insertFirst(2);
    m.insertFirst(4);
    m.insertFirst(9);
    m.insertFirst(8);
    m.insertLast(10);
    m.insertLast(12);
    print(m);
    LinkedList n = concatenateLL(l, m);
    print(n);
    System.out.println(l.getNumberOfNodes(l.getHeadNode()));
    System.out.println(m.getNumberOfNodes(m.getHeadNode()));
}

In the main method, length of list l should return 4 and list m should return 6. But after I call concatenation method before calling getNumberOfNodes(), I get length of l as 10 (which is number of nodes of list n as a result of concatenation of l and m) and length of m as 15 (which I have no idea why).

Answer 1

Yes, LInkedList a = l; does not create a copy of linked-list l.

You'll have to create a new linked-list, if you don't want to modify l.

Answer 2

When I see your code I guess that you are used to write in C/C++ (based on naming convention and expected behavior). Your problem lies in making deep copy. At the beginning of the concatenateLL method you need to make a deep copy of both lists and then you can concatenate them in the way you currently do it.

LinkedList a = l; // problem line

In C/C++ it would call a copy-constructor but Java doesn't have anything like that so you need to implement it by yourself. You can use method clone() declared by java.lang.Object and override it but you need to make a deep copy not the shallow because you are changing also references between nodes, not just the lists.

For example the method can look somehow like this:

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
   LinkedList a = new LinkedList();

   // copy Nodes, you need to create new instance of them
   for ( int i = 0; i < l.getNumberOfNodes(l.getHeadNode()); ++i )
        a.insertLast( l.getNode( i ) );

   // copy Nodes, you need to create new instance of them
   for ( int i = 0; i < m.getNumberOfNodes(m.getHeadNode()); ++i )
        a.insertLast( m.getNode( i ) );

   return a;
}

But I need to mention that this implementation has a O(n^2) complexity because of method getNode() is O(n). The better solution is to use the iterator but I don't know whether your class implements it.

EDIT: To improve the complexity to O(n) I suggest you to implement the standard interface Iterator Anyway the point lies in keeping the reference to current element to be able to simply get next. If I make a simple example:

Node item = l.getHeadNode();

while( item != null ) {
    // copy the item
    a.insertLast( item );
    item = item.getNext();
}

And the same for the list m.

Answer 3

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
    LinkedList a = new LinkedList();
    Node l_last = l.getHeadNode();
    Node m_first = m.getHeadNode();
    while(l_last != null) {
        a.insertLast(l_last.getElement());
        l_last = l_last.getNext();
    }
    while(m_first != null) {
        a.insertLast(m_first.getElement());
        m_first = m_first.getNext();
    }       
     return a;
}