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).

Try using a debugger to step through the code - should give you some insight into what is happening. — davidA, Sep 12 '12 at 05:04
`LinkedList a = l;` is just like saying `a` is now the object `l` so you are modifying `l` — , Sep 12 '12 at 05:12
see also http://stackoverflow.com/questions/40480/is-java-pass-by-reference?lq=1 — , Sep 12 '12 at 05:13
@RC: yes i know that is causing the issue. the only thing i can think of is to copy all elements of the linked list into new linked list. but i dont think that is the right soln...plz help — ueg1990, Sep 12 '12 at 05:31
that i create a new list in my function (LinkedList a) and copy elements of linked list l to a — ueg1990, Sep 12 '12 at 05:36

Gaim · Accepted Answer · 2012-09-12T06:06:49.623

1

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.

edited Sep 12 '12 at 06:06

answered Sep 12 '12 at 05:36

Gaim

6,734
4
38
58

LinkedList a = l; => is this an example of shallow copy?? for deep copy, so i create a new list and copy all elements of linked list l to the new list? then do the same for linked list m and then concaentate the two new list?? isnt that inefficient use of memory?? – ueg1990 Sep 12 '12 at 05:44
`LinkedList a = l;` is not copy. It means, that both variables `a` and `l` refers to the same instance of `LinkedList`. It means that both variables points to the same memory. Well you need to copy both of them when you need to have it clean and unchanged. You are right, that in the theory you can reuse the list `m` but I think that is not a good practice if you don't write memory critical application – Gaim Sep 12 '12 at 05:49
the code u added above: is that a deep copy? if yes, how will an iterator offer a better soln? – ueg1990 Sep 12 '12 at 05:51
If it is a deep copy it depends on the implementation of `insertNode` method. You need to make a new instance of it, I left it up to you, I just added the comment. Iterator would improved the time complexity from `O(n^2)` to `O(n)` because `getNode` would be `O(1)`. – Gaim Sep 12 '12 at 05:54
Now I realized that reuse of list `m` is bad idea because when you make a concatenation of lists `l` and `m` to `a` and then you change the list `m` it would affect also the list `a`. – Gaim Sep 12 '12 at 05:58
i think i figured out how to do it in O(n), can u have a look below – ueg1990 Sep 12 '12 at 06:01
@ueg1990 Look at my code edit. Your posted code now looks fine and it is in `O(n+m)` where `n` is length of list `l` and `m` is length of list `m` – Gaim Sep 12 '12 at 06:07

score 0 · Answer 2 · edited Sep 30 '12 at 01:24

0

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.

edited Sep 30 '12 at 01:24

Littm

4,923
4
30
38

answered Sep 12 '12 at 05:38

Ajay Sharma

1

so i create a new list and copy all elements of linked list l to the new list? then do the same for linked list m and then concaentate the two new list?? isnt that inefficient use of memory?? – ueg1990 Sep 12 '12 at 05:43

score 0 · Answer 3 · answered Sep 12 '12 at 06:01

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

Problems in implementing code for linked list

3 Answers3