Thread: 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

Originally Posted by ghoul

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 ?

Originally Posted by Djsarkar

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.

Originally Posted by rstanley

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;
}

Originally Posted by rstanley

... 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.

Originally Posted by rstanley

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

Originally Posted by rstanley

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".

Originally Posted by ghoul

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!!!

Originally Posted by laserlight

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.

Originally Posted by laserlight

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

Originally Posted by Salem

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