Thread: single linked list with head and tail pointers

  1. #16
    Registered User
    Join Date
    Feb 2022
    Posts
    73
    I am trying to convert step's into code. I am specily stuck with function

    Code:
    #include<stdio.h>
    #include<stdint.h>
    #include<stdlib.h>
    
    
    struct node 
    {
        int data;
        struct node * next;
    };
    
    
    
    
     struct node *add (struct node *head, struct node * tail, int value  )
     {
    	struct node * current = malloc(sizeof(*current));
         
          if ( current != NULL )
          {
                current -> data = value;
                current -> next = tail;
                
                if( head == NULL )
                {
                    head = current ;     
                }
                
                else 
                    
                {
                      tail = current ;
                            
                }
          }
    	  
    	  return current;
    
    
     }
    int main ()
    { 
       struct node * head;
       struct node * tail;
       struct node * temp;
       
       temp = add ( head, tail, 3  );
      
       return 0;
    }

  2. #17
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,156
    From your post 8

    Code:
    #include<stdio.h>
     
    #include<stdint.h>
    #include<stdlib.h>
     
    struct node 
    {
        int data;
        struct node * next;
    };
     
     
    int main ()
    { 
       struct node * head = NULL;
       struct node * tail = NULL;
       
       return 0;
    }
    What you should do now is
    Code:
    #include<stdio.h>
    #include<stdlib.h>
     
    struct node 
    {
        int data;
        struct node * next;
    };
    
    struct list {
       struct node *head;
       struct node *tail;
    };
     
    int main ()
    { 
       struct list mylist = { NULL, NULL }; // an empty list
       return 0;
    }
    Now add can be
    Code:
    void add ( struct list *list, int data ) {
      // do things with list->head and/or list->tail
    }
    
    int main ()
    { 
       struct list mylist = { NULL, NULL }; // an empty list
       add(&mylist, 42);
       return 0;
    }
    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.

  3. #18
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    957
    Quote Originally Posted by Dadu@ View Post
    As I said I am trying to make function. That's not the complete function because I am stuck there. I am looking help to undestand what it takes and what it gives when it execute
    Dadu: I ask that you re-read my earlier post, and please follow my recommendations. You need a more thorough understanding of the basics of the C Language before going further with linked lists.

  4. #19
    Registered User
    Join Date
    Feb 2019
    Posts
    967
    Why the last node must point to a NULL node? Why the list cannot have a first 'void' node? Why to add a node you need to allocate inside the function? Here's a simplier implementation (see slist_add_next and slist_delete_next and slist_is_empty functions).

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    // This implementation uses only a head sentinel node (not a a tail sentinel
    // which, if used, would avoid deletion special case). In this implementation
    // the last node points to itself.
    
    struct slist_head { struct slist_head *next; };
    
    // Macro: initializes an empty list:
    //
    //  struct slist_head = SLIST_INIT( list );
    //
    #define SLIST_INIT( lst_ ) \
      { (lst_).next = &(lst_) }
    
    // Add an element after specified node.
    static inline void slist_add_next ( struct slist_head *node, struct slist_head *elem )
    {
      // ONE special case when list is empty.
      elem->next = ( node == node->next ) ? elem : node->next;
      node->next = elem;
    }
    
    // Deletes the next node.
    static inline void slist_del_next ( struct slist_head *node )
    {
      struct slist_head *next;
    
      next = node->next;
      // Special case for last node to delete...
      node->next = ( next == next->next ) ? node : next->next;
    }
    
    // Returns true if we have an empty list.
    static inline int slist_is_empty( struct slist_head *head )
    { return head == head->next; }
    
    // Exactyly the same as above, but different pointer.
    #define slist_is_last_node( node__ ) slist_is_empty( node__ )
    
    // Test
    int main ( void )
    {
      // Structure of "our" node (polimorphism!).
      struct anode
      {
        struct list_head *next;   // need to be the first element!
        float x, y, z;
      };
    
      // Empty list.
      struct slist_head list = SLIST_INIT ( list );
    
      struct slist_head *i;     // iterators.
      struct slist_head *tail;  // 'tail' node.
      struct anode *node;       // Points to a new node.
    
      // Add 3 nodes.
      // NOTE: Allocation isn't made by list functions!
      node = malloc ( sizeof * node );
      // here should check for allocation error.
      node->x = 1.0f;
      node->y = 2.0f;
      node->z = 3.0f;
      tail = ( struct slist_head *) node;    // Store the newly created node.
      slist_add_next ( &list, tail );
    
      node = malloc ( sizeof * node );
      // here should check for allocation error.
      node->x = 4.0f;
      node->y = 5.0f;
      node->z = 6.0f;
      // Add after the 'tail' node.
      slist_add_next ( tail, ( struct slist_head * ) node );
      tail = ( struct slist_head * ) node;  // Store the newly created node.
    
      node = malloc ( sizeof * node );
      // here should check for allocation error.
      node->x = 7.0f;
      node->y = 8.0f;
      node->z = 9.0f;
      // Add after the 'tail' node.
      slist_add_next ( tail, ( struct slist_head * ) node );
      // Don't need to save the newly created node here (in this example).
    
      // Show all nodes.
      i = &list;          // initialy points to head.
      while ( ! slist_is_last_node( i ) )
      {
        struct anode *p;
    
        i = i->next;
    
        p = ( struct anode * ) i;
        printf ( "(x,y,z) = (%f,%f,%f)\n",
                 p->x, p->y, p->z );
      }
    
      // Free all nodes.
      while ( ! slist_is_empty( &list ) )
      {
        i = list.next;
        slist_del_next( &list );
        free( i );
      }
    }

  5. #20
    Registered User
    Join Date
    Sep 2020
    Posts
    340
    I'm more of a traditionalist, and prefer an interface something like this, if you really need add and delete at tthe head, middle, and tail of a list.

    That is unless you have special performance requirements, where you really don't want to be calling "swiss army knife" functions.

    Code:
    struct anode
    {
      struct anode *next;
      float x, y, z;
    };
    
    
    struct anode *add_node_after(struct anode **head, struct anode **tail, struct anode *after, float x, float y , float z); // Use NULL for after to add at the head of the list
    int                 del_node(struct anode **head, struct anode **tail, struct anode *node_to_free);
    
    
    int main ( void )
    {
      // Head and tail pointers
      struct anode *head = NULL, *tail = NULL;
    
      // If you want, test the return value to check that a valid node was added. 
      add_node_after(&head, &tail, NULL,  1.0,  2.0,  3.0); // Add to the empty list
      add_node_after(&head, &tail, head,  4.0,  5.0,  6.0); // Add after head (and it is the new tail)
      add_node_after(&head, &tail, head,  7.0,  8.0,  9.0); // Add between head and tail
      add_node_after(&head, &tail, tail, 10.0, 11.0, 12.0); // Add at the very end
      add_node_after(&head, &tail, NULL, 13.0, 14.0, 15.0); // Add at the very start
    
      // Walk the list
      for(struct anode *node = head; node != NULL; node = node->next) {
        printf ( "(x,y,z) = (%f,%f,%f)\n", node->x, node->y, node->z );
      }
    
      // Delete all the nodes
      while (head != NULL)
        del_node(&head, &tail, head);
    
      return 0
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Declaring head and tail for doubly linked list
    By eagerissac in forum C Programming
    Replies: 1
    Last Post: 11-08-2020, 01:52 PM
  2. Linked List - Add to Tail
    By Brandon Smith in forum C Programming
    Replies: 10
    Last Post: 04-10-2012, 09:55 AM
  3. "insert sort with head and tail pointers"
    By noway2 in forum C Programming
    Replies: 2
    Last Post: 10-24-2011, 10:18 PM
  4. Linked List - Add to Tail
    By beatbox32 in forum C Programming
    Replies: 9
    Last Post: 08-08-2011, 03:43 PM
  5. Another List Q - Seg fault on head-tail list
    By JimpsEd in forum C Programming
    Replies: 11
    Last Post: 05-10-2006, 12:53 AM

Tags for this Thread