What are Doubly Linked Lists?


After reading this article you should be able to answer the following questions.

  • What are doubly linked lists?
  • How doubly linked lists are implemented?
  • What are the applications for doubly linked lists?
  • How doubly linked lists are different than singly-linked lists?

Introduction

The following are problems with singly linked lists:

  1. A singly linked list allows traversal of the list in only one direction.
  2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
  3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.

These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively.

The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in Figure 1.

Figure 1 : Doubly Linked List as a chain

If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in Figure 2

Figure 2 : Doubly Linked List maintained as circular list

If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in Figure 3.

Figure 3 : A doubly linked list maintained as a circular list with a header node.

Therefore, the following representation is required to be used for the nodes of a doubly linked list.


struct dnode  {
      int data;
      struct dnode *left,*right;
   };

Inserting into a doubly linked list is done as :

struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
        struct dnode *temp;
        /* if the existing list is empty then insert a new node as the
           starting node */
        if(p==NULL)
        {
                p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new
                                                                   node data value
                                                                   passed as parameter */

                if(p==NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                p->data = n;
                p-> left = p->right =NULL;
                *q =p;
        }
        else
        {
                temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates
                                                                        new node using
                                                                        data value passed as
                                                                        parameter and puts its
                                                                        address in the temp
                                                                      */
                if(temp == NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                temp->data = n;
                temp->left = (*q);
                temp->right = NULL;
                (*q)->right = temp;
                (*q) = temp;
        }
        return (p);
}

2 Comments

How to delete a specified node from a Linked List?


Deleting a specified node from a linked List

To delete a node, first we determine the node number to be deleted (this is based on the assumption that the nodes of the list are numbered serially from 1 to n). The list is then traversed to get a pointer to the node whose number is given, as well as a pointer to a node that appears before the node to be deleted. Then the link field of the node that appears before the node to be deleted is made to point to the node that appears after the node to be deleted, and the node to be deleted is freed.

Implementation :

struct node *delet ( struct node *p, int node_no )
{

        struct node *prev, *curr ;
        int i;

        if (p == NULL )
        {
                printf("There is no node to be deleted \n");
        }
        else
        {
                if ( node_no > length (p))
                {
                        printf("Error\n");
                }
                else
                {
                        prev = NULL;
                        curr = p;
                        i = 1 ;
                        while ( i < node_no ) { prev = curr; curr = curr-> link;
                                i = i+1;
                        }
                        if ( prev == NULL )
                        {
                                p = curr -> link;
                                free ( curr );
                        }
                        else
                        {
                                prev -> link = curr -> link ;
                                free ( curr );
                        }
                }
        }
        return(p);
}
/* a function to compute the length of a linked list */
int length ( struct node *p )
{
        int count = 0 ;
        while ( p != NULL )
        {
                count++;
                p = p->link;
        }
        return ( count ) ;
}

Figure 1 : before delete

Figure 2 : After delete

1 Comment

Sorting and Reversing a Linked List


This article will traverse you through few easy steps to sort a linked list. Linked list needs to be sorted for many applications in computer science.  If you haven’t already ready my article of basic knowledge for Linked List, I would recommend to go through that first. You may also be interested to check out how to delete a node form a linked list.

Sorting a Linked List

To sort a linked list, first we traverse the list searching for the node with a minimum data value. Then we remove that node and append it to another list which is initially empty. We repeat this process with the remaining list until the list becomes empty, and at the end, we return a pointer to the beginning of the list to which all the nodes are moved, as shown in Figure 1.

Figure 1: Sorting a linked list

Reversing a Linked List

To reverse a list, we maintain a pointer each to the previous and the next node, then we make the link field of the current node point to the previous, make the previous equal to the current, and the current equal to the next, as shown in Figure 2.

Figure 2 : A linked list showing the previous, current, and next nodes at some point during reversal process.

Therefore, the code needed to reverse the list is:

Therefore, the code needed to reverse the list is

Prev = NULL;
While (curr != NULL)
{
Next = curr->link;
Curr -> link = prev;
Prev = curr;
Curr = next;
}

Implementation :

Sorting a Linked List:


/* a function to sort a list */
struct node *sortlist(struct node *p)
{
        struct node *temp1,*temp2,*min,*prev,*q;
        q = NULL;
        while(p != NULL)
        {
                prev = NULL;
                min = temp1 = p;
                temp2 = p -> link;
                while ( temp2 != NULL )
                {
                        if(min -> data > temp2 -> data)
                        {
                                min = temp2;
                                prev = temp1;
                        }
                        temp1 = temp2;
                        temp2 = temp2-> link;
                }
                if(prev == NULL)
                        p = min -> link;
                else
                        prev -> link = min -> link;
                min -> link = NULL;
                if( q == NULL)
                        q = min; /* moves the node with lowest data value in the list
                                    pointed to by p to the list
                                    pointed to by q as a first node*/
                else
                {
                        temp1 = q;
                        /* traverses the list pointed to by q to get pointer to its
                           last node */
                        while( temp1 -> link != NULL)
                                temp1 = temp1 -> link;
                        temp1 -> link = min; /* moves the node with lowest data value
                                                in the list pointed to
                                                by p to the list pointed to by q at the end of list pointed by
                                                q*/
                }
        }
        return (q);
}

Reversing a Linked List:

/* a function to sort reverse list */
struct node *reverse(struct node *p)
{
        struct node *prev, *curr;
        prev = NULL;
        curr = p;
        while (curr != NULL)
        {
                p = p-> link;
                curr-> link = prev;
                prev = curr;
                curr = p;
        }
        return(prev);
}

Leave a comment

Now its time for Blackberry Playbook


Just after Apple released iPad and has seen a huge success of the product worldwide. The other companies are trying to catch up with tablet products. BlackBerry maker Research In Motion is jumping into the tablet arena with the PlayBook. It will have a 7-inch screen and is designed for both personal and business users.

The insides of  Blackberry Playbook sound pretty good as well, and almost put the iPad to shame: a dual-core 1GHz processor, 1GB RAM, front and rear facing cameras that both support high definition, Flash 10.1 with hardware acceleration, HDMI out, USB, and HTML5 support.

It’s got a widescreen 1024 x 600 display that supports multi-touch, and RIM was proud to announce that the Playbook will connect with BlackBerry enterprise servers right out of the box. Now, on paper Blackberry Playbook sounds powerful, but it’s really going to be the UI and user experience in software that will make or break this thing.

Blackberry playbook

RIM says that the Blackberry Playbook isn’t just for business, and that its OpenGL support is perfect for gaming. It also has e-reader capabilities, and a full web browser, as previously mentioned. Expect the BlackBerry App World to make an appearance here as well, along with in-app purchase integration that developers will be able to tap in to. RIM also says that the BlackBerry Playbook will be offerred in 3G and 4G models in the future.

Blackberry Playbook

Lets see who takes over in this tablet war. iPad already has decent market share but how these new devices are going to snatch the attraction, has yet to be seen.

Blackberry Playbook Specifications :

Blackberry Playbook Specs

  • 1 GHz Dual Core Processor
  • 1 GB RAM
  • 7 inch LCD  display with 1024 x 600 screen resolution
  • Multitouch capacitive display
  • Dimensions : 130mm x 194mm x 10mm
  • Weight : 400g
  • microUSB , micro HDMI and DLNA connectivity
  • Wi-Fi 802.11 a/b/g/n
  • Bluetooth 2.1 + EDR
  • Powered by QNX platform with multitasking
  • Full Adobe Flash 10.1 support
  • Built-in support for HTML 5
  • Video Conferencing with HD Quality and Stereo sound
  • 5 MP Rear Camera
  • 3 MP Front Camera
  • Video playback : 1080p HD video – H.264, MPEG4, WMV , DivX formats
  • Audio Playback :MP3, AAC, WMA
  • Pair with any Blackberry Device ( min OS 5.0 device)  via Bluetooth for Push Email , Calendar , Docs and BBM

Blackberry Playbook Vs iPad

Blackberry Playbook is already compared with Apple’s iPad and the it would be mostly based on Portability , Processor Power, Display and App Store. Blackberry Playbook surely has got better processor power and portability than iPad but it would be a hart nut to break for them to beat Apple’s display and touch effect. Apple’s app store is another thing they will find it difficult to crack.

iPad and Blackberry Playbook

Blackberry Playbook - Portability

Leave a comment

How to implement a linked list?


After reading this article you should be able to answer:

  • What is a linked list?
  • Why do we need a linked list?
  • How to implement a linked list?
  • What is the structure of a linked list node?
  • How to insert a node into a linked list?
  • How to print the existing linked list?

THE CONCEPT OF THE LINKED LIST

Introduction

When dealing with many problems we need a dynamic list, dynamic in the sense that the size requirement need not be known at compile time. Thus, the list may grow or shrink during runtime. A linked list is a data structure that is used to model such a dynamic list of data items, so the study of the linked lists as one of the data structures is important.

Concept

An array is represented in memory using sequential mapping, which has the property that elements are fixed distance apart. But this has the following disadvantage: It makes insertion or deletion at any arbitrary position in an array a costly operation, because this involves the movement of some of the existing elements.

When we want to represent several lists by using arrays of varying size, either we have to represent each list using a separate array of maximum size or we have to represent each of the lists using one single array. The first one will lead to wastage of storage, and the second will involve a lot of data movement.

So we have to use an alternative representation to overcome these disadvantages. One alternative is a linked representation. In a linked representation, it is not necessary that the elements be at a fixed distance apart. Instead, we can place elements anywhere in memory, but to make it a part of the same list, an element is required to be linked with a previous element of the list. This can be done by storing the address of the next element in the previous element itself. This requires that every element be capable of holding the data as well as the address of the next element. Thus every element must be a structure with a minimum of two fields, one for holding the data value, which we call a data field, and the other for holding the address of the next element, which we call link field.

Therefore, a linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is, by storing the address of the next element in the link field of the previous element.

In other words,

A linked list is a set of nodes. Each node contains a value and at least one link, which tells where to find another node. The format of a node may be a structure such as a record or an array. The crucial idea is that each node in a linked list contains information about how to find the next in a sequence of nodes. Immediate access to every node is not necessary, for one node will lead to another, just as stepping stones lead from one side of a creek to another.

In the simplest arrangement, shown in Figure

Figure 1 : Simplest Arrangement of Linked List

1, the links are linear: the address of Node 1 is stored in variable Head, a link to node 2 is stored in node 1, and so forth. The last link points to a special node, NIL, which is recognizably not the address of any node.

However, doubly linked lists are slightly different. Read it here.

Implementation :


Structure of a node of a linked list

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

Inserting a new node in the linked list

struct node *insert(struct node *p, int n)
{
        struct node *temp;
        /* if the existing list is empty then insert a new node as the
           starting node */
        if(p==NULL)
        {
                p=(struct node *)malloc(sizeof(struct node)); /* creates new node
                                                                 data value passes
                                                                 as parameter */

                if(p==NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                p-> data = n;
                p-> link = p; /* makes the pointer pointing to itself because it
                                 is a circular list*/
        }
        else
        {
                temp = p;
                /* traverses the existing list to get the pointer to the last node of
                   it */
                while (temp-> link != p)
                        temp = temp-> link;
                temp-> link = (struct node *)malloc(sizeof(struct node)); /*
                                                                             creates new node using
                                                                             data value passes as
                                                                             parameter and puts its
                                                                             address in the link field
                                                                             of last node of the
                                                                             existing list*/
                if(temp -> link == NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                temp = temp-> link;
                temp-> data = n;
                temp-> link = p;
        }
        return (p);
}

Print the linked list


void printlist ( struct node *p )
{
        struct node *temp;
        temp = p;
        printf("The data values in the list are\n");
        if(p!= NULL)
        {
                do
                {
                        printf("%d\t",temp->data);
                        temp=temp->link;
                } while (temp!= p);
        }
        else
                printf("The list is empty\n");
}

4 Comments