Data Structures and Algorithms_Linked List.1

Linked Lists

Basic explanation of Linked List along with C code creating it.

This writer dived deep into the ocean of Arrays (Don’t know what I am talking about? Click here!)

Now let’s climb the peaks of linked lists.

What are Linked List?

It is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. Each node is divided into two parts — the first part contains information of the element, the second part, the linked part contains the address of the next node in the list.

Linked list representation

The START or HEAD node consists of the address of the very first node in the list. We need only this node to traverse through the entire list.

Looks simple enough doesn’t it? Linked list is basically like train buggeys, can be added and removed easily without having to shift EVERY single buggey. Only the ones linked to the ones to be deleted or near the area to be added need to change their linkage.

Only issue is unlike arrays, C doesnt have built in linked lists to call and store only info. We will need to create them , this is where struct node kicks in.( The code for creating linked lists is present in the end of this blog)

Now, one of the basic operations we can do to any data structure is TRAVERSE it 🙌.

Algorithm

1. Assign PTR (pointer) = START
2. Repeat steps 3 and 4 while PTR != NULL
3. PROCESS(INFO(PTR))
4. PTR = LINK(PTR).

Below in the C code we have printed the info in place of PROCESS it.

// Creating and Traversing a Linked List
#include <stdio.h>
#include <stdlib.h>

struct node 
{
    int info;
    struct node *link;
};
int main() {
    int i,n , new;
    struct node *ptr, *q, *head;
    q = (struct node *) malloc(sizeof(struct node)); // creating head node.
    q -> info = 0;
    q -> link = NULL;
    head = q;
    ptr = head;
    
    for (i = 1; i<10; i++) // making other nodes 
    {
        q = (struct node *) malloc(sizeof(struct node));
    q -> info = i;
    q -> link = NULL;
    
    ptr -> link = q; // Link the nodes
    ptr = q; // p jumps to current node 
    }
    ptr = head;
    while (ptr != 0)
    { 
        printf("%d -> ", ptr -> info);
        ptr = ptr -> link;
        
    }
    printf("end");
    return 0;
}