I find linked list quit difficult in c programming I have read many tutorials, looked many program of linked list but still I am not getting clear understanding. I think I don’t understand basic concept of singly linked list.

So I’ve drawn singly linked list diagram on paper that looks right to me.


I am trying to make picture that show empty list, that shows what happens when first node add to the list, when second node to list, when third node add to list, when fourth node add to list, and when fifth node add to list with pointer.

 

Do you understand pointers?

Bob

 

Do you understand pointers?

Bob

Yes I understand Pointer, Structure, Pointer to Structure and Dynamic Memory.

I'm having trouble with the function where the node is added to the list at the end.

Can you tell how do you draw the diagram for the following.

A struct pointer head is declared in the main function which is initially null.

We have a function AddNode that creates a node in list

The new node should always be added to the end of the list. When function AddNode called from main

The last node in the list should always point to a null value.

But it's too early for me to write a program. That's why I want to draw picture of discription

 

Do you really mean that you cannot draw it, or that you don’t know how to code it?

If you can’t draw it that means you can draw a list with five elements, but not one with six elements. How can that be?

Bob

 

A list with no elements has a head pointer that contains a NULL
In the absence of any other information you have to "walk" the list from the head to the tail to add a new element. You change the pointer in the tail element to point to the new element and you make the new element the tail by setting its pointer to NULL.

Some singly linked list headers will also contain a pointer to the tail in which case it is not necessary to "walk" the list to find the tail.

 

Do you really mean that you cannot draw it, or that you don’t know how to code it?

If you can’t draw it that means you can draw a list with five elements, but not one with six elements. How can that be?

Bob

I've written code for list but I don't think its good way to do it

#include<stdio.h>
#include<stdlib.h>
    
typedef struct Node 
{
  int data;
  struct Node *next;
}list;
  int main()
{
  list *head = NULL;
  list *second = NULL;
  list *third = NULL;
  list *fourth = NULL;
  list *fifth = NULL;
  list *temp = NULL;

  
  head  = malloc(sizeof(*head)); 
  second = malloc(sizeof(*second));
  third  = malloc(sizeof(*third));
  fourth  = malloc(sizeof(*fourth));
  fifth  = malloc(sizeof(*fifth));
    
  head->data = 3;
  head->next = second;
    
  second->data = 5;
  second->next = third;   
    
  third->data = 9;
  third->next = fourth;
 
  fourth->data = 12;
  fourth->next = fifth;
 
  fifth ->data = 20;
  fifth->next = NULL;
  
   temp = head;
  while (temp != NULL)
  {
     printf(" %d ", temp->data);
     temp = temp->next;
  }
      
  return 0;
}

Output from program
3 5 9 12 20

 

A list with no elements has a head pointer that contains a NULL
In the absence of any other information you have to "walk" the list from the head to the tail to add a new element. You change the pointer in the tail element to point to the new element and you make the new element the tail by setting its pointer to NULL.

Some singly linked list headers will also contain a pointer to the tail in which case it is not necessary to "walk" the list to find the tail.

I need to write function that add the node at end of list
dummy code

#include<stdio.h>
#include<stdlib.h>
    
typedef struct Node 
{
  int data;
  struct Node *next;
}list;

int main()
{
  list *head = NULL;
        
  return 0;
}

That was the reason I was first trying to draw it on paper to understand how function will implement for list

 

I need to write function that add the node at end of list
dummy code

#include<stdio.h>
#include<stdlib.h>
   
typedef struct Node
{
  int data;
  struct Node *next;
}list;

int main()
{
  list *head = NULL;
       
  return 0;
}

That was the reason I was first trying to draw it on paper to understand how function will implement for list

So can you translate the verbal description that I gave you into code?

 

So can you translate the verbal description that I gave you into code?

Head Pointer point to null value when list is empty. I don't know more than it.

Here are some points that should be done in the function

• We need a function AddNode that creates a node in list
• The new node should always be added to the end of the list.
• The last node in the list should always point to a null value.

I am neither able to write the code nor implement the diagram for this function

 

Head Pointer point to null value when list is empty. I don't know more than it.

Here are some points that should be done in the function

• We need a function AddNode that creates a node in list
• The new node should always be added to the end of the list.
• The last node in the list should always point to a null value.

I am neither able to write the code nor implement the diagram for this function

