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 Doubly Linked Lists

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

In this tutorial you will learn about C Programming – What is Doubly linked lists, Adding Nodes Doubly linked lists, Traversing a Doubly linked lists and working with Doubly linked list Example.

Doubly linked lists are the same as singly linked lists, except they have an extra pointer per node so they point to the next node and the previous node. You just make sure that whenever you insert a node you set next to the next node and previous to the previous node. They will also commonly keep a tail and head pointer so that traversal may start at either end of the list.

Doubly Linked List Nodes

A doubly linked list node would look like this:

  1. struct dllnode {
  2.  
  3. 	  Arbitrary Data Portion
  4.  
  5.   	  struct dllnode *next; 
  6. 	  struct dllnode *previous;
  7. 	};

It contains a data portion and a pointer to both the next and previous nodes in the list sequence allowing for two-way traversal.

Creating A Doubly Linked List

When creating a doubly linked list, we want to be able to go both ways as well as be able to start at either end of the list when traversing it. As mentioned earlier, we use a both a tail and a head pointer to provide this functionality.

Checking for head being NULL is sufficient for checking for an empty list.

  1. if (head == NULL) {
  2. 	    //This node becomes the first and last node in the list.                    
  3. 	    newnode->previous =	NULL;
  4. 	    newnode->next = NULL;
  5. 	    head = newnode;
  6. 	    tail = head;
  7. 	}

Pretty much the same as we have done throughout this tutorial with the singularly linked lists, with the addition of the previous pointer needing to be set to NULL and the tail also being equal to the new node.

Inserting Nodes

Same as linear singularly linked lists, we can add at the beginning, middle, or end of a doubly linked list.

Placing a node at the beginning of a doubly linked list is quite simple but an empty and nonempty must be handled differently.

When the list is empty all you have to do is create the new node, set its next and previous pointers to NULL, and point the head and tail pointers to it. We already saw the code for this in the last section.

Inserting a new node at the beginning of a nonempty doubly linked list is a little tricky, but not impossible. First you create your new node and set its previous pointer to NULL, but the next pointer to the current head. Then set the current head’s previous pointer to the new node being inserted to move the old head one up in the list. Now all you have to do is point head at the new node and you are done.

In code it should look something like this

  1. newnode->previous = NULL;
  2.     newnode->next = head;
  3.     head->previous = newnode;
  4.     head = newnode;

Insertion of a new node at the end of the list is quite similar although we use the tail pointer as a reference instead of the head pointer. Since the empty list case here is identical to the empty list case above for insert at beginning we will skip it.

To place a node at the end of the nonempty list you create the new node, set its next pointer to NULL and its previous pointer to the current tail. Then set the current tail’s next pointer to the new node. Now point tail to the new node which you have inserted a node at the back of the list. Although it’s not in our example, here is a code snippet

  1. newnode->next = NULL;
  2.     	newnode->previous = tail;
  3.     	tail->next = newnode;
  4.     	tail = newnode;

Note the similarity to the sample for insertion at the beginning.

Here’s the fun part, this is the greatest feature of the doubly linked list. It’s actually so simple though, you may be disappointed.

Forward traversal is identical to singly linked list traversal. Seriously, there is no difference. This should look familiar.

  1. if (head != NULL) {
  2. 	    currentnode = head;
  3. 	    while (currentnode->next != NULL) { 
  4. 	      currentnode = currentnode->next; 
  5. 	    }
  6.      	}

With that in mind, you would think that going the other way would be the same but with the tail pointer. You would be correct.

  1. if (tail != NULL) { 
  2. 	    currentnode = tail;
  3. 	    while (currentnode->previous != NULL) { 
  4. 	      currentnode = currentnode->previous; 
  5. 	    }
  6.      	}

A common thing to do in game programming is to keep a list of objects currently on the screen. One reason is for updating the screen to make them appear to move. Linked lists are perfectly suited to this purpose because of their dynamic nature. Let’s make a list of the x and y coordinates of all objects currently displayed on a screen for an arbitrary game.

We don’t want to do too much because it will take attention away from the main topic, so all we are going to do is create a list of five objects and print the locations of each object forwards and then backwards. There is no limit to what you could do besides simply printing the coordinates but this example should be sufficient for the basics.

The sample has one function for adding nodes to the front of the list. It takes into account the empty and nonempty list cases we learned about above.

Then it creates five objects that have an x and y coordinate, and adds the nodes to the list by calling the addnode function and passing it the newly created node, thus making the last node added at the beginning of the list and the first node added the end.

After the list is created and all the game objects coordinates are known, we traverse the list from the beginning to the end and print all the x and y values for each object. Then we do the same, but start from the tail and go back to the head.

  1.  #include <stdio.h>
  2.  #include <stdlib.h>
  3.  
  4. struct dllnode {
  5.   int x;
  6.   int y;
  7.   struct dllnode *next;
  8.   struct dllnode *previous;
  9. };
  10.  
  11. //Here's the doubly linked list root pointers.
  12. struct dllnode *head = NULL;
  13. struct dllnode *tail = NULL;
  14.  
  15. void addnode(struct dllnode *newnode) {
  16.  
  17.   if (head == NULL) {
  18.     //This node becomes the first and last node in the list.
  19.     newnode->previous = NULL;
  20.     newnode->next = NULL;
  21.     head = newnode;
  22.     tail = head;
  23.  
  24.   } else {
  25.     //List is not empty, insert at front of list.
  26.     newnode->previous = NULL;
  27.     newnode->next = head;
  28.     head->previous = newnode;
  29.     head = newnode;
  30.   }
  31. }
  32.  
  33. void main() {
  34.   int i;
  35.   int x, y;
  36.   struct dllnode *current;
  37.  
  38.   //Create 5 objects in a diagonal line across the screen from eachother.
  39.   for (i = 0; i < 5; i++) {
  40.     struct dllnode *newnode;
  41.     x = y = i;
  42.     newnode = (struct dllnode *)malloc(sizeof(struct dllnode));
  43.     newnode->x = x;
  44.     newnode->y = y;
  45.  
  46.     addnode(newnode);
  47.   }
  48.  
  49.   //Traverse the list and print the current position of each object.
  50.   current = head;
  51.   i = 1;
  52.   while (current != NULL) {
  53.     printf("Object %d: ", i);
  54.     printf("n");
  55.     printf(" x position: %d", current->x);
  56.     printf("n");
  57.     printf(" y position: %d", current->y);
  58.     printf("n");
  59.     i++;
  60.     current = current->next;
  61.   }
  62.  
  63.   //Do the same but start at the back of the list.
  64.   current = tail;
  65.   i = 1;
  66.   while (current != NULL) {
  67.     printf("Object %d: ", i);
  68.     printf("n");
  69.     printf(" x position: %d", current->x);
  70.     printf("n");
  71.     printf(" y position: %d", current->y);
  72.     printf("n");
  73.     i++;
  74.     current = current->previous;
  75.   }
  76. }

Here is a screenshot after running the example program. As you can see, it went through the list starting at the beginning then again from the end, creating the mirror image as seen here.

« « How OOAD is used in the Real World
C Circular Linked Lists » »

Author Description

Avatar

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Programming – File management in C

    May 31, 2006 - 0 Comment
  • C Programming – Decision Making – Branching

    April 4, 2006 - 0 Comment
  • C Language – The Preprocessor

    May 31, 2006 - 0 Comment
  • 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 – An Overview

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

    August 21, 2011 - 0 Comment
  • C Circular 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 Circular 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