Data Structure and algorithm using C: Linear Linked list -thebytewise

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. Thus can be stored in a non-contiguous memory location.

The visual representation of a Linked list is shown below:


Here one box represents one "Node", the data of the node is stored in the "Data" portion of the node, and "Next" will point to the address of the next node.

The head/header pointer is assigned to the first Node in the List, and the "Next" portion of the last node will point to NULL value.


//declaration of a node

struct node{
int data;
struct node *next;
}*header;

Now as the node structure is declared it's time to create a List and assign memory to it


//creation of a List

void createList(int n){
struct node *newNode, *temp; //temp is used to move to the next node
int data, i;

newNode = (struct node *) malloc(sizeof(struct node)); /* declaring a node and allocating a new memory*/

if(newNode == NULL){
    printf("ERROR: Memory Overflow"); /*If newNode is NULL that will mean the memory creation was unsuccessful*/
}

//Initializing of the first Node in the List
else{
    printf("Enter element 1: ");
    scanf("%d", &data);
    newNode->data = data;
    newNode->next = NULL;
    header = newNode;
    temp = newNode;
//----------------------------

//Initialization of the subsequent Nodes in the list

    for(i=2;i<=n;++i){

            newNode = (struct node *) malloc(sizeof(struct node));

       if(newNode == NULL){
        printf("ERROR: Memory Overflow");
       }
       else{
        printf("Enter element %d: ",i);
        scanf("%d",&data);

        newNode->data = data;
        newNode->next = NULL;
        temp->next = newNode;
        temp = temp->next;
       }
    }
}
}

Here, as the header always has to point to the first Node, a temporary variable *temp is created to point to the address of the next node in the List.

This temporary variable can also be used to traverse the list.

//traversing the list

void traverseList(int n){
struct node *temp;
int i;

if(header == NULL){
    printf("ERROR: Memory Underflow");
}

else{
    temp = header;
    for(i=0;i<n;++i){
        printf("\ndata %d= %d",i+1, temp->data);
        temp = temp->next;
    }
}
}


FULL PROGRAM


#include<stdio.h>
#include<stdlib.h>

void createList();
void traverseList();

struct node{
int data;
struct node *next;
}*header;


int main(){
    int n;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    createList(n);
    printf("\nData in the list:\n");
    traverseList(n);
    return 0;
}

void createList(int n){
struct node *newNode, *temp;
int data, i;

newNode = (struct node *) malloc(sizeof(struct node));

if(newNode == NULL){
    printf("ERROR: Memory Overflow");
}
else{
    printf("Enter element 1: ");
    scanf("%d", &data);
    newNode->data = data;
    newNode->next = NULL;
    header = newNode;
    temp = newNode;

    for(i=2;i<=n;++i){

            newNode = (struct node *) malloc(sizeof(struct node));

       if(newNode == NULL){
        printf("ERROR: Memory Overflow");
       }
       else{
        printf("Enter element %d: ",i);
        scanf("%d",&data);

        newNode->data = data;
        newNode->next = NULL;
        temp->next = newNode;
        temp = temp->next;
       }
    }
}
}

void traverseList(int n){
struct node *temp;
int i;

if(header == NULL){
    printf("ERROR: Memory Underflow");
}

else{
    temp = header;
    for(i=0;i<n;++i){
        printf("\ndata %d= %d",i+1, temp->data);
        temp = temp->next;
    }
}
}

/* alternatively for traversing the list instead of the for loop a while loop can also be used as

while(temp!=NULL){
printf("\ndata %d= %d",i+1, temp->data);
        temp = temp->next;
}
*/



94 views
  • Facebook
  • Instagram

©2020 by thebytewise. All Rights Reserved