I'm sorry to say that my coding skills have atrophied in retirement and I don't have any compiler to check prototype solutions, so I'm not going to be much help to you. I should point out that the "head" pointer is a standalone element. It is a pointer to a list, but it is not a list, because a list has two elements and the head pointer has only one. Before messing with malloc() you might want to try using a statically allocated array of structures of type list. That will be easier to debug when you get to that stage.

 

I find linked list quit difficult in c programming I have read many tutorials, looked many program of linked list but still I am not getting clear understanding. I think I don’t understand basic concept of singly linked list.

So I’ve drawn singly linked list diagram on paper that looks right to me.

View attachment 254129
I am trying to make picture that show empty list, that shows what happens when first node add to the list, when second node to list, when third node add to list, when fourth node add to list, and when fifth node add to list with pointer.

In general (and in functional languages certainly) items are added to a singly-linked list only at the head - period. Another way to grasp this is that lists are - ideally - immutable, that is once some code has a pointer to some list, the list never ever changes.

Above, if some code has a pointer to element 3034, then that pointer and the elements that follow it, never ever change as items are added to the list.

Now immutability is of course not forced upon us but is highly desirable for a host of reason (for example the list might be accessed concurrently by multiple threads), so that's my opinion on this.

So having said that adding elements to the list in your diagram is simple:

1. Create new element.
2. Set elements next_ptr to the valued pointed to by the head_ptr.
3. Set head_ptr to point to this new element.

Done.

Of course if you don't want immutability then there are algorithms for inserting nodes more arbitrarily, in this situation there are just three cases to consider:

1. Add element to head of list
2. Add element to tail of list
3. Add element into middle of list (that is after being added there is an element before and after).

All you need to consider when designing this is a two element list and the new node to add, if you code for each of the three cases the solution will work for lists of any length. Of course you need a rule for deciding at what point to insert a new node (that is how are items ordered), that rule likely depends on some data inside the node, its good practice to extract that rule so that it is not part of the insert logic, that is make the list insert independent of the rule so that the rule can be changed without any impact on the list insert, the insert code is then reusable for any kind of list with any rule.

 

In general (and in functional languages certainly) items are added to a singly-linked list only at the head - period. Another way to grasp this is that lists are - ideally - immutable, that is once some code has a pointer to some list, the list never ever changes.

In general, when we make a list on paper, we add one by one item. For example, if I want to list the players of a cricket team, I will start with 1, 2, and the last player will be number 11. It is observed that the new number in the list is added last. That's why I want to create a list in which I add a new node to the end of the list.

I have no idea how to write a function for the code posted in #7 that add the new node at end of list. I am asking for help to write this function.

So having said that adding elements to the list in your diagram is simple:

1. Create new element.
2. Set elements next_ptr to the valued pointed to by the head_ptr.
3. Set head_ptr to point to this new element.

Done.

I'm sure the diagram shows that the new node is added to the end of the list. No node has ever been added before the head node

 

In general, when we make a list on paper, we add one by one item. For example, if I want to list the players of a cricket team, I will start with 1, 2, and the last player will be number 11. It is observed that the new number in the list is added last. That's why I want to create a list in which I add a new node to the end of the list.

I have no idea how to write a function for the code posted in #7 that add the new node at end of list. I am asking for help to write this function.



I'm sure the diagram shows that the new node is added to the end of the list. No node has ever been added before the head node

In which case this can be achieved by adjusting the "head" structure to also point to the tail of the list. If it is the tail to which items must be appended then having a pointer to that in the "head" structure is the sensible thing to do.

 

In which case this can be achieved by adjusting the "head" structure to also point to the tail of the list. If it is the tail to which items must be appended then having a pointer to that in the "head" structure is the sensible thing to do.

We already discussed this earlier in the thread. In the case that you have a "head' pointer ONLY, you need to "walk" the list to find the "tail". If you do it often enough then having a pointer to the "tail" makes sense. If you do it rarely, or never, then not so much. Like everything else in the software arena there are compromises and tradeoffs.

 

We already discussed this earlier in the thread. In the case that you have a "head' pointer ONLY, you need to "walk" the list to find the "tail". If you do it often enough then having a pointer to the "tail" makes sense. If you do it rarely, or never, then not so much. Like everything else in the software arena there are compromises and tradeoffs.

Sure, if the list at some point has a million items though then it is a serious CPU cost to find the tail. My point is if the problem is to append things to the tail of the list and we only have a pointer to the head then the problem is that design, it is inadequate and a poor solution.

So I guess the next question is what exactly is driving this requirement? the requirement to not have a pointer to the tail yet at the same time the requirement to be able to append things to that tail, only Mukesh can answer this I guess.

 

