Like Tree1Likes
  • 1 Post By Cat

Linked List - inserting nodes

This is a discussion on Linked List - inserting nodes within the C Programming forums, part of the General Programming Boards category; I'm trying to create a function that allows insertion anywhere in a linked list...here is what I have so far ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    100

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

  2. #2
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    Don't use "ll", it looks like 11.
    Don't cast what malloc returns
    Check that the malloc succeeded before using it

    Usually, when you want to insert a node somewhere in the list, you would call a "search" function for a certain node, and then make
    Code:
    /* Where new_node is insearted after node */
    new_node->next = node->next
    node->next = new_node;
    There is lots of code and algorithms out there for singally linked lists
    Fact - Beethoven wrote his first symphony in C

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    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.

  4. #4
    Registered User
    Join Date
    Feb 2013
    Posts
    100
    Quote Originally Posted by anduril462 View Post
    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;
        
    }

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    Quote Originally Posted by johngoodman View Post
    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;
        
    }
    You didn't follow ANY advice.

    I'm out.
    Fact - Beethoven wrote his first symphony in C

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    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.

  7. #7
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Please don't continue to create more and more duplicate threads for the same thing.
    Salem likes this.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Line 11 is rather amusing.
    Read the FAQ about why you shouldn't cast malloc.
    Don't call malloc to allocate two nodes when you are only inserting one. I don't know what you ever thought was going to happen to the other one. It's what one calls a memory leak, and in this case both of them are actually being leaked.
    But hey that's what you get when trying to incorrectly solve the wrong problem, and not having much clue about how pointers or dynamic memory allocation works.

    Well as I already stated in one of the many other redundant threads, I'm not going to help you solve the wrong problem. You don't "add at index" with a linked-list. THat's not what they are for.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked list and nodes
    By Lina_inverse in forum C Programming
    Replies: 2
    Last Post: 10-23-2012, 01:59 PM
  2. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  3. inserting strings into linked list nodes
    By occams razor in forum C Programming
    Replies: 8
    Last Post: 03-31-2007, 12:17 AM
  4. Linked List and Nodes
    By paperbox005 in forum C++ Programming
    Replies: 2
    Last Post: 08-04-2004, 09:12 AM
  5. Inserting new nodes in a sorted double linked list
    By carrja99 in forum C++ Programming
    Replies: 2
    Last Post: 03-07-2003, 07:34 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21