C++ - Insertion in a Linked List without using a node's constructor. Is it possible?

Question

I'm working on implementing a Templated Linked List in C++ that will be used to simulate a train moving through numerous stops where traincars are both added and removed. Traincar is its own class and each object is supposed to be given a unique ID starting with 1 and incremented when a car is added. However, when running my code, the id is being incremented more than it is supposed to.

After some experimentation and with help from previous answers, I have determined that it is the new node statements within my LinkedList class methods that are causing the id to be incremented more than wanted. However, I do not see a way to implement insertion methods without creating a new node. Is there any way around this?

Here is my TrainCar class:

class TrainCar {
public:
  static int nextID;
  int id;
  char typeOfCar;
  int numberOfStops;
  node<char>* car;

  TrainCar();
};

int TrainCar::nextID = 1;

TrainCar::TrainCar() {
  cout << "id++" << endl;
  id = nextID++;
  int i = (rand() % 3);//gives a random number 0 - 2, used to determine what
                       //type of car to add
  if(i == 0) {
    typeOfCar = 'P';
  }
  else if(i == 1) {
    typeOfCar = 'C';
  }
  else {
    typeOfCar = 'M';
  }
  car = new node<char>(typeOfCar);
  numberOfStops = (rand() % 5) + 1;//gives a random number 1 - 5;
}

Here is my main() function

int main() {
  LinkedList<TrainCar> train;
  int addCargoCar = 0;

  for(int i = 0; i < 10; i++) {
    TrainCar newCar;
    if(newCar.typeOfCar == 'P') {
      train.AddToFront(newCar);
      addCargoCar++;
    }
    else if(newCar.typeOfCar == 'C') {
      train.AddAtIndex(newCar, addCargoCar);
    }
    else {
      train.AddToEnd(newCar);
    }
  }

  cout <<"Welcome to the Train Station! Here is your train!" << endl;
  char type;
  int id, numberOfStops, i, j;
  for(i = 0; i < train.size; i++) {
    type = train.Retrieve(i).typeOfCar;
    id = train.Retrieve(i).id;
    numberOfStops = train.Retrieve(i).numberOfStops;
    cout << "[" << id << ":" << type << ":" << numberOfStops << "] ";
  }
}

The output should be something similar to

[5:P:1][6:P:4][8:P:2][3:P:2][10:C:3][2:C:3][4:C:1][1:M:1][7:M:3][9:M:2]

But my output is:

[17:P:2][9:P:2][5:C:2][19:C:1][15:C:2][1:M:5][3:M:4][7:M:1][11:M:3][13:M:1]

Edit: Here is the AddToFront() method: (all other add methods are similar in nature). The issue with the output is the new node<T>(d) statements

template <class T>
void LinkedList<T>::AddToFront(T d) {
  node<T>* newNode = new node<T>(d);

  if(head == NULL) {
    head = newNode;
    tail = newNode;
    size++;
  }

  else {
    newNode->next = head;
    head = newNode;
    size++;
  }
}

Edit2: Here is my Retrieve function (now fixed, it no longer uses a new node statement):

template <class T>
T LinkedList<T>::Retrieve(int index) {
  node<T>* cur = head;
  for(int i = 0; i < index; i++) {
    cur = cur->next;
  }
  return(cur->data);
}

Answer 1

You have the right idea to use a static member variable to keep track of identifiers. But you can't use only that.

The static member variable is a member of the class and not any specific object. Therefore all object share the same id.

Use a static member to keep track of the next possible id, and then use a non-static member variable to store the actual id for the object.

Something like

class TrainCar {
public:
    static int next_id;  // Used to get the id for the next object
    int id;  // The objects own id
    ...
};

TrainCar::TrainCar() {
    id = next_id++;  // Get next id and save it
    ...
}

You should probably also have a copy-constructor and copy-assignment operator, otherwise you could get two objects with the same id.

---

Regarding

Why are the id values so high and why are they being incremented by more than one each time?

That's because you probably create more objects than you expect. With the code you show, as well as with the change suggested above, you will create a new id for every object that is default-constructed. And depending on what your LinkedList template class is doing (why don't you use std::vector) there might be new objects created.

An educated guess is that the Retreive function of your list class default constructs the object it contain. That's why you get three objects constructed when printing, as you call Retrieve three times. Probably a similar story about your Add functions.