Linked List 1(sstutor)

Linked List 1

Introduction:

Data structure refers to the way we arrange data or the way in which data is stored in memory. There are different types of data structures. Array is a simple data structure that we have already seen.

We come across data structures in everyday life as well. When we go shopping, it is common practice to prepare a shopping list. Might be something like below:

Noodles - 2 packets

Tomatoes - 1 kg

Cornflakes - 1

Chocolate

Bread

A data structure is simply a way of organizing data and we have organized data in our shopping list as well. From what we’ve learnt so far we would categorize this as an array perhaps. The information isn’t sorted and we simply keep increasing the list when we think of more things to buy. But the problem with arrays is that they are fixed. You can’t keep on increasing their size as and when you feel like it. So we have a better data structure called a vector to serve this purpose.

Similarly, we witness queues everyday (either while shopping, booking tickets, waiting in the canteen etc.). A queue is based on the principle of first come first serve. A queue is another data structure.

When writing applications depending on the requirement we would need to use an appropriate data structure to organize information. In this chapter we’ll take a look at some common data structures.

Introduction:

What is a linked list?

If you have read books on memory then you would have come across a concept similar to linked lists. All these books usually explain one method for remembering the names of random objects in order. For example, your friend might read out the following list to you just once:

Sheep, carpet, bottle, cigar, tent

and throw a challenge. The challenge is that after a few minutes you should be able to recollect the five names in the same order. Not a big deal, right? Try it with 20 and you’ll realize the difficulty. Memory experts suggest that we associate each object with the next one in the list; or in other words create a link between every neighbouring object. In our case we might say, “A sheep was born on a carpet, the carpet was rolled into a bottle, the bottle smoked a cigar, the cigar was resting in a tent!” The idea is to form comical associations between two objects since these associations are retained in our memory longer. The beauty of this technique is that if your friend names any object from the list, you will be able to say what is the next object in the list (irrespective of the object’s position in the list).

The linked list data structure is very similar to this (except for the comical association!); and instead of object names, we call the elements of a linked list as nodes. A linked list consists of a series of nodes with each node pointing to the next node in sequence. A node has 2 parts:

Data
Address of the next node

Some points to note about linked lists:

In terms of coding, linked lists are more complex than arrays.
It is easy to increase or decrease the size of a linked list (i.e. you can easily manipulate the size of a linked list). In the case of an array this is a problem.
New nodes in a linked list are created as and when required.
Insertion of new elements (or nodes) is easier. In an array it is quite difficult to insert an element in the middle of the array.
Deletion of a node is easy since only the address part of the previous node needs to be changed.
Every node contains data and also has an address that points to the next node (this part is basically a pointer).

Diagrammatic representation of a linked list:

To distinguish the last node of the linked list from the other nodes, the last node will point to NULL (address 0). The very first node is called the 'head'. It doesn't have a data part and only points to the next node (basically the 'head' indicates the starting position of the linked list).

Creating a linked list:

To aid in the understanding of the linked list concept, let's write a little program which will simulate a linked list. The program should do the following:

Store a set of integers.
It should be possible to delete a particular element.
Permit insertion of a new node (element).
Deletion of a particular node.
A way to display the entire contents of the list.

Let's do this program the OOPs way. First of all we need to have an idea about how we are going to represent a single node of the linked list. The simplest way is to use a structure for a node.

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

'data' is used to hold the data. In this case we are creating a linked list to store only integers (so 'data' is of type int). Every node contains a pointer to the next node. For this we create a pointer pointing to an object of type 'node'. Thus the pointer 'next' will contain the address of the next node.

So, we now have a way to represent a node in our linked list. Let's now model a class to simulate the Linked list itself.

//A class to simulate a Linked List

class list
{
private:
        struct node
        {
            int data;
            node *next;
        };
        node *head;                        //to represent the 'head' of the linked list
public:
        list ( )
        {
            head=NULL;                    //initially the linked list is empty; initialize head to NULL
        }
        void addnode (int);
        void display( );
};

'head' is used to store the starting location of the linked list (we need the starting point of the linked list). When you create an object of type 'list', your new linked list will be empty (which means that 'head' should point to a NULL location since there are no nodes in the linked list). This is why we make use of the constructor to initialize the 'head' value to NULL. The last node is also called the 'tail'.

Adding a new node to the linked list:

First let's see how to add a new node to our linked list. The following steps are involved in adding a new node:

If the 'head' has a value of NULL it means that the node we are going to add is the first node.
If 'head' is not NULL, then identify the last node of the linked list and add the node at the end.

void list::addnode ( int num )
{
    node *newnode, *pointer;

    newnode = new node;                  //creating a new node
    newnode->data = num;                  //assigning the data to the new node
    newnode->next = NULL;              //the new node will be the last node, so point to NULL

    if (head = = NULL)
    {
        head = newnode;        //'head' now contains the pointer to point to the newly added node
    }
    else
    {
        pointer = head;                                    //initialize pointer to the 'head'
        while (pointer->next != NULL)     //move from one node to the next till we reach the tail
        {
            pointer = pointer->next;
        }
        pointer->next=newnode;            //make the last node point to the new node
    }
}

The logic might initially seem confusing. The addnode( ) function is called with an integer argument (this integer is the data that we want to store in the new node). We create a new node saying:

node *newnode;
newnode = new node;

'newnode' is a pointer which points to the structure 'node'. Thus you can access 'data' and 'next' using this pointer (by using the arrow operator). Next we set the elements of the newly created node.

newnode->data = num; //assigning the data to the new node
newnode->next = NULL; //the new node will be the last node, so point to NULL

Supposing the linked list is empty, then the 'head' value will be NULL. Thus there is no need to scan the list and locate the last node. So,

    if (head = = NULL)
    {
        head = newnode;                    //'head' now contains the pointer to point to the newly added node
    }

'head' will now point to the first node of the linked list. In case we want to add more nodes then we need to find out the last node of the list (the last node will be the one which points to NULL). Once we identify this node, all we have to do is assign the address of the newly created node to the 'next' value of the last node.

    else
    {
        pointer = head;                                    //initialize pointer to the 'head'
        while (pointer->next != NULL)           //move from one node to the next till we reach the tail
        {
            pointer = pointer->next;
        }
        pointer->next=newnode;                    //make the last node point to the new node
    }

Displaying the contents of the linked list:

This is relatively simple. All we need to do is traverse through the entire list (from the header to the tail) using a loop. Within the loop we can display the data stored in that node.

void list::display( )
{
    node *pointer;
    pointer = head;                                //start from the 'head'
    while (pointer != NULL)
    {
        cout<<endl<<pointer->data;
        pointer = pointer->next;
    }
}

The above code should be quite self-explanatory.

Whenever you use 'new' use a 'delete':

After using your linked list you will want to destroy all the nodes (i.e. free all the memory allocated using the 'new' operator). For this purpose you could write the code for destroying the list in the destructor as shown below:

~list( )
{
    node *current,*temp;
    current = head;
    temp = current;
    while(current != NULL)
    {
        cout<<endl<<"destroying node";
        temp = current->next;
        delete current;
        current = temp;
    }
}

The next section provides the complete program for a linked list.

or you can go back to Contents page 2.