top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

    Get Free Article Updates

Facebook Login
Site Registration

Circular Linklist Implementation in C (Singly)

+1 vote
303 views

What is Link List
W linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a link to the next node in the sequence.

enter image description here

Why Circular Link List
As you can see in the first image that the last->next is null but if last->next is pointing to the head node is called circular link list. The main advantage id that if you have access to any node then you can get access of any node.

Necessary Functions

struct node * create_node(int data)
void insert_at_begining(int info)
void insert_at_position(int info, int position)
void delete_at_begining()
void delete_at_position(int position)
void search(int key)
void update(int olddata, int newdata)
void traverse()
void rev_traverse(struct node *p)

Sample Code
C sample code someone can try C++ code...

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

/* We can have additional structure which can have head and last node is node pointer and 
   additionally can have length variable which contains the length of the link list */
struct node *head = NULL, *last = NULL;
int length = 0;


struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void insert_at_begining(int info)
{
    struct node *new;
    new = create_node(info);

    if (head == NULL && last == null)
    {   
        head = last = new;
        head->next = last->next = NULL;
    }
    else
    {
        new->next = head;
        head = new;
        last->next = head;
    }
}

void insert_at_position(int info, int position)
{
    struct node *new, *ptr, *prevnode;
    int len = 0, i;

    new = create_node(info);

    if (head == NULL)
    {
        if (position == 1)
        {
            head = last = new;
            head->next = last->next = NULL; 
        }
        else
            printf("\n empty linked list you cant insert at that particular position");
    }
    else
    {
        if (length < position)
            printf("\n node cant be inserted as position is exceeding the linkedlist length");

        else
        {
            for (ptr = head, i = 1; i <= length; i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (i == position-1)
                {
                    prevnode->next = new;
                    new->next = ptr;
                    break;
                }
            }
        }
    }
}

void delete_at_begining()
{
    struct node *y;

    if (head == NULL) 
        printf("\n List is empty");
    else
    {
        x = last;
        y = head;
        head = y->next;
        last->next = head;
        length--;
        free(y);
    }
}

void delete_at_position(int position)
{
    int count = 0, i;
    struct node *ptr, *temp, *prevnode;

    if (head == last && head == NULL)
        printf("\n empty linked list you cant delete");
    else
    {
        if (length < position)
            printf("\n node cant be deleted at position as it is exceeding the linkedlist length");

        else
        {
            for (ptr = head,i = 1; i <= length; i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (position == 1)
                {   
                    length--;
                    head = ptr;
                    last->next = head;
                    free(prevnode);
                    break;
                }
                else if (i == position - 1)
                {   
                    length--;
                    prevnode->next = ptr->next;
                    free(ptr);
                    break;
                }
            }
        }
    }
}

