Thread: linked list code example

  1. #1
    Registered User
    Join Date
    Jul 2020
    Posts
    28

    linked list code example

    Hi
    anyone can help me to understand following sample example code for linked list
    Code:
    struct Node{
        int Value;
        struct Node *Next;
    };
     
    struct LinkedList
    {
        struct Node *Head;
        struct Node *Tail;
    };
     
    void appendNode(struct LinkedList *List, int value)
    {
        /* ... */
    }
     
    int main(void)
    {
        struct LinkedList List = {NULL, NULL};
        appendNode(&List, 123);
        /* destroy the linked list when done
           ... */
        return 0;
    }
    There are two structures in code I understand structure Node is use for Nodes but I don't have any idea of second structure LinkedList

    Code:
      struct LinkedList List = {NULL, NULL};
    I am confused in above line of code. List is pointer but It's initialized two times with NULL value

  2. #2
    Registered User
    Join Date
    Oct 2019
    Posts
    46
    Quote Originally Posted by Djsarkar View Post
    Code:
     
    struct LinkedList
    {
        struct Node *Head;
        struct Node *Tail;
    };

    Code:
      
    
    struct LinkedList List = {NULL, NULL};
    I am confused in above line of code. List is pointer but It's initialized two times with NULL value
    That initializes the variables in 'LinkedList' to NULL. After this this, the pointer List.Head and List.Tail are both NULL.

    Kindly note the declaration declares a 'LinkedList' object on the stack and not a pointer to an object of 'LinkedList'. In the later case would have looked like:

    Code:
    struct LinkedList *List = NULL;
    Last edited by ghoul; 10-02-2021 at 03:09 AM.

  3. #3
    Registered User
    Join Date
    Jul 2020
    Posts
    28
    Quote Originally Posted by ghoul View Post
    That initializes the variables in 'LinkedList' to NULL. After this this, the pointer List.Head and List.Tail are both NULL.

    Kindly note the declaration declares a 'LinkedList' object on the stack and not a pointer to an object of 'LinkedList'. In the later case would have looked like:

    Code:
    struct LinkedList *List = NULL;
    Code:
      struct LinkedList List = {NULL, NULL};
    Do these two lines means same or Is there a difference between two lines ?

  4. #4
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    Quote Originally Posted by Djsarkar View Post
    Code:
    struct LinkedList *List = NULL;
    Code:
      struct LinkedList List = {NULL, NULL};
    Do these two lines means same or Is there a difference between two lines ?
    They are different.

    The first is a NULL pointer to a LinkedList struct object that would be created later on the heap using malloc() or calloc().

    The second is an actual LinkedList object that has been defined preferably as a local variable on the stack. You should avoid global variables if possible.

    NULL is used to set a pointer to some implementation defined value. If a pointer does not point to some actual data, it should be set to NULL. If a NULL pointer is de-referenced, it should result in a segmentation error.

    All local variables should initialized to 0, NULL, or some usable value depending on the data types. The members of a struct no matter where it is created should be initialized as well.

    A good book on the C Programming Language would give you all the information on Pointers, plus creating and using structs. Later a good book on Data Structures and Algorithms would instruct you on Linked Lists and other data structures.
    Last edited by rstanley; 10-02-2021 at 05:49 AM.

  5. #5
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    Quote Originally Posted by Djsarkar View Post
    Hi
    anyone can help me to understand following sample example code for linked list
    Code:
    struct Node{
        int Value;
        struct Node *Next;
    };
     
    struct LinkedList
    {
        struct Node *Head;
        struct Node *Tail;
    };
     
    void appendNode(struct LinkedList *List, int value)
    {
        /* ... */
    }
     
    int main(void)
    {
        struct LinkedList List = {NULL, NULL};
        appendNode(&List, 123);
        /* destroy the linked list when done
           ... */
        return 0;
    }
    There are two structures in code I understand structure Node is use for Nodes but I don't have any idea of second structure LinkedList

    Code:
      struct LinkedList List = {NULL, NULL};
    I am confused in above line of code. List is pointer but It's initialized two times with NULL value
    A "List" will minimally be a pointer to the first of one or more "Nodes" that contain data. "Next" in each Node will point to the next node in the list, and the last node "Next" pointer will be set to NULL, indicating there are no more nodes in the list.

    The second struct, LinkedList contains two pointers. "Head" will point to the first node in the list, and "Tail" will point to the last node in the list. If there is only one node in the list, the both Head and Tail will point to the same node.

    The example code you showed is really a mix of a "Single" linked list, and a "Double" linked list.

  6. #6
    Registered User
    Join Date
    Jul 2020
    Posts
    28
    Quote Originally Posted by rstanley View Post

    The second struct, LinkedList contains two pointers. "Head" will point to the first node in the list, and "Tail" will point to the last node in the list. If there is only one node in the list, the both Head and Tail will point to the same node.
    What I need to do if I want to add node in end of list

    Code:
     #include<stdio.h>
    #include<stdlib.h>
    
    struct Node
    {
        int Value;
        struct Node *Next;
    };
    
    
    struct LinkedList
    {
        struct Node *Head;
        struct Node *Tail;
    };
    
    
    void appendNode(struct LinkedList *List, int value)
    {
        
        // Dynamically allocate memory using malloc() 
        List = malloc(sizeof(struct Node)); 
      
        // Check if the memory has been successfully 
        if (List == NULL) { 
            printf("Memory not allocated.\n"); 
            exit(0); 
        } 
        else 
        {  
           // Memory has been successfully allocated 
            printf("Memory successfully allocated using malloc.\n"); 
        }
      
    }
    
    
    int main(void)
    {
        struct LinkedList List = {NULL, NULL};
        appendNode(&List, 1);
    
    
        return 0;
    }

  7. #7
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    Quote Originally Posted by Djsarkar View Post
    What I need to do if I want to add node in end of list
    First of all, I think you need to look for a book on algorithms and data structures, or a good online tutorial on how to create and use linked lists. Please stay away from Geekforgeeks, as I have found their tutorials to be often flawed. (Unfortunately, many online tutorials are very limited.)

    You really need at least two functions, one to create a node and assign the data, and a second to append the node, passing pointers to the list, and the new node. You are trying to do too much with the one function, appendNode().

    And, I would recommend at least two functions to add a node to the list. One to add a node to the Head, and a second one to add the node to the Tail. Even a third could be written to insert the node into the middle of the list. Plus you need a a couple of function to remove one node, or all the nodes, calling free().

    Well written single linked lists, double linked lists, and other data structures, are not simple. A lot of thought and planning using pencil and paper are recommended before attempting to code them.
    Last edited by rstanley; 10-02-2021 at 11:30 AM.

  8. #8
    Registered User
    Join Date
    Oct 2019
    Posts
    46
    Quote Originally Posted by rstanley View Post

    ... Even a third could be written to insert the node into the middle of the list....
    To me it sounds much better if put like this :-> To insert a node at a certain index in the list. That way you accomplish the overall functionality of being able to insert anywhere on the list.

  9. #9
    Registered User
    Join Date
    Jul 2020
    Posts
    28
    Quote Originally Posted by rstanley View Post
    Please stay away from Geekforgeeks, as I have found their tutorials to be often flawed. (Unfortunately, many online tutorials are very limited.)
    The sample code I posted is idea of @laserlight

    Quote Originally Posted by rstanley View Post
    Well written single linked lists, double linked lists, and other data structures, are not simple. A lot of thought and planning using pencil and paper are recommended before attempting to code them.
    The head always points to the "start" and the tail always points to the "end".
    Attached Images Attached Images linked list code example-linked-list-jpg 

  10. #10
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    Quote Originally Posted by ghoul View Post
    To me it sounds much better if put like this :-> To insert a node at a certain index in the list. That way you accomplish the overall functionality of being able to insert anywhere on the list.
    Although I didn't specify it, an insertNode() function, implies the need for a searchNode() function with one or two node pointers to search for where in the list to insert the new node. Your term, "index" is better used when discussing arrays.

    IMHO, a thorough Single Linked List system would need at least:
    addHead() to add a node to the start of the list
    addTail() to add a node to the end of the list (Append)
    insertNode() Use searchNode() to locate where to insert a new node
    searchNode() Used by insertNode()
    deleteNode() Delete one node in the list
    deleteList() to call deleteNode() for each node
    printList() Print the data and possibly the address of all the nodes in the list
    ...

    You need to learn all the details of creating and using a Single Linked List, before attempting to convert it to a Double Linked List, before going even further.
    I am not trying to discourage you but trying to show how complex it can get very fast.

    Again, a good book on Algorithms and Data Structures is HIGHLY recommended!!!

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,360
    Quote Originally Posted by rstanley
    The example code you showed is really a mix of a "Single" linked list, and a "Double" linked list.
    No, it isn't, not at all. I demonstrated bundling the head and tail in a single structure as an abstraction of a singly linked list that also keeps track of its tail, since Djsarkar was originally keeping them separate. It has nothing to do with doubly linked lists.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    Quote Originally Posted by laserlight View Post
    No, it isn't, not at all. I demonstrated bundling the head and tail in a single structure as an abstraction of a singly linked list that also keeps track of its tail, since Djsarkar was originally keeping them separate. It has nothing to do with doubly linked lists.
    The examples of a simple single linked list I have dealt with in the past have only used Head. I have always associated Head and Tail with a double linked list. That's why I said it.

  13. #13
    Registered User
    Join Date
    Jul 2020
    Posts
    28
    Quote Originally Posted by laserlight View Post
    No, it isn't, not at all. I demonstrated bundling the head and tail in a single structure as an abstraction of a singly linked list that also keeps track of its tail, since Djsarkar was originally keeping them separate. It has nothing to do with doubly linked lists.
    I have expended code bit in post #6 and shown behavioral picture diagram for list in post #9. Now I need your help in appendNodefunction. I don't understand what should be inside the function

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,800
    Look at your picture in post #9

    Code:
    if ( List->Head == NULL ) {
      // update head and tail to point to the node you created
    } else {
      // add the node to where tail points, and adjust tail.
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  15. #15
    Registered User
    Join Date
    Jul 2020
    Posts
    28
    Quote Originally Posted by Salem View Post
    Look at your picture in post #9

    Code:
    if ( List->Head == NULL ) {
      // update head and tail to point to the node you created
    } else {
      // add the node to where tail points, and adjust tail.
    }
    In beginning Both Head and Tail point to next node in list. How to write code for this in function

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help With Linked List Code
    By TehQii in forum C Programming
    Replies: 4
    Last Post: 11-29-2016, 10:25 PM
  2. I need help with my code [linked list]
    By Pipo1990 in forum C Programming
    Replies: 5
    Last Post: 05-23-2015, 05:49 AM
  3. I have a problem in linked list code
    By QuantaPhysics in forum C Programming
    Replies: 2
    Last Post: 05-25-2014, 06:34 PM
  4. Linked list - why this bit of code?
    By chris1985 in forum C Programming
    Replies: 2
    Last Post: 10-04-2005, 06:17 AM
  5. Linked List Working Code
    By Linette in forum C++ Programming
    Replies: 9
    Last Post: 01-24-2002, 12:00 PM

Tags for this Thread