Linked List 2(sstutor)

Linked List (Part 2)

The complete program will be as below (along with the output):

//A class to simulate a Linked List

#include <iostream>
using namespace std;

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
        }

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

//Function to add a new node to the end of the linked list

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
    }
}

//Function to display the contents of the linked list

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

int main( )
{
    list x;
    x.addnode(2);
    x.addnode(1);
    x.addnode(12);
    x.addnode(10);
    x.display( );
    return 0;
}

The output will be:

2
1
12
10
destroying node
destroying node
destroying node
destroying node

Assignments:

There are some more things you can do to your linked list class. You can write an insert statement to insert a new node in a particular location. You can write a function to delete a node (while deleting you have to physically remove the node using the 'delete' operator and you have to change the address stored in the previous node). Create a template for a linked list (so that the linked list can be used to hold any type of data).

Singly linked lists: What we have discussed so far are called singly linked lists (because they contain the address of only the next node – i.e. they can be used to traverse the list in one direction alone).

Doubly linked lists: These linked lists contain nodes having 2 pointers (one points to the next node and one points to the previous node). Thus you can traverse the linked list either forward or backwards.

Circular linked list: In this type of linked list the last node (i.e. the ‘tail’) will point to the first node (instead of pointing to the NULL address).

Continue learning linked lists in the next topic: Linked Lists using STL

Go back to Contents page 2.