Thread: single linked list with head and tail pointers

  1. #1
    Registered User
    Join Date
    Feb 2022
    Posts
    73

    single linked list with head and tail pointers

    I am trying to understand how the single linked list will design if we are using head and tail pointers in list. First node would be "head" of list and last node be "tail" of list.

    In a case where no elements in list so head and tail should be NULL pointer.

    What happens in case when first node created ?

    Does the head pointer point to the first node of list ? I think yes

    Does the tail pointer point to the first node of list ? I think yes

    Does the first node point to the next node of list ? I think yes

  2. #2
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    **snip

    Actually I'm a little confused.. Could you explain your design more?

    My understanding of a single linked list is as follows:

    The head is just the first node in the linked list.
    The tail is just the nodes that follow the head.

    if we have a linked list with 5 nodes:

    node1->node2->node3->node4->node5

    In this case node1 would be the head and node2->node3->node4->node5 would be the tail.
    Last edited by G4143; 03-04-2022 at 11:16 PM.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,410
    Quote Originally Posted by Dadu@
    Does the head pointer point to the first node of list ? I think yes
    Yes.

    Quote Originally Posted by Dadu@
    Does the tail pointer point to the first node of list ? I think yes
    Yes.

    Quote Originally Posted by Dadu@
    Does the first node point to the next node of list ? I think yes
    I think you're talking about the next pointer of the first node. Since the first node was only just created, there is no second node, hence the next pointer of the first node must be a null pointer.

    Quote Originally Posted by G4143
    The head is just the first node in the linked list.
    The tail is just the nodes that follow the head.
    That's the Lisp car vs cdr concept, useful for recursive thinking. But in this context, the tail refers to the last element of the linked list.
    Last edited by laserlight; 03-05-2022 at 12:05 AM.
    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

  4. #4
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    If you are creating a 'simple' linked list then the structure for the node should be straight forward. The node structure should have a member for the data and a member for the next node. That's it.
    Code:
    typedef struct node* LL_NODE_PTR;
    
    typedef struct node {
      int data;
      LL_NODE_PTR next;
    } LL_NODE;

  5. #5
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    Quote Originally Posted by laserlight View Post
    That's the Lisp car vs cdr concept, useful for recursive thinking. But in this context, the tail refers to the last element of the linked list.
    Could you post a link to the context the OP and you are referring to?

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,410
    Quote Originally Posted by G4143
    Could you post a link to the context the OP and you are referring to?
    The OP wrote it right there in post #1:
    Quote Originally Posted by Dadu@
    First node would be "head" of list and last node be "tail" of list.
    This is typically used when you want to have a constant time append operation for the linked list (in addition to constant time prepend).
    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

  7. #7
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    Quote Originally Posted by laserlight View Post
    The OP wrote it right there in post #1:

    This is typically used when you want to have a constant time append operation for the linked list (in addition to constant time prepend).
    OK! I see what the OP is after now.

  8. #8
    Registered User
    Join Date
    Feb 2022
    Posts
    73
    Quote Originally Posted by laserlight View Post
    Yes.

    I think you're talking about the next pointer of the first node. Since the first node was only just created, there is no second node, hence the next pointer of the first node must be a null pointer.

    Yes. I was talking about the next pointer of the first node

    What happens in case when second node added in list

    1. Does the head pointer point to the first node of list ? I think yes
    2. Does the tail pointer point to the second node of list ? I think yes
    3. Does next pointer of the first node point to the next node of list ? I think yes
    4. I think pointer of second node point to NULL because this is last node in list.


    if everything looks correct, I will try to write function for complete process

    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;
    }
    Last edited by Dadu@; 03-05-2022 at 02:28 AM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,410
    Quote Originally Posted by Dadu@
    Does the head pointer point to the first node of list ? I think yes
    Yes.

    Quote Originally Posted by Dadu@
    Does the tail pointer point to the second node of list ? I think yes
    Yes

    Quote Originally Posted by Dadu@
    Does next pointer of the first node point to the next node of list ? I think yes
    Yes, but that's a self-referential tautology and hence doesn't really mean anything useful. What you probably meant to say is that you think that the next pointer of the first node points to the second node of the list, and indeed that should happen.

    Quote Originally Posted by Dadu@
    I think pointer of second node point to NULL because this is last node in list.
    Yes.
    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

  10. #10
    Registered User
    Join Date
    Feb 2022
    Posts
    73
    Quote Originally Posted by laserlight View Post
    Yes.

    Yes, but that's a self-referential tautology and hence doesn't really mean anything useful. What you probably meant to say is that you think that the next pointer of the first node points to the second node of the list, and indeed that should happen.
    I am stuck in function

    Code:
    #include<stdio.h>
    #include<stdint.h>
    #include<stdlib.h>
    
    struct node 
    {
        int data;
        struct node * next;
    };
    
    
     // Type Function (Type) 
     struct node * current = malloc(sizeof(*current);
         
          if ( current != NULL )
          {
                current -> data = value;
                current -> next = ;
                
                if( head == NULL )
                {
                    head = current ;     
                }
                
                else 
                    
                {
                      tail = current ;
                            
                }
          }
    
    
    int main ()
    { 
       struct node * head;
       struct node * tail;
      
       return 0;
    }
    Last edited by Dadu@; 03-05-2022 at 03:24 AM.

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,156
    > I am stuck in function
    That's because it isn't a function.

    Review your other threads, such as
    How to link next node in linked list
    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.

  12. #12
    Registered User
    Join Date
    Feb 2022
    Posts
    73
    Quote Originally Posted by Salem View Post
    > I am stuck in function
    That's because it isn't a function.

    Review your other threads, such as
    How to link next node in linked list
    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
    Last edited by Dadu@; 03-05-2022 at 03:31 AM.

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,156
    Well it's not going anywhere until you do make it a function.

    Just posting random lines out of context and says "it doesn't work" tells us nothing.
    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.

  14. #14
    Registered User
    Join Date
    Feb 2022
    Posts
    73
    Quote Originally Posted by Salem View Post
    Well it's not going anywhere until you do make it a function.

    Just posting random lines out of context and says "it doesn't work" tells us nothing.
    It's clear that I want to make function. I guess function will take three arguments. I don't have any idea if function needs to return value or it don't need to return anything

  15. #15
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    At the very least you should post a function signature and what you expect that function to do.

    i.e.

    Code:
    struct linked_list create_empty_list(void) {
    /*This function initializes and returns a struct linked_list*/
    }

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