CODEWITHSUNDEEP
c++dynamicnodes
Priya Gill
Priya Gill

Reputation: 67

Array-style Linked list implementation C++

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.

Upvotes: 0

Views: 542

Answers (2)

mchouhan
mchouhan

Reputation: 1873

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?

Upvotes: 0

Fabien Bouleau
Fabien Bouleau

Reputation: 464

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

Upvotes: 1

Related Questions