0

I am given a task to simulate a linked list structure, but using an array of Nodes rather than an actual linked list. When I call my append function, I want to check to see if my existing array is full, and if it is, I want to double the array size, and append my Node to the end of the "list" (array).

I am having trouble doubling my array size.

To give you context, here is my some of my .h file: 

...
const int NULL_INDEX = -1;

struct Node {
    char info;
    int next;
};

class LList1 {

private:
    Node free [4];

    // When more memory is called for, the array will double in size
    // returns true if reallocation of memory was successful
    bool doubleSize();
    .
    .
    .
}

and here is the part of my .cpp file that tries to double the array size:

bool LList1::doubleSize() {
    Node* newArray = new Node[this->length()*2];
    memcpy(newArray, free, this->length()*2);
    free = newArray;
    return true;
}

I also tried using realloc and other functions. I keep having the same problem. The line 

"free = newArray"

keeps giving me this error in XCode: "Array type 'Node[4]' is not assignable"

Please give me some insight into a better way to do this. All solutions online seem to work fine for arrays of ints, but not for my array of Nodes.

Much appreciated.

Priya Gill
  • 67
  • 1
  • 5
  • `Node free [4];` is a not a resizable array. Also `new Node[this->length()*2];` returns a pointer to the newly allocated array. `free` is not a pointer that can be re-assigned – Rohith R Sep 26 '16 at 07:03
  • That wouldn't work for an array of `int` either; you must be doing something differently for those. Your member needs to be a pointer. – molbdnilo Sep 26 '16 at 07:16
  • What you are describing seems more like a dynamic sized array ([vector](http://en.cppreference.com/w/cpp/container/vector)), rather than a linked list. – A. Sarid Sep 26 '16 at 07:20
  • @A.Sarid It's a linked list "inside" an array (`next` is the index of the next node). – molbdnilo Sep 26 '16 at 07:52

2 Answers2

1

A couple of things are incorrect in your code:

  1. Your free property is a static array. In your case you need a dynamic one, with proper constructor.
  2. The memcpy command takes the size in bytes, hence you need to multiply by sizeof(Node).
  3. Perhaps it was intended, but the doubleSize() method was private.

Here is a corrected version of the code that compiles and runs:

...
const int NULL_INDEX = -1;

struct Node {
    char info;
    int next;
};

class LList1 {
public:
    LList1();
    ~LList1();
    int getLength();
    bool doubleSize();

private:
    int length;
    Node* free;

    // When more memory is called for, the array will double in size
    // returns true if reallocation of memory was successful
};

int LList1::getLength() {
    return this->length;
}

LList1::LList1() {
    this->free = new Node[4]; // Default size
    this->length = 4;
}

LList1::~LList1() {
    delete []this->free;
}

bool LList1::doubleSize() {
    Node* newArray = new Node[this->length*2];
    memcpy(newArray, free, this->length * sizeof(Node));
    free = newArray;
    this->length *= 2;
    return true;
}


int main(int, char **) {
    LList1 l;
    std::cout << "Original length: " << l.getLength() << std::endl;
    l.doubleSize();
    std::cout << "After doubling length: " << l.getLength() << std::endl;
    return 0;
}
Fabien Bouleau
  • 464
  • 3
  • 11
0

You are getting confused between arrays and pointers. Your variable free is a constant pointer which cannot be reassigned. You need to change Node free [4] to Node *free if you want to modify its value.

C/C++ int[] vs int* (pointers vs. array notation). What is the difference?

Community
  • 1
  • 1
mchouhan_google
  • 1,775
  • 1
  • 20
  • 28