• AVR Freaks

Hot!How to write function to add node in list

Page: 123 > Showing page 1 of 3
Author
abhi143
Junior Member
  • Total Posts : 110
  • Reward points : 0
  • Joined: 2018/05/20 09:06:52
  • Location: 0
  • Status: offline
2020/02/27 20:29:47 (permalink)
0

How to write function to add node in list

I want to add each new node at last of list. it's standard c question,  Perhaps I should not ask this question on this forum But I think people who know about this can help me
 
I can create a list without writing any function
 

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

struct node
{
int value;
struct node *next;
};
int main ()
{
struct node *first = NULL;
struct node * second = NULL;

second = malloc (sizeof(*second));
second->value = 100;
second-> next = first;

printf ("value in Node 1 = %d \n", second->value);

struct node * third = malloc (sizeof(*third));
third -> value = 200;
third -> next = second ;
printf ("value in Node 2 = %d \n", third->value);

struct node * fourth = malloc (sizeof(*fourth));
fourth -> value = 300;
fourth -> next = third ;
printf ("value in Node 3 = %d \n", fourth->value);

return 0;
}

 
value in Node 1 = 100
value in Node 2 = 200
value in Node 3 = 300
 

I want to understand this only through my example But this method of creating a list is not good, so I want to write a function that adds a each new node to the last of the list. I hope someone will help me
 
#1

