Double linked list in c++ implementation

In this double linked list tutorial we go step by step in building our doubly linked list and towards the end we have the source code for a complete program implementing the doubly liked list.

The linked list is a collection of nodes of a given type

For demonstration purpose we create a type NODE of the structure node.

typedef struct node
{
	int data;   // stores the node data
	node *next,*prev;// 2 ptrs(ptr vars),will have mem add,holding node type
}NODE;

we have an integer data element and two pointer variables of the node type *prev and *next
in our linked list,these two pointer variables connect the present node to the previous and the next node in the chain of the double linked list.These two variables will hold the memory address of the previous and the next node in case the nodes are there and NULL or no address otherwise.

We begin by creating a new node

NODE* create(int num)  // fn returns a pointer(add) of NODE type(add of new node)
						// null if node not created
						//fn is passed the value with which node to be populated
{
	NODE *temp;
	temp=new NODE;
	if(temp)  // Mem allocated sucessfully,ie temp not NULL
	{

		temp->data=num;
		temp->next=NULL;//new node doesnt pt anywhere yet,till anothernode created
		temp->prev=NULL;
		return temp;
	}
	else
	{
		cout<<"\n\n\t\tOut of memory ! Press a key to continue ...";getch();
		return NULL;
	}
}

A pointer var of type NODE is declared in line 5.A new NODE is created and the address of the newly created node is assigned to the pointer variable temp in line 6. In line 7 we check that when the new node was created using the new,the creation of the node was successful and a valid address of the newly created node was returned.If the creation of the node was not successfull,new would have returned null,and the if would fail in line 7.The integer data passed in the argument is assigned to the data element of the node structure in line 10.The *next and *prev pointers presently do not point anywhere. The function returns the address of the newly created node.This address can easily be assigned to a pointer variable of the NODE type,in the calling program,as we shall see later.

Also a function which creates a node without any data will look like

NODE* create()  // fn returns a pointer(add) of NODE type(add of new node)
						// null if node not created,node data made=0
{
	NODE *temp;
	temp=new NODE;
	if(temp)  // Mem allocated sucessfully,ie temp not NULL
	{

		temp->data=0; //no data passed ,by default init to zero
		temp->next=NULL;//new node doesnt pt anywhere yet,till anothernode created
		temp->prev=NULL;
		return temp;
	}
	else
	{
		cout<<"\n\n\t\tOut of memory ! Press a key to continue ... ";getch();
		return NULL;
	}
}

Continue reading the remaining 6 pages of the article through page links below ....