Thread: Linked List - inserting nodes

I'm trying to create a function that allows insertion anywhere in a linked list...here is what I have so far but am a bit confused on where to go from here

Code:

void llAddAtIndex(LinkedList** ll, char* value, int index) {

  LinkedList* newNode = (LinkedList*)malloc(sizeof(ll));
  newNode = *ll;
  LinkedList* prevNode = (LinkedList*)malloc(sizeof(ll));
  
  if(index == 0){
    newNode->next = newNode;
    newNode = newNode;
    }
  for(int i = 0; i < index; i++){
      prevNode = newNode;
    newNode = newNode->next;
  }
    
}

Click_here gave some good advice, especially the "ll" part. Also

Code:

LinkedList* newNode = (LinkedList*)malloc(sizeof(ll));
newNode = *ll;

That is a memory leak. You malloc memory and store the address in newNode. Then you immediately overwrite that address with *ll, so you lose it. You have no way of passing it to free() to free it. You have a similar problem with prevNode, which I don't think you need to malloc at all.

Code:

malloc(sizeof(ll))

That is the wrong size. ll is a pointer to pointer to LinkedList type. You need to allocate enough space to store an actual LinkedList node. That would be malloc(sizeof(LinkedList)), or even better yet

Code:

LinkedList *newNode;
newNode = malloc(sizeof(*newNode));

Notice how I use the variable name in the sizeof expression, not the type name. That way, if the type of newNode ever changes, you only need to change it in one place (the declaration). The malloc call will always allocate the correct amount of memory.

Originally Posted by anduril462

Click_here gave some good advice, especially the "ll" part. Also

Code:

LinkedList* newNode = (LinkedList*)malloc(sizeof(ll));
newNode = *ll;

That is a memory leak. You malloc memory and store the address in newNode. Then you immediately overwrite that address with *ll, so you lose it. You have no way of passing it to free() to free it. You have a similar problem with prevNode, which I don't think you need to malloc at all.

Code:

malloc(sizeof(ll))

That is the wrong size. ll is a pointer to pointer to LinkedList type. You need to allocate enough space to store an actual LinkedList node. That would be malloc(sizeof(LinkedList)), or even better yet

Code:

LinkedList *newNode;
newNode = malloc(sizeof(*newNode));

Notice how I use the variable name in the sizeof expression, not the type name. That way, if the type of newNode ever changes, you only need to change it in one place (the declaration). The malloc call will always allocate the correct amount of memory.

Here is my altered code, it seems a bit closer but not quite there...it's hard to mental figure out what is going on

Code:

void llAddAtIndex(LinkedList** ll, char* value, int index) {

  LinkedList* newNode;
  newNode = (LinkedList*)malloc(sizeof(*newNode));
  newNode = *ll;
  LinkedList* prevNode = (LinkedList*)malloc(sizeof(*newNode));
  prevNode = *ll;
  
  if(index == 0){
    newNode->next = newNode;
    newNode = newNode;
    }
  for(int i = 0; i < index; i++){
      newNode->next = prevNode->next;
    prevNode->next = newNode;
  }
  prevNode->value = value;
    
}

Still lots of problems. I recommend you put the keyboard away for now. Start by reading lots of tutorials. Then, get out the paper and pencil. Keep drawing lists, and practicing inserting nodes at the beginning, in the middle and at the end. Pay careful attention to every little step you take, that will become your algorithm. Once you actually understand how to implement a linked list on paper, then you can begin coding.