Here are some suggestion too, I've designed very sophisticated systems in C in fact a compiler too which entails huge lists and trees, here's a tip for how to define and declare basic structures:

typedef void               * Any_ptr;
typedef struct list_struct * List_ptr;
typedef struct node_struct * Node_ptr;

typedef struct list_struct
{
   Node_ptr   head_ptr;
   Node_ptr   tail_ptr;
} List;

typedef struct node_struct
{
   Node_ptr   prev_ptr;
   Node_ptr   next_ptr;
   Any_ptr    data_ptr;
   int        data_len;  // storing length of data here allows us to be able to free up the data memory automatically if we ever need that.
} Node;

/* we are now able to simply declare items as "Node" or "List" as well as "Node_ptr" and so on */

List_ptr CreateList()
{
   List_ptr ptr = malloc(sizeof(List));

   ptr->head_ptr = NULL:
   ptr->tail_ptr = NULL;

   return ptr;
}

Node_ptr CreateNodeFromData(Any_ptr node_data, int node_data_length)
{

   Node_ptr ptr = malloc(sizeof(Node));

   ptr->prev_ptr = NULL;
   ptr->next_ptr = NULL;
   ptr->data_ptr = node_data;
   ptr->data_len = node_data_len;

   return ptr;
}

OK you can see that I define typedefs for both structures and pointers to those structures, this makes code much more readable and greatly reduces the need to declare stuff with * all the time.

You can see how creating a new empty list and creating a new element for the list, are coded.

In this basic design the list nodes do not contain data, but they do contain a pointer to the data. This make the design completely independent of the type of stuff you might want to put into the list.

The next step is to write functions like InsertAtHead() and InsertAtTail(), for example:

void InsertAtTail (List_ptr list_ptr, Node_ptr node_ptr)
{

   if (list_ptr->head_ptr == NULL && list_ptr->tail_ptr == NULL)  // The list is currently empty
      {
      list_ptr->head_ptr = node_ptr;
      list_ptr->tail_ptr = node_ptr;
      return;
      }
    
    node_ptr->prev_ptr = list_ptr->tail_ptr;
    list_ptr->tail_ptr = node_ptr;
  
    return;
}

void InsertAtHead (List_ptr list_ptr, Node_ptr node_ptr)
{

   if (list_ptr->head_ptr == NULL && list_ptr->tail_ptr == NULL)  // The list is currently empty
      {
      list_ptr->head_ptr = node_ptr;
      list_ptr->tail_ptr = node_ptr;
      return;
      }
    
    node_ptr->next_ptr = list_ptr->head_ptr;
    list_ptr->head_ptr = node_ptr;
  
    return;
}

 

Sure, if the list at some point has a million items though then it is a serious CPU cost to find the tail. My point is if the problem is to append things to the tail of the list and we only have a pointer to the head then the problem is that design, it is inadequate and a poor solution.

So I guess the next question is what exactly is driving this requirement? the requirement to not have a pointer to the tail yet at the same time the requirement to be able to append things to that tail, only Mukesh can answer this I guess.

I did state the conditions under which it would be reasonable.

 

Advice is being given for two pointers let's try to make list now

Now how new node will add at end of list

#include<stdio.h>
#include<stdlib.h>
    
typedef struct Node
{
  int data;
  struct Node *next;
}list;

void InsertAtNode ( list *head, list *tail, int value )
{
    list *new = NULL;
    new = malloc(sizeof(*new));
}

int main()
{
  list *head = NULL;
  list *tail = NULL;
  InsertAtNode ( head, tail, 10 );
 
  return 0;
}

 

Advice is being given for two pointers let's try to make list now

Now how new node will add at end of list

#include<stdio.h>
#include<stdlib.h>
   
typedef struct Node
{
  int data;
  struct Node *next;
}list;

void InsertAtNode ( list *head, list *tail, int value )
{
    list *new = NULL;
    new = malloc(sizeof(*new));
}

int main()
{
  list *head = NULL;
  list *tail = NULL;
  InsertAtNode ( head, tail, 10 );

  return 0;
}

May I ask, why are you seeking an answer to this question? are you building/designing something or might this some kind of college assignment you've been given?

 

May I ask, why are you seeking an answer to this question? are you building/designing something or might this some kind of college assignment you've been given?

This is not a school assignment. I am practicing advanced topic linked list in c language. I have already posted the code of a list without function. There are many codes on the internet but I can't understand them. My specific problem is that I'm having trouble writing the function.