void search(int key)
{
    int count = 0, i, f = 0;
    struct node *ptr;

    if (head == NULL)
        printf("\nlist is empty no elemnets in list to search");
    else
    {
        for (ptr = head,i = 0; i < length; i++,ptr = ptr->next)
        {
            count++;
            if (ptr->data == key)
            {
                printf("\n the value is found at position at %d", count);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n the value is not found in linkedlist");
    }
}


void update(int olddata, int newdata)
{   
    int i, f = 0;
    struct node *ptr;

    if (head == NULL)
        printf("\n list is empty no elemnts for updation");
    else
    {   
        for (ptr = head, i = 0; i < length; ptr = ptr->next,i++)
        {   
            if (ptr->data == olddata)
            {   
                ptr->data = newdata;
                printf("value is updated to %d", ptr->data);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n no such old value to be get updated");
    }
}

void traverse()
{
    if (head == NULL)
        printf("\n List is empty");
    else
    {
        x = head;
        while (x->next !=  head)
        { 
            printf("%d->", x->data);
            x = x->next;
        }
        printf("%d", x->data);
    }
}

void rev_traverse(struct node *p)
{
    int i = 0;

    if (head == NULL)
    {
        printf("empty linked list");
    }
    else
    {
        if (p->next !=  head)
        {
            i = p->data;
            rev_traverse(p->next);
            printf(" %d", i);
        }
        if (p->next == head)
        {
            printf(" %d", p->data);
        }
    }
}
posted Aug 31, 2014 by Salil Agrawal

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button


Related Articles

What is Doubly Link List
In a doubly linked list, each node contains, two links one is called next which points to the next node and one is called prev which points to the previous node in the sequence.

Doubly Link List

Why Circular Doubly Link List
As you can see in the previous image that the head->prev is null and so the last->next but if head->prev is pointing to the last node and last->next is pointing to the head node is called doubly circular link list

Circular Doubly Link List

Necessary Function
However it is dependent on how you like to manage the link list but the following function would be useful addition which can make any Doubly Link List useful in most of the situations -

struct node* create_node(int info)
void add_node(int info)
void insert_at_first(int info)
void insert_at_last(int info)
void insert_at_position(int info, int position)
void sort_list()
void delete_node_position(int position)
void update(int olddata, int newdata)
void search(int key)
void display_from_begining()
void display_in_reverse()

Sample Code
Here is the sample code (only the functions) written in C, any taker for C++

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

/* We can have additional structure which can have head and last node is node pointer and 
   additionally can have length variable which contains the length of the link list */
struct node *head = NULL, *last = NULL;
int length = 0;

struct node* create_node(int info)
{
    struct node *new;
    length++;
    new = (struct node *)malloc(sizeof(struct node));
    new->data = info;
    new->next = NULL;
    new->prev = NULL;
    return new;
}

void add_node(int info)
{
    struct node *new;
    new = create_node(info);
    if (head == last && head == NULL)
    {
        head = last = new;
        head->next = last->next = NULL;
        head->prev = last->prev = NULL;
    }
    else
    {
        last->next = new;
        new->prev = last;
        last = new;
        last->next = head;
        head->prev = last;
    }
}

void insert_at_first(int info)
{
    struct node *new;
    new = create_node(info);
    if (head == last && head == NULL)
    {   
        head = last = new;
        head->next = last->next = NULL;
        head->prev = last->prev = NULL;
    }
    else
    {
        new->next = head;
        head->prev = new;
        head = new;
        head->prev = last;
        last->next = head;
    }
}

void insert_at_last(int info)
{
    struct node *new;
    new = create_node(info);
    if (head == last && head == NULL)
    {
        head = last = new;
        head->next = last->next = NULL; 
        head->prev = last->prev = NULL;
    }
    else
    {
        last->next = new;
        new->prev = last;
        last = new;
        head->prev = last;
        last->next = head;
    }
}

void insert_at_position(int info, int position)
{   
    struct node *new, *ptr, *prevnode;
    int len = 0, i;

    new = create_node(info);

    if (head == last && head == NULL)
    {
        if (position == 1)
        {
            head = last = new;
            head->next = last->next = NULL; 
            head->prev = last->prev = NULL;
        }
        else
            printf("\n empty linked list you cant insert at that particular position");
    }
    else
    {
        if (length < position)
            printf("\n node cant be inserted as position is exceeding the linkedlist length");

        else
        {
            for (ptr = head, i = 1;i <= length;i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (i == position-1)
                {
                    prevnode->next = new;
                    new->prev = prevnode;
                    new->next = ptr;
                    ptr->prev = new;
                    break;
                }
            }
        }
    }
}

void sort_list()
{   
    struct node *temp, *ptr;
    int tempdata, i, j;

    if (head == last && head == NULL)
        printf("\nlinked list is empty no elements to sort");
    else
    {
        for (ptr = head,i = 0;i < length;ptr = ptr->next,i++)
        {
            for (temp = ptr->next,j=i;j<length;j++)
            {
                if (ptr->data > temp->data)
                {
                    tempdata = ptr->data;
                    ptr->data = temp->data;
                    temp->data = tempdata;
                }
            }
        }
        for (ptr = head, i = 0;i < length;ptr = ptr->next,i++)
            printf("\n%d", ptr->data);
    }
}

void delete_node_position(int position)
{   
    int count = 0, i;
    struct node *ptr, *temp, *prevnode;

    if (head == last && head == NULL)
        printf("\n empty linked list you cant delete");
    else
    {
        if (length < position)
            printf("\n node cant be deleted at position as it is exceeding the linkedlist length");

        else
        {
            for (ptr = head,i = 1;i <= length;i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (position == 1)
                {   
                    length--;
                    last->next = prevnode->next;
                    ptr->prev = prevnode->prev;
                    head = ptr;
                    free(prevnode);
                    break;      
                }
                else if (i == position - 1)
                {   
                    length--;
                    prevnode->next = ptr->next;
                    ptr->next->prev = prevnode;
                    free(ptr);
                    break;
                }
            }
        }
    }
}

void update(int olddata, int newdata)
{   
    int i, f = 0;
    struct node *ptr;

    if (head == last && head == NULL)
        printf("\n list is empty no elemnts for updation");
    else
    {   
        for (ptr = head, i = 0; i < length; ptr = ptr->next,i++)
        {   
            if (ptr->data == olddata)
            {   
                ptr->data = newdata;
                printf("value is updated to %d", ptr->data);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n no such old value to be get updated");
    }
}

void search(int key)
{
    int count = 0, i, f = 0;
    struct node *ptr;

    if (head == last && head == NULL)
        printf("\nlist is empty no elemnets in list to search");
    else
    {
        for (ptr = head,i = 0; i < length; i++,ptr = ptr->next)
        {
            count++;
            if (ptr->data == key)
            {
                printf("\n the value is found at position at %d", count);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n the value is not found in linkedlist");
    }
}

void display_from_begining()
{
    int i;
    struct node *ptr;

    if (head == last && head == NULL)
        printf("\nlist is empty no elemnts to print");
    else
    {   
        printf("\n%d number of nodes are there", length);
        for (ptr = head, i = 0;i < length;i++,ptr = ptr->next)
            printf("\n %d", ptr->data);
    }
}

void display_in_reverse()
{
    int i;      
    struct node *ptr;

    if (head == last && head == NULL)
        printf("\nlist is empty there are no elments");
    else
    {
        for (ptr = last, i = 0;i < length;i++,ptr = ptr->prev)
        {
            printf("\n%d", ptr->data);
        }
    }
}
READ MORE

What is Queue
Queue is a abstract data type with two operation add_data(enque) and get_data(deque) and provides the data in the form of its arrival or simply it maintains the first in first out machenism (FIFO). Data is always added to its top and retrieved from its rear.

Queue ADT

Required Functions

int queue_size()
struct node * create_node(int data)
void add_data(int data)
int get_data()
void traverse_queue()

Sample Code

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

struct node *top, *rear;
int length= 0;

int queue_size()
{
    printf("\n No. of elements in queue : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_data(int data)
{
    struct node *new;
    new = create_node(data);

    if ((top == NULL) && (rear == NULL))
    {
        top = new;
        rear = new;
    }
    else
    {
        top->next = new;
        top = new;
    }
}

int get_data()
{
    struct node *temp_rear;
    int ret_val;

    temp_rear = rear;

    if (temp_rear == NULL)
    {
        printf("\n Error : Trying to pop from empty queue");
        return -1;  // Assuming -1 as error
    }
    else
    {
        temp_rear = temp_rear->next;
    }

    printf("\n Popped value : %d", rear->data);
    ret_val = rear->data;

    free(rear);
    rear = temp_rear;

    length--;
    return ret_val;
}

void traverse_queue()
{
    struct node *temp_rear;

    temp_rear = top;

    if (temp_rear == NULL)
    {
        printf("Queue is empty");
        return;
    }

    while (temp_rear != NULL)
    {
        printf("%d ", temp_rear->data);
        temp_rear = temp_rear->next;
    }
} 
READ MORE

A circular linklist is the linklist whose last node points to the head node in place of null.
LinkList

To convert a linklist to circular linklist we need to find the last node i.e. the node which is pointing to null and make it to point at the head.

Sample Implementation

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

struct node *head;
int length= 0;

int list_size()
{
    printf("\n No. of elements in List : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_node(int data)
{
    struct node *new;
    new = create_node(data);

    if (head == NULL)
    {
        head = new;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

void to_circular(struct node **p)
{
    struct node *rear;

    rear = *p;
    while (rear->next != NULL)
    {
        rear = rear->next;
    }
    rear->next = *p;
}

// Should be called after converting to circular only
void display_list() 
{
    struct node *temp_head;

    temp_head = head;

    if (temp_head == NULL)
    {
        printf("List is empty");
        return;
    }

    while (temp_head != head)
    {
        printf("%d ", temp_head->data);
        temp_head = temp_head->next;
    }
}  
READ MORE

What is Stack
A stack is a ADT which has LIFO i.e. last in first out behavior. Which means the element which is enetered at the later would be accessed at first. A Stack has two basic operations which are called push and pop which are used to store and retrieve data from the stack.

Stack ADT

Required Functions
Though only push and pop are the necessary function but lets define the following function for the stack implementation in C using LinkList.

int stack_size()
struct node * create_node(int data)
void push(int data) 
void pop()
void traverse_stack()

Sample Code

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

struct node *top;
int length= 0;

int stack_size()
{
    printf("\n No. of elements in stack : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void push(int data)
{
    struct node *new;
    new = create_node(data);

    if (top == NULL)
    {
        top = new;
    }
    else
    {
        new->next = top;
        top = new;
    }
}

void pop()
{
    struct node *temp_top;

    temp_top = top;

    if (temp_top == NULL)
    {
        printf("\n Error : Trying to pop from empty stack");
        return;
    }
    else
        temp_top = temp_top->next;

    printf("\n Popped value : %d", top->data);
    free(top);
    top = temp_top;

    length--;
}

void traverse_stack()
{
    struct node *temp_top;

    temp_top = top;

    if (temp_top == NULL)
    {
        printf("Stack is empty");
        return;
    }

    while (temp_top != NULL)
    {
        printf("%d ", temp_top->data);
        temp_top = temp_top->next;
    }
}
READ MORE
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...