Linked Lists
Have you seen a train engine with multiple bogies? There is a link between each of these that keeps the whole train moving. There is huge amount of data that needs to be kept linked together as a set. To store such data in contiguous memory is not feasible (Example: in an array) and there needs to be a mechanism that can make the most optimal use of memory that is present. A linked list is one of the best ways to accomplish this. While there is no indexing like in an array, it is lot more easy to add and delete data elements. In this article, I would like to post some basic functions that are associated with these linked lists in C.
Basic stuff to know:
1. struct : It’s a declaration that allows users to store many variables of multiple datatypes together with a single name.
2. pointer: It is a variable that holds the memory address of another variable.
3. malloc: It is a function that allocates the requested memory and returns a pointer to it.
DECLARING A NEW NODE
struct node {
int data;
struct node* next;
};
“node” is a structure that holds a variable “data” in each element in the list and the link to the next “node” is stored in “next”.
ADDING A NEW NODE
struct node* newNode(int key)
{
struct node* temp = (struct node*) malloc(sizeof(struct node));
temp->data = key;
temp->next = NULL;
return temp;
}
The function with name “newNode” whenever called will create a new node with the “data” field of the node being assigned to the “key” and the “next” being pointed to NULL. The node is created by allocating memory using malloc function. Memory being allocated would be of the size of the struct. The malloc function here returns a pointer of the struct node type. The function returns a pointer to struct back to the calling function. The return type of this function is struct node* and the arguments include an int data type.
For example:
struct node* head = newNode(50);
head->next = newNode(20);
This will create a node with data = 50 and the first pointer of that list will be pointed by “head”. Once the node head is created, the head->next will represent the formation of a link to a new node that will contain data and a next pointer in it. “->” operator is used access the members of a structure (like data and next). newNode(20) will create a new node with data = 20. So now the list can be represented as:
(50) -> (20) -> NULL
PRINTING THE LINKED LIST
void printList(struct node* nodePrint)
{
while(nodePrint != NULL)
{
printf("%d -> ",nodePrint->data);
nodePrint = nodePrint->next;
}
printf("NULL\n");
}
When the function printList is called with its arguments as the pointer to the head of the list, it prints the linked list accordingly. Suppose there were 5 newNode function calls with data as 20, 50, 10, 15, 25 consecutively and the printList is called with the parameters passed to the function being the pointer pointing to the head node containing data=20, the following would be the output on the screen:
20 -> 50 -> 10 -> 15 -> 25 -> NULL
This is how the function is being implemented: The argument contains the pointer to the head of the linked list. The while loop is keeping a check on the pointer if it has a definite value or if it is NULL. If the pointer turns out to be NULL, the loop is exit. If not, the control enters the while loop. Here, the data element stored at the current nodePrint structure is printed. Now, the current nodePrint will be assigned the value of pointer pointed to the next element by accessing the “next” link of the current node. The loop continues until the current nodePrint becomes NULL. Once it becomes NULL, a print statement prints out “NULL” to represent the end of the linked list to be printed.
REVERSING THE LINKED LIST
void reverse(struct node** head)
{
struct node* prev = NULL;
struct node* curr = *head;
struct node* next;
while(curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
When a function “reverse” is called by passing a pointer to the pointer of the head node of a linked list as its parameters, it reverses the way the linked list is organized and turns it around into a reversed linked list. The reason a pointer to a pointer is being passed as an argument is to directly access the linked list and manipulate it so that the function does not have to return anything to the calling function and still get the job done of reversing the linked list. Whenever the control enters this function three nodes are created, “prev”, “curr” and “next”. These three nodes keep track of the previous node, the current node and the next node of the existing linked list. Initially the previous node is NULL which is the end of the new reversed linked list. The current node that is being manipulated initially would be the head node of the actual linked list. The next node will hold the data item that is to be considered next while reversing the linked list. A while loop iterates until the end of the present linked list. What happens inside the while loop is that initially the “next” takes the value of the next element of the present linked list. The next element in the current list becomes the previous node that holds the reversed linked list. Now, the previous node will take the value of the current node to keep track of the reversed list and the current list will have one less node. This process is repeated until the end of the list in the present list and when the end is reached, the head of the reversed linked list will be assigned as the last node of the present node.
For example, suppose the linked list is represented as:
50 -> 20 -> 15 -> 25 -> NULL
Step A: When the function is called, the pointer to the pointer pointing to the node with data=20 is sent as the argument to the function call.
Step B: A node pointer prev is initialized to NULL, curr is initialized to the pointer of data=20 and next is uninitialized.
Step C: An iteration begins with the condition that curr is not NULL. So, every time curr is not NULL, the next step (Step D) will repeat. If not the control goes to the last step (Step E).
Step D: The four main sub-steps that occur in this step are as follows and pictorially represented later:
1. next = curr->next
2. curr->next = prev
3. prev = curr
4. curr = next
Step E: Make the last element added in the reversed linked list to be the head pointer.
These steps will make it clear why the function is working with pointer to pointer and not just the head pointer to be sent to the function for reference.