45 Replies Related Threads

    ric
    Super Member
    • Total Posts : 26159
    • Reward points : 0
    • Joined: 2003/11/07 12:41:26
    • Location: Australia, Melbourne
    • Status: online
    Re: How to write function to add node in list 2020/02/27 21:12:06 (permalink)
    +1 (1)
    You have asked in the 8 bit PIC forum, but the 8 bit C compilers don't support malloc, so it's plainly not for use on a PIC...
     
    The sort of code you are trying to write would be horrendously inefficient to run on a small microcontroller anyway.
    What are you actually trying to achieve?
     

    I also post at: PicForum
    Links to useful PIC information: http://picforum.ric323.co...opic.php?f=59&t=15
    NEW USERS: Posting images, links and code - workaround for restrictions.
    To get a useful answer, always state which PIC you are using!
    #2
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 3835
    • Reward points : 0
    • Joined: 2015/04/30 10:49:57
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/27 21:19:15 (permalink)
    0
    Best to get the structure correct before attempting any code.
     
    The basic structures (In my code)
     
    This will give you something to work on.
    //----------------------------------------------------
    typedef struct{
        struct Object_t    *Prev;
        struct Object_t    *Next;
        struct List_t      *List;
        int                 Flag;
    }Object_t;
    //----------------------------------------------------
    typedef struct{
        struct Object_t    *ItemTail;
        struct Object_t    *ItemHead;
        struct List_t      *ListPrev;
        struct List_t      *ListNext;
        int                 Items;
        int                 Flag;
    }List_t;
    //----------------------------------------------------




    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #3
    abhi143
    Junior Member
    • Total Posts : 110
    • Reward points : 0
    • Joined: 2018/05/20 09:06:52
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/27 21:46:09 (permalink)
    -1 (1)
    ric
    You have asked in the 8 bit PIC forum, but the 8 bit C compilers don't support malloc, so it's plainly not for use on a PIC...
     
    The sort of code you are trying to write would be horrendously inefficient to run on a small microcontroller anyway.
    What are you actually trying to achieve?

    I had  mentioned  that this question is not related to micro. I wrote the program for the linked list in the c language and tested it on the PC
     
    When I run code I get following output
    value in Node 1 = 100
    value in Node 2 = 200
    value in Node 3 = 300
     
    I want to write a function that adds a each new node to the last of the list. I am struggling with function ?
     
    #4
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 3835
    • Reward points : 0
    • Joined: 2015/04/30 10:49:57
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/27 22:17:33 (permalink)
    +2 (2)
    You struggle because you do not understand the concept.
    It's such a simple answer.
     
    Is this for School homework ?

    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #5
    Mysil
    Super Member
    • Total Posts : 3667
    • Reward points : 0
    • Joined: 2012/07/01 04:19:50
    • Location: Norway
    • Status: offline
    Re: How to write function to add node in list 2020/02/27 23:15:44 (permalink)
    +3 (3)
    Hi,
    This is my opinion:
    In a small microcontroller, the only sensible way to handle a list of objects, is by using a fixed size array.
    It may be an array of single variables, or an array of struct objects, something like:
    #define  MAX_NODES  10
    typedef  struct node
    {    int value;
        struct node *next;
    }  node_t;
    static  node_t   node_list[MAX_NODES];       /* Array of nodes. */
    static  node_t  *pFirstNode =   &node_list[0];   /* Pointer to first node. */
    static  node_t  *pLastNode  =   &node_list[0];   /* Pointer to last node. */
    static  node_t  *pCurrentNode = NULL;

     
    To be able to add another node to the queue,
    you will need to keep a pointer or index to the last node inserted, outside of the list itself, 
    othervise you will have to search thru all the entries to find the end node.
     
    Similarly, if you want to remove the first node from the list,
    you will need another pointer or index to the first node that now is valid, also outside the list itself.
     
    If you want to remove or insert a node in between other nodes in the linked list,
    then you will need 2 pointers in each entry, pointer to Next entry, and pointer to Previous entry.
     
    If you know that entries are always inserted in one end of the list,
    and always removed from the other end,
    then you have a circular buffer, and do not actually need to keep pointers in the list itself,
    just the pointers to the Insert point, and Extract point are sufficient.
     
    When a circular buffer is stored in a fixed size array, and the last position in the array is used,
    then the next pointer to use is the start of the array.
     
    Anyway, whether nodes are allocated dynamically, or are stored in a array,
    You will need to handle the case when there are no more space available for another entry.
     
    MCC driver for UART peripheral can show you a circular buffer of bytes. 
     
    A 8 bit PIC microcontroller, is able to increment or decrement a 8 bit index or pointer in a single instruction.
    If a array is  larger than 80 bytes in a PIC10, PIC12 or PIC16 device, then pointers will have to be 2 bytes.
    Then pointer cannot be incremented or decremented in a single atomic instruction,
    and if your datastructure is used to communicate between Interrupt code, and code called from main,
    then additional precautions may be needed.
     
    Any textbook on C programming should have a chapter on linked lists and similar structures.
     
        Mysil
    #6
    abhi143
    Junior Member
    • Total Posts : 110
    • Reward points : 0
    • Joined: 2018/05/20 09:06:52
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 01:06:05 (permalink)
    0
    Gort2015Is this for School homework ?

    No, All I am doing is to convert my logic into code.
    Gort2015
    You struggle because you do not understand the concept.

     I understand the concept, that's why I wrote the code and shown the result. I am struggling to create function only 
    you can check code online here https://www.onlinegdb.com/online_c_compiler
     
     
    #7
    pcbbc
    Super Member
    • Total Posts : 1649
    • Reward points : 0
    • Joined: 2014/03/27 07:04:41
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 03:29:03 (permalink)
    +1 (1)
    MysilIf you want to remove or insert a node in between other nodes in the linked list,
    then you will need 2 pointers in each entry, pointer to Next entry, and pointer to Previous entry.

    Generally yes.
     
    But with only a Next pointer you could search the list again (if you don't mind the overhead) and find the item you are removing.  Then you'll "know" the previous item.  It's not hugely efficient, but on a limited footprint 8-bit device it may well suffice and save some complexity (and space) of a doubly linked list.
     
    Regardless of if this is homework or not, you (or your tutor) seem to have chosen the wrong platform for your areas of study.  RTOS and malloc are not concepts well suited to very limited resource embedded 8-bit products.  Not trying to put you off, but you'd be better investigating such programming concepts elsewhere.  Once you have the fundamentals nailed down you can apply them to embedded programming, and have the skill set to realise why they may not be appropriate...
    #8
    abhi143
    Junior Member
    • Total Posts : 110
    • Reward points : 0
    • Joined: 2018/05/20 09:06:52
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 05:08:13 (permalink)
    -1 (1)
    pcbbc
     Regardless of if this is homework or not, you (or your tutor) seem to have chosen the wrong platform for your areas of study.  Once you have the fundamentals nailed down you can apply them to embedded programming, and have the skill set to realise why they may not be appropriate...

    Looks a little bit negative.  C code runs on the PC while embedded C code runs on the micro-controller. I don't see much difference between embedded C and C programming. linked list is one of the concept of c language and I am trying to understand it. It's not related to microcontroller  
     
    First I made a diagram for the linked list using paper and pencil. After that I wrote the code for my list. I have already posted the code as well as the result. If you want, you can also view the code by running it on the online compiler.
     
    My question was that I want to write a function for my list But I do not understand how to write this function. So I posted my question on the forum.  I hope someone will help me 
    #9
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 3835
    • Reward points : 0
    • Joined: 2015/04/30 10:49:57
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 05:28:36 (permalink)
    +1 (1)
    You need better memory management than malloc, reserve memory then hand this over to MM.
     
    New objects always get appended to the end with new by default.
     

    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #10
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 3835
    • Reward points : 0
    • Joined: 2015/04/30 10:49:57
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 05:52:12 (permalink)
    0
    You need to get a full understanding otherwise it will always be complicated when it need not be.
     
    Swapping two objects.
    .include    "ObjectLib3.inc"
    .global     _obj_swap
    ;----------------------------------------------------
    .section    objectcode3, code
    ;----------------------------------------------------
    arg_ObjectX    =  w0
    X              =  w0
    arg_ObjectY    =  w1
    Y              =  w1
    XN             =  w2
    XP             =  w3
    flag           =  w4
    tmp            =  w5
    SP             = w15
    ;rtn error        w0

    _obj_swap:     ;int obj_swap(Object_t *O1, Object_t *O2);
        ;null?
        cp0        X
        bra        z,error_null
        cp0        Y
        bra        z,error_null
        ;--------------------------------------
        ;locked?
        mov        [X+O_Flag],flag
        btsc       flag,#OFLAG_LOCK
        bra        error_lock
        mov        [Y+O_Flag],flag
        btsc       flag,#OFLAG_LOCK
        bra        error_lock
        ;--------------------------------------
        ;same?
        cp         X,Y
        bra        z,exit_ok
        ;--------------------------------------
        ;side by side, X->Next = Y?
        mov        [X+O_Next],XN
        cp         Y,XN
        bra        nz,chkprev
        ;--------------------------------------
        ;exchange
        exch       X,Y
        bra        move
        ;--------------------------------------
    chkprev:
        ;side by side, X->Prev = Y
        mov        [X+O_Prev],XP
        cp         Y,XP
        bra        nz,dual
        ;--------------------------------------
    move:
        ;move X only
        push.d     X
        rcall      _obj_remove        ;unlink X
        pop.d      w0
        rcall      _obj_insert        ;insert X to Y
        bra        exit_ok
        ;--------------------------------------
    dual:
        ;swap X and Y if X = Tail
        mov        [X+O_Flag],flag
        btsc       flag,#OFLAG_TAIL
        exch       X,Y
        ;--------------------------------------
        mov        [X+O_Next],XN
        push       XN
        push.d     X
        rcall      _obj_remove        ;unlink X
        mov        [SP-2],w1          ;Y
        mov        [SP-4],w0          ;X
        rcall      _obj_insert        ;insert X to Y
        ;--------------------------------------
        mov        [SP-2],w0          ;y
        rcall      _obj_remove       ;unlink Y
        pop        w0                 ;Y
        dec2       SP,SP
        pop        w1                 ;XN
        rcall      _obj_insert        ;insert Y to X->N
        ;--------------------------------------
    exit_ok:
        clr        O_Error
        retlw      #OERR_OK,w0
        ;--------------------------------------
    error_lock:
        mov        #OERR_LOCK,w0
        bra        $+4
        ;--------------------------------------
    error_null:
        mov        #OERROR_NULL,w0
        mov        w0,O_Error
        return
    ;----------------------------------------------------
    .end

    post edited by Gort2015 - 2020/02/28 05:56:12

    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #11
    LdB_ECM
    Super Member
    • Total Posts : 313
    • Reward points : 0
    • Joined: 2019/04/16 22:01:25
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 06:05:18 (permalink)
    0 (2)
    I agree with what everyone has said and personally would do it the mysil way.
     
    However for portability sometimes that is not desirable and in those situation it is trivial to make a malloc function for any MCU. You just take a static block of memory and dish it out when requested.
     
    Portability is why FreeRTOS does it that way and it provides 5 well tested schemes called heap1 to heap5
    https://github.com/FreeRTOS/FreeRTOS-Kernel/tree/10bbbcf0b9bcab1869b3bac3987d32116f351718/portable/MemMang
     
    The 5 different modes are described here
    https://www.freertos.org/a00111.html
     
    It is easy enough to free them of the FrreRTOS header includes and they are free to use.
     
    I am with the rest of you this looks like a suck it and see exercise by the OP but he can do actual reading if he really wants to do it.
    #12
    1and0
    Access is Denied
    • Total Posts : 10588
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 12:05:42 (permalink)
    +2 (2)
    abhi143
     
    I had  mentioned  that this question is not related to micro. I wrote the program for the linked list in the c language and tested it on the PC
     
    ...
    I want to write a function that adds a each new node to the last of the list. I am struggling with function ?


    This is an 8-bit PIC microcontrollers forum, so your C question for PC is out of place.
     
    Having said that, for what it's worth, I think this will do what you've asked; i.e. add a new node to the end of a singly linked list.
    #include<stdio.h>
    #include<stdlib.h>
     
    struct node {
        int value;
        struct node *next;
    };

     

    struct node *start = NULL;

     

    void insert(int val);
    void display(void);

     

    int main ()
    {
        insert(100);
        insert(200);
        insert(300);
        display();
        return 0;
    }

     

    void insert(int val)
    {
        struct node *temp, *ptr;
        temp = (struct node *) malloc(sizeof(struct node));
        if (temp == NULL) {
            printf("Out of Memory.\n");
            return;
        }
        temp->value = val;
        temp->next = NULL;
       
        if (start == NULL) {
            start = temp;
        } else {
            ptr = start;
            while (ptr->next != NULL) {
                ptr = ptr->next;
            }
            ptr->next = temp;
        }
    }

     

    void display(void)
    {
        struct node *ptr;
        if (start == NULL) {
            printf("List is empty.\n");
            return;
        } else {
            printf("List elements are:\n");
            ptr = start;
            while (ptr != NULL) {
                printf("%d\n", ptr->value);
                ptr = ptr->next;
            }
        }
    }
    #13
    1and0
    Access is Denied
    • Total Posts : 10588
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 12:07:25 (permalink)
    +1 (1)
    Stupid forum is messing up the code tag. I'm not going to waste my time fixing it. :(
     
    #14
    crosland
    Super Member
    • Total Posts : 1886
    • Reward points : 0
    • Joined: 2005/05/10 10:55:05
    • Location: Warks, UK
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 13:12:19 (permalink)
    +4 (4)
    abhi143
    Looks a little bit negative.  C code runs on the PC while embedded C code runs on the micro-controller. I don't see much difference between embedded C and C programming. linked list is one of the concept of c language and I am trying to understand it. It's not related to microcontroller  



    But it is related when the microcontroller has very little memory (a few kB compared to a PC (a few GB) and does not support malloc. Until you understand such basic differences between the two environments, the answers will continue to seem negative.
    #15
    NKurzman
    A Guy on the Net
    • Total Posts : 18424
    • Reward points : 0
    • Joined: 2008/01/16 19:33:48
    • Location: 0
    • Status: online
    Re: How to write function to add node in list 2020/02/28 15:23:46 (permalink)
    +1 (1)
    crosland
    abhi143
    Looks a little bit negative.  C code runs on the PC while embedded C code runs on the micro-controller. I don't see much difference between embedded C and C programming. linked list is one of the concept of c language and I am trying to understand it. It's not related to microcontroller  

    But it is related when the microcontroller has very little memory (a few kB compared to a PC (a few GB) and does not support malloc. Until you understand such basic differences between the two environments, the answers will continue to seem negative.



    Seconded.  If you think C is fully portable between and 8-bit PIC and a 64bit PC, you will find a lot of disappointment.
    Also Note that C may not be fully portable across Different chip makers and even different brand compilers made for the same CPU.
    #16
    1and0
    Access is Denied
    • Total Posts : 10588
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: How to write function to add node in list 2020/02/28 18:24:55 (permalink)
    0
    NKurzman
     
    Seconded.  If you think C is fully portable between and 8-bit PIC and a 64bit PC, you will find a lot of disappointment.
    Also Note that C may not be fully portable across Different chip makers and even different brand compilers made for the same CPU.

    OP will just have to learn it by experience; i.e. find out the hard way. ;)
     
    #17
    abhi143
    Junior Member
    • Total Posts : 110
    • Reward points : 0
    • Joined: 2018/05/20 09:06:52
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/29 07:55:52 (permalink)
    0
    1and0
    I think this will do what you've asked; i.e. add a new node to the end of a singly linked list.
     
    Stupid forum is messing up the code tag. I'm not going to waste my time fixing it. :(

    Yes program add each new node at last of list. I understand function  Its simple way to add new node at end 

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

    struct node {
    int value;
    struct node *next;
    };
    struct node *start = NULL;

    void insert(int val);
    void display(void);

    int main ()
    {
    insert(100);
    insert(200);
    insert(300);
    display();
    return 0;
    }

    void insert(int val)
    {
    struct node *temp, *ptr;
    temp = (struct node *) malloc(sizeof(struct node));
    if (temp == NULL) {
    printf("Out of Memory.\n");
    return;
    }
    temp->value = val;
    temp->next = NULL;

    if (start == NULL) {
    start = temp;
    } else {
    ptr = start;
    while (ptr->next != NULL) {
    ptr = ptr->next;
    }
    ptr->next = temp;
    }
    }

    void display(void)
    {
    struct node *ptr;
    if (start == NULL) {
    printf("List is empty.\n");
    return;
    } else {
    printf("List elements are:\n");
    ptr = start;
    while (ptr != NULL) {
    printf("%d\n", ptr->value);
    ptr = ptr->next;
    }
    }
    }

     
    I was trying to understand this function https://en.wikipedia.org/wiki/Linked_list

    node addNode(node head, int value) {
    node temp, p; // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL.
    temp->data = value; // add element's value to data part of node
    if (head == NULL) {
    head = temp; // when linked list is empty
    }
    else {
    p = head; // assign head to p
    while (p->next != NULL) {
    p = p->next; // traverse the list until p is the last node. The last node always points to NULL.
    }
    p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
    }

    #18
    1and0
    Access is Denied
    • Total Posts : 10588
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: How to write function to add node in list 2020/02/29 08:18:46 (permalink)
    0
    abhi143
    Yes program add each new node at last of list. I understand function  Its simple way to add new node at end 
     
    I was trying to understand this function https://en.wikipedia.org/wiki/Linked_list

    If you've understood my function, what part of the function from wikipedia you do not understand?  They are very similar except it also returns the head of the linked list.
    #19
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 3835
    • Reward points : 0
    • Joined: 2015/04/30 10:49:57
    • Location: 0
    • Status: offline
    Re: How to write function to add node in list 2020/02/29 08:37:26 (permalink)
    0
    Ignore code, it is the logic that you should look into.
     
    The last object:
     
    head
    obj -> next = NULL
    obj -> prev = ptr to previous
     
     
    Inside "new":
    1 SizeT == 0? exit
    2. calloc SizeT of object checking for null
    3. append to list
     
    Append:
    1. new -> next = NULL (already clear  but looks neater)
    2. new -> prev = head
    3. head -> next = new
    4. head = new
     

    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #20
    Page: 123 > Showing page 1 of 3
    Jump to:
    © 2020 APG vNext Commercial Version 4.5