1

I want to insert several nodes into an empty singly-linked list. It's OK when I insert the first node. However, the fist node is replaced by the second node when I call the function

the first time using function ListInsert(), the variable newNode is at the memory unit 0x7fffffffdf50. And the second time calling function ListInsert(), *L = 0x7fffffffdf50, **L = {m_Data = first node data, m_nextNode = NULL}. but when I create the newNode, it is still at the memory unit 0x7fffffffdf50. If I set newNode = second node data, it actually replace the first node but not insert into the linked list 

struct t_Node
{
  struct t_Data m_Data;
  struct t_Node *m_nextNode;
}
typedef struct Node* t_LinkedList;

void ListInsert(t_LinkedList* L, int position, struct t_Data newData)
{
  if (!*L)
  {
    struct t_Node newNode;
    newNode.m_Data = newData;
    newNode.m_nextNode = NULL;
    (*L) = &newNode;
  }

  /* first Node is not NULL */
  else
  {
    t_LinkedList anIterator;
    anIterator = (*L);

    if (!(*anIterator).m_nextNode)
    {
      struct t_Node newNode;
      newNode.m_Data = newData;
      newNode.m_nextNode = NULL;

      (*anIterator).m_nextNode = &newNode;
    }
  }
}

t_LinkedList aLinkedList;
aLinkedList = NULL;

ListInsert(&aLinkedList,1,data1);
ListInsert(&aLinkedList,2,data2);

I expect to insert the second node based on the singly linked list with one node but not to replace the first node, and to maintain the structure of the program.

startFromZero
  • 44
  • 3
  • 2
    Are you familiar with `malloc(), free()`? – chux - Reinstate Monica Jul 21 '19 at 04:49
  • Thanks for your last comment. Do you mean initializing the aLinkedList `aLinkedList = (struct t_Node*) malloc(sizeof(struct t_Node))`? If so, the judgement in function ListInsert() that `if (!*L)` is not True. How do I judge if the linked list has no nodes? – startFromZero Jul 21 '19 at 05:18
  • You need to understand that `newNode`, just like every other automatic variable, exists only within the curly brackets it is declared in, and any pointer to it becomes *invalid* as soon as the compound statement has finished. – n. m. could be an AI Jul 21 '19 at 05:20
  • Thanks for your last commment. Do you mean that the `newNode` in the first ListInsert() has been deleted? In my view, after the first time calling function ListInsert(), `aLinkedList` has already pointed to a node(`*aLinkedList` = node with data1). However, the second time, I create a new `newNode` that is different from the node I create in the first ListInsert(). But I don't understand what I should do to insert a new node but not to replace the variable that `*L` points to? – startFromZero Jul 21 '19 at 05:31
  • You do `struct t_Node * newNode = malloc...`, not `aLinkedList = malloc ...` – n. m. could be an AI Jul 21 '19 at 05:37
  • 1
    Your view does not correespond to any objective reality. In reality, after your first call to ListInsert, there is no node your list can.point to. The memory that the node used to occupy is free and will be reused at the next opportunity. – n. m. could be an AI Jul 21 '19 at 05:39
  • thanks for your last comment. I want to pack the process that create a `struct t_node newnode` in the function ListInsert. how to save the structure variable in the outer function that I create in the function ListInsert? or my entire idea about packing the process inserting a node into a list? I should create a struct Node in the outer function but not pass a struct t_Data? – startFromZero Jul 21 '19 at 06:08
  • 2
    I have no idea what you mean by "packing the process". You have to malloc your node struct. Read a good C book. – n. m. could be an AI Jul 21 '19 at 07:13
  • 1
    Stack Overflow is not a tutoring website. You've been given the hint: you need to use `malloc`. Any decent C book will have at least the linked list exercise with `malloc`. – Antti Haapala -- Слава Україні Jul 21 '19 at 10:19

1 Answers1

1

When you create new variable inside a function, the memory for that variable is allocated on the stack, that is why when the function returns the memory is no longer accessible. So we need to dynamically allocate memory in the heap. Read this to get a better idea about heap and stack. Here is the modified version of your code using dynamic allocation. Also note that when allocating memory dynamically, we need to free the memory when we are done using it, therefore I added a deleteList() function to delete the list.

#include<stdio.h>
#include<stdlib.h>

struct t_Node
{
  int m_Data;
  struct t_Node *m_nextNode;
};
typedef struct t_Node* t_LinkedList;

void ListInsert(t_LinkedList* L, int position,  int newData)
{
  struct t_Node * newNode = malloc(sizeof(struct t_Node));
  newNode -> m_Data = newData;
  newNode -> m_nextNode = NULL;
  if (!*L)
  {
    (*L) = newNode;
  }

  /* first Node is not NULL */
  else
  {
    t_LinkedList anIterator;
    anIterator = (*L);

    if (!(*anIterator).m_nextNode)
    {
      (*anIterator).m_nextNode = newNode;
    }
  }
}
void printList(t_LinkedList list)
{
  while(list != NULL)
  {
    printf("%d\n", list->m_Data);
    list = list -> m_nextNode;
  }
}
void deleteList(t_LinkedList list)
{
  t_LinkedList node = list -> m_nextNode;
  while(node)
  {
    free(list);
    list = node;
    node = node -> m_nextNode;
  }
}
int main()
{
  t_LinkedList aLinkedList;
  aLinkedList = NULL;

  ListInsert(&aLinkedList,1,10);
  ListInsert(&aLinkedList,2,20);
  printList(aLinkedList);
  deleteList(aLinkedList);
  return 0;
}
LetAptimus
  • 61
  • 3