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");
}

Advertisements
  1. Sorting and Reversing a Linked List « Encrypt3d
  2. Merging two sorted linked lists !! « Encrypt3d
  3. What are Doubly Linked Lists? « Encrypt3d
  4. How to insert a node in a linked list recursively? « Encrypt3d

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: