Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Circular Linked Lists

By Brian Moriya | on June 26, 2011 |
C Language

In this tutorial you will learn about C Programming – What is Circular Linked List, Adding Nodes to Circular Linked Lists, Traversing a Circularly Linked List and working with Circularly Linked List Example.

Circular linked lists are usually used for a queue or stack type situation, or for implementing a round robin algorithm in system level programming. You could also use one for a multiplayer game where you were keeping track of player’s turns where it just repeats until the game ends.

They are exactly the same as a singly linked list, but instead of setting the next pointer in the last node of the list to NULL, you set it to point to head. Hence the name circular. Instead of a head pointer, they commonly use a tail pointer instead to keep track of the last node.

A cingularly linked list node looks exactly the same as a linear singly linked list. Here’s the node for the example programming example.

  1. struct cllnode {
  2. 	  char name[4];
  3. 	  struct cllnode *next;
  4. 	};

It should be familiar from the previously introduced linear linked list, just a data portion and the next pointer.

Adding Nodes to Circular Linked Lists

Adding nodes and creating new circularly linked lists is very similar to the linear ones we learned previously. Let’s look at our example to illustrate.

  1. void addNode(struct cllnode *newnode) {
  2. 	  //List is empty. Create new list.                                             
  3. 	  if (tail == NULL) {
  4.  
  5. 	    tail = newnode;
  6. 	    newnode->next = tail;
  7.  
  8. 	  } else {
  9. 	    //List isn't empty so add at the tail. Remember "first in first out."       
  10. 	    newnode->next = tail->next;
  11. 	    tail->next = newnode;
  12. 	    tail = newnode;
  13. 	  }
  14. 	}

That addNode function is all it takes to handle both the empty and non-empty singularly linked list cases when adding new nodes. You add at the back of the list in this linked list case and that’s one of the reasons these are used for modeling queues and FIFO stacks.

Just as in the singularly linked list case you first check if the list pointer (no matter what you are calling it) is NULL. Then set the tail equal to the new node being added and make its pointer point back at itself, thus completing the circle.

When there are nodes in the list, you first set the new node’s next pointer to tail->next because you are adding it just after tail, not at tail. You may be able to see why we use tail pointers rather than head pointers for circularly linked lists. The head would be 2 pointers away from where we perform insertions.

After that, you set tail’s next pointer to the new node and set tail equal to the new node. Viola, we have inserted a new node at the end of the list, and tail is now pointing at it.

Traversing a Circularly Linked List

Traversing a circularly linked list is a little different than the regular type, due to the fact that there is no NULL termination to tell you when to stop. However, we can just use the tail pointer for this purpose as well.

As we see in this snippet of our example program, it’s not any more difficult to traverse, it’s just different

  1. if (tail != NULL) {
  2. 	    current = tail->next;
  3.  
  4. 	    while (current != tail) {
  5.  
  6. 		...
  7.  
  8.       	current = current->next;
  9. 	    }
  10.  
  11. 	    current = tail;
  12.  
  13. 	    ...
  14. 	  }

We begin with the familiar check for the list’s existence. If we have a list, we set the current pointer to the node after tail. From here we can just go through the nodes until we return to tail, so we use a while loop to do that. The traversal is the same as before in that you just set the current pointer to the next one at the end of the wile loop.

Now if you want to do something when you get to the tail you must do it after the while loop traversal, because our condition stopped the traversal at the node just before tail and started just after it. As you can see we had to add an addition print out block after the while loop to be able to see the last node’s information printed out.

This example models a turn based game with four players. It creates a circularly linked list of the four players, and starts traversing through the list for each player’s turn, giving them a prompt when it reaches them.

Note the first player joins gets their turn first, and the last player gets his turn at the end. This is the queue behavior of the circularly linked list.

  1.  #include <stdio.h>
  2.  #include <stdlib.h>
  3.  
  4. struct cllnode {
  5.   char name[4];
  6.   struct cllnode *next;
  7.  
  8. };
  9.  
  10. //The circular linked list tail pointer.
  11. struct cllnode *tail = NULL;
  12.  
  13. void addNode(struct cllnode *newnode) {
  14.   //List is empty. Create new list.
  15.   if (tail == NULL) {
  16.     tail = newnode;
  17.  
  18.     newnode->next = tail;
  19.  
  20.   } else {
  21.     //List isn't empty so add at the tail. Remember "first in first out."
  22.     newnode->next = tail->next;
  23.     tail->next = newnode;
  24.     tail = newnode;
  25.   }
  26. }
  27.  
  28. void main() {
  29.   int i;
  30.   char players[4][4] = {
  31.     "Bob", "Tom", "Tim", "Joe"
  32.   };
  33.  
  34.   //Use this node for traversing the list.
  35.   struct cllnode *current;
  36.  
  37.   //Create a circularly linked list for the players
  38.   for (i = 0; i < 4; i++) {
  39.     //Create node for each of the players in the players array.
  40.     struct cllnode *newnode;
  41.     newnode = (struct cllnode *)malloc(sizeof(struct cllnode));
  42.     strcpy(newnode->name, players[i]);
  43.  
  44.     //Add the 4 players to the queue.
  45.     addNode(newnode);
  46.   }
  47.  
  48.   //Check that list isn't empty.
  49.   if (tail != NULL) {
  50.     //Set node to the first item in the list.
  51.     current = tail->next;
  52.  
  53.     //Go around the loop until we return to the tail pointer.
  54.     while (current != tail) {
  55.       printf("It's your turn: ");
  56.       puts(current->name);
  57.       printf("n");
  58.       sleep(3);
  59.  
  60.       //traverse the list.
  61.       current = current->next;
  62.     }
  63.  
  64.     //Have to print tail separately.
  65.     current = tail;
  66.  
  67.     printf("It's your turn: ");
  68.     puts(current->name);
  69.     printf("n");
  70.     sleep(3);
  71.  
  72.     //Clean up current.
  73.     current = NULL;
  74.   }
  75. }

When you compile and run this example, you should see the first message saying that it’s the first player’s turn. The program will pause for 3 seconds before moving on through the rest of the players’ turns.

The output of the above code if unmodified should look like this after it finishes.

« « C Doubly Linked Lists
UML Usage in OOAD » »

Author Description

Avatar

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Programming – Decision Making – Looping

    April 4, 2006 - 0 Comment
  • Call by Value and Call by Reference

    July 6, 2006 - 0 Comment
  • C Programming – Arrays

    April 13, 2006 - 0 Comment
  • Concept of Pixel in C Graphics

    July 11, 2006 - 0 Comment
  • C Programming – Handling of Character String

    April 17, 2006 - 0 Comment
  • TSR in C – An Introduction

    July 11, 2006 - 0 Comment
  • C Programming – Functions (Part-II)

    May 22, 2006 - 0 Comment
  • C Programming – Data Types : Part 2

    August 21, 2011 - 0 Comment
  • C Programming – An Overview

    March 2, 2006 - 0 Comment
  • C Programming – Functions (Part-I)

    May 23, 2006 - 0 Comment
  • C Programming – Data Types : Part 2

    August 21, 2011 - 0 Comment
  • C Doubly Linked Lists

    June 26, 2011 - 0 Comment
  • TSR in C – An Introduction

    July 11, 2006 - 0 Comment
  • Concept of Pixel in C Graphics

    July 11, 2006 - 0 Comment
  • Call by Value and Call by Reference

    July 6, 2006 - 0 Comment
  • C Language – The Preprocessor

    May 31, 2006 - 0 Comment
  • C Programming – File management in C

    May 31, 2006 - 0 Comment
  • C Programming – Linked Lists

    May 29, 2006 - 0 Comment
  • C Programming – Dynamic Memory allocation

    May 29, 2006 - 0 Comment
  • C Programming – Pointers

    May 25, 2006 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Programming – Data Types : Part 2
  • C Doubly Linked Lists
  • TSR in C – An Introduction
  • Concept of Pixel in C Graphics
  • Call by Value and Call by Reference

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT