Java LinkedList Array referencing

Question

So I have a simple program that creates a LinkedList array of given size n, with each value in the list representing a new separate LinkedList data Structure.

public class Graph {

public final LinkedList[] graph;

public Graph(int n){
    graph = new LinkedList[n];  

    for (int i=0; i<n; i++){
        graph[i] = new LinkedList();
    }

}

public void addEdge(int x, int y){

    graph[x].addFirst(y);
    graph[y].addFirst(x);

}

For some reason, however, when I call the addEdge() method with two int values, instead of adding them to the specific called LinkedList in graph[], it adds them to every LinkedList in graph[].

What is the problem here?

Edit:*

public void addEdge(int x, int y){

    graph[x].addFirst(y);
    graph[y].addFirst(x);

    for (int i=0; i<graph.length; i++){
        Node tmp = graph[i].first;

        System.out.println(i + ":");

        while (tmp != null){
            System.out.print(tmp.name + " ");

            tmp = tmp.Rnext;
        }
        System.out.println();
    }
    System.out.println();

}


public class Test {

public static void main(String[] args) {


    Graph myGraph1 = new Graph(8);
    myGraph1.addEdge(1, 2);
    myGraph1.addEdge(1, 7);
    myGraph1.addEdge(1, 4);
    myGraph1.addEdge(2, 5);
    myGraph1.addEdge(2, 6);
    myGraph1.addEdge(6, 3);
    myGraph1.addEdge(3, 8);
    myGraph1.addEdge(5, 7); 
    }
}

Here is the output of graph:
0:
1 2 
1:
1 2 
2:
1 2 
3:
1 2 
4:
1 2 
5:
1 2 
6:
1 2 
7:
1 2 

0:
1 7 1 2 
1:
1 7 1 2 
2:
1 7 1 2 
3:
1 7 1 2 
4:
1 7 1 2 
5:
1 7 1 2 
6:
1 7 1 2 
7:
1 7 1 2 

0:
1 4 1 7 1 2 
1:
1 4 1 7 1 2 
2:
1 4 1 7 1 2 
3:
1 4 1 7 1 2 
4:
1 4 1 7 1 2 
5:
1 4 1 7 1 2 
6:
1 4 1 7 1 2 
7:
1 4 1 7 1 2 

0:
2 5 1 4 1 7 1 2 
1:
2 5 1 4 1 7 1 2 
2:
2 5 1 4 1 7 1 2 
3:
2 5 1 4 1 7 1 2 
4:
2 5 1 4 1 7 1 2 
5:
2 5 1 4 1 7 1 2   
6:
2 5 1 4 1 7 1 2 
7:
2 5 1 4 1 7 1 2 

0:
2 6 2 5 1 4 1 7 1 2 
1:
2 6 2 5 1 4 1 7 1 2 
2:
2 6 2 5 1 4 1 7 1 2 
3:
2 6 2 5 1 4 1 7 1 2 
4:
2 6 2 5 1 4 1 7 1 2 
5:
2 6 2 5 1 4 1 7 1 2 
6:
2 6 2 5 1 4 1 7 1 2 
7:
2 6 2 5 1 4 1 7 1 2 

0:
6 3 2 6 2 5 1 4 1 7 1 2 
1:
6 3 2 6 2 5 1 4 1 7 1 2 
2:
6 3 2 6 2 5 1 4 1 7 1 2 
3:
6 3 2 6 2 5 1 4 1 7 1 2 
4:
6 3 2 6 2 5 1 4 1 7 1 2 
5:
6 3 2 6 2 5 1 4 1 7 1 2 
6:
6 3 2 6 2 5 1 4 1 7 1 2 
7:
6 3 2 6 2 5 1 4 1 7 1 2

Here is the LinkedList and Node Class I am using:

import java.util.NoSuchElementException;

public class LinkedList {

public static Node first;

    public LinkedList(){ 
    first = null;

    } 

    // Returns true if the list is empty 
    public boolean isEmpty(){ 
    return first == null; 
    } 

    // Inserts a new node at the beginning of this list. 
    public void addFirst(int name){ 

    first = new Node(name, first);
    }


    public boolean findData(int d){
    if(first == null) throw new NoSuchElementException();
    Node tmp = first;

    while (tmp != null) {

        if (tmp.name == d) return true;
        tmp = tmp.Rnext;
    } return false;
}
}


    public class Node { 

    public int name;
    public Node Rnext;

    public Node(){ 
    name = 0;
    Rnext = null; 
    } 

    public Node(int n, Node r){ 
    this.name = n;
    this.Rnext = r;
} 

}

How are you checking that they are actually being added to every linked list? — Tanmay Patil, Apr 06 '14 at 22:45
See here for syntax of creating lists of lists in Java, that seems like it could be the problem http://stackoverflow.com/questions/217065/cannot-create-an-array-of-linkedlists-in-java — mike, Apr 06 '14 at 22:47
Can you show the code that creates the instance and adds edge? Also add some sysout for debugging purpose and paste the output here. — Bhesh Gurung, Apr 06 '14 at 22:52
I am printing each linked list at the end of the program, but this code adds values to every linkedlist in the array, opposed to just the reference of graph[x] and graph[y] — Sean, Apr 06 '14 at 22:52
Good, can you show us the code that adds and prints, along with what you see on console as output? — Bhesh Gurung, Apr 06 '14 at 22:53
You're not using `java.util.LinkedList`, are you? What `LinkedList` class are you using? If it's custom, can you show us that code? — torquestomp, Apr 06 '14 at 22:59
`public static Node first;` there's your problem right there — Zyn, Apr 06 '14 at 23:02
Indeed, first is static, which means all LinkedList objects share the same contents. Why not use java.util.LinkedList? — Ernest Friedman-Hill, Apr 06 '14 at 23:06

score 1 · Accepted Answer · answered Apr 06 '14 at 23:02

1

public static Node first;

This is the problem. Every single LinkedList you make is sharing the same Node, so they're all effectively the same list.

Don't use static for instance variables.

answered Apr 06 '14 at 23:02

torquestomp

3,304
19
26

Java LinkedList Array referencing

1 Answers1