Simply changing the value of a variable changes the value of a node in my linked list? This should not happen

Question

So, I am making a chess engine in Java. Given a current board configuration, the AI should figure out each possible move it can make, add it to a linked list of all possible moves, and return that list. Currently I am testing the following board configuration:

/*bRbNbBbQbKbBbNbR
  bPbPbPbPbPbPbPbP
  NuNuNuNuNuNuNuNu
  NuNuNuwRNuNuNuNu
  NuNuNuNuNuNuNuNu
  NuNuNuNuNuNuNuNu
  wPwPwPwPwPwPwPwP
  NuwNwBwQwKwBwNwR*/

"bR" means black rook, "bN" is black knight, etc. "Nu" means null or no piece. In this configuration I moved the bottom-left white rook to the middle of the board.

The following method, possibleMoves(), in my Mobility class is what should generate and return a linked list of all of the possible board configurations. Each index i corresponds to pieces on the board starting from the left. In this case the AI is white, so 0 is the leftmost white pawn, 7 is the rightmost white pawn, 8 is the white rook that is now in the center of the board, 9 is the other white rook, etc. Right now I'm only testing the rooks, so the other conditionals are empty. nonPawnBoardGen() returns a sublist of possible board configurations.

public LL possibleMoves(){
    LL children = new LL();
    /*
     * check each piece
     */
    for(int i = 0; i < 16; i++){
        if(i < 8){//pawns

        }
        else if(i < 10){//rooks
            children.joinWith(nonPawnBoardGen(i, 0, -1)); //positions to the left
            children.joinWith(nonPawnBoardGen(i, 0, 1)); //right
            children.joinWith(nonPawnBoardGen(i, -1, 0)); //up
            children.joinWith(nonPawnBoardGen(i, 1, 0)); //down
        }
        else if(i < 12){
        //  checkKnight(r, c, int dR, int dC)
        }
        else if(i < 14){//bishops

        }
        else{ //king, queen

        }
    }
    return children;
}

joinWith(), in my LL class, joins a sublist with the total children linked list.

public void joinWith(LL newList){
    if(newList.isEmpty())
        return;
    if(this.isEmpty()){
        first = newList.getFirst();
        last = newList.getLast();
    }
    else{
        last.next = newList.getFirst();
        last = newList.getLast();
    }
}

The following function, nonPawnBoardGen(), is another function in my Mobility which gets passed a piece index and a unit vector. So, if I want to check all of the possible left moves of the rook in the center of the board, I would call nonPawnBoardGen(8, 0, -1) because the rook is index 8, it will remain in the same row, and it will iterate through columns to the left. That function call should return a sublist of all of the possible board configurations involving this rook because I would still need to check everything to the right, up, and down from the rooks current position.

private LL nonPawnBoardGen(int index, int vecR, int vecC){
    LL boardSubLst = new LL();
    int sR, sC; //source row and col
    if(turn == true){//white
        //last 16 coords are white pieces
        if(coords[index + 16] == null){//if piece does not exist, return
            return null;
        }
        sR = coords[index + 16].getRow(); //each coord is an object containing a row and col value
        sC = coords[index + 16].getCol();
    }
    else{//black
        //first 16 coords are black pieces
        if(coords[index] == null){
            return null;
        }
        sR = coords[index].getRow();
        sC = coords[index].getCol();
    }
    int curR = sR; //current row
    int curC = sC; //current col
    curR+=vecR; //iterate by unit vector
    curC+=vecC;
    while(curR > -1 && curR < 8 && curC > -1 && curC < 8){ //while in range of board
        if(turn == true){//white
            if(board[curR][curC].charAt(0) != 'w'){ //if space is free or opposite color, valid move
                coords[index + 16].setRow(curR); //move rook to new position
                coords[index + 16].setCol(curC);
                if(board[curR][curC].charAt(0) == 'b'){ //if space contains piece of opposite color,
                    int r, c;                           //piece needs to be removed
                    for(int j = 0; j < 16; j++){ //iterate through 16 opponent pieces
                        r = coords[j].getRow();
                        c = coords[j].getCol();
                        if(curR == r && curC == c){ //check which opponent's piece's coords match
                            coords[j] = null;       //the rook's current coords, then remove opp's piece
                            boardSubLst.insert(coords); //add board config to sublist
                            break;
                        }
                    }
                    break;
                }
                else{ //if the space is null, simply add board config to sublist
                    boardSubLst.insert(coords);
                }
            }
            else{ //if space is same color, break
                break;
            }
        }
        else{//black
            if(board[curR][curC].charAt(0) != 'b'){
                coords[index].setRow(curR);
                coords[index].setCol(curC);
                if(board[curR][curC].charAt(0) == 'w'){
                    int r, c;
                    for(int j = 0; j < 16; j++){
                        r = coords[j + 16].getRow();
                        c = coords[j + 16].getCol();
                        if(curR == r && curC == c){
                            coords[j + 16] = null;
                            boardSubLst.insert(coords);
                            break;
                        }
                    }
                    break;
                }
                else{
                    boardSubLst.insert(coords);
                }
            }
            else{
                break;
            }
        }
        curR+=vecR;
        curC+=vecC;
    }
    return boardSubLst;
}

To make this long story short, in nonPawnBoardGen(), every time I get a new valid board configuration, I edit the board coordinates (white in this case):

coords[index + 16].setRow(curR);
coords[index + 16].setCol(curC);

and add them to a list of board configurations:

boardSubLst.insert(coords);

However, every time I edit coords, each value in the boardSubList linked list changes to the current value of coords. Why is this happening?

EDIT: I think I can avoid this problem just by having nonPawnBoardGen() generate and return only one set of coordinates. The iterator can be saved in the class rather than locally in the function. Each set of coordinates returned can be added directly to the list of children in possibleMoves(). I will try this and see what happens...

Answer 1

I stopped working on my code for awhile, just came back to it and solved the problem. Thank you Elliott and Anantha. You were both right. My array of chess piece coordinates is actually an array of objects, with each object being a set of coordinates. Originally, I changed my code so that I was making a copy of the array each time before editing the coordinates and adding the array to my list, but this was only making new references to the same set of the array's objects. The solution was to not only make new array references, but to allocate new coordinate objects within the array every time I changed coordinates. I think I'm making this sound a lot more convoluted than it actually is, but yes it was a problem of continuously referencing the same area in memory. It was not too obvious. Thanks a lot!

Answer 2

When you call

boardSubLst.insert(coords);

You are passing the same reference to the coords array. I think you will find the easiest solution is to copy the array instead, for example using Arrays.copyOf(T[] original, int newLength)

boardSubLst.insert(Arrays.copyOf(coords, coords.length));

Or, assuming coords is of type Coord[] you could use System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

Coord[] coords2 = new Coord[coords.length];   
System.arraycopy(coords, 0, coords2, 0, coords.length);
boardSubLst.insert(coords2);