The same thing is true . When you start working around some simple double linked list you are very closer towards implementing Binary tree and Binary search tree.The following is the basic doubly linked list implementation in C++ (Just an enhancement to previous singly linked list).


/* The simple double linear linked list program written in C/C++
This creates a head node of linked list first and insert the new nodes to the end of linked list .
You have to define the maximum size of linked list on start run .
This program is just a little enhancement of single linear linked list
*/
#include<iostream.h>

struct list
{
int value;
struct list * left;
struct list * right;
};

struct list * insert( struct list *, int);

int main()
{
struct list *head=(struct list *) malloc(sizeof(struct list));
cout <<"Enter the total no of nodes to be present in the linked list\n";
int total_element;
cin >> total_element;
cout<< "Enter the head value\n";
/* Create a head node and assign the value also assign the left and right node address to NULL (The linked list will end with a node whose next address is NULL */
cin >> head ->value;
head->left=NULL;
head->right=NULL;
for(int i=1;i<total_element;i++) {
cout<<"Enter the next node value \n";
int new1;
cin>>new1;
// The insert function gets the head pointer and new value as arguments
head= insert(head,new1);
}
// Start from the head and display all the nodes in the linked list till the node is NULL
struct list *disp=head;
struct list *disp_reverse;
cout <<" The display of the inserted doubly linked list from the first node \n";
// Start from the tail and display all the nodes in the linked list till the head
do{
cout<<"-->"<<disp->value;
disp_reverse = disp;
disp=disp->right;
}while (disp!=NULL);

cout <<" \nThe display of the inserted doubly linked list from the last node \n";
do{
cout<<"-->"<<disp_reverse->value;
disp_reverse=disp_reverse->left;
}while (disp_reverse!=NULL);
cout<<endl;

}
// Here we need to goto the end of the current linked list and create a new element and link there, finally return the head pointer
struct list * insert( struct list *head, int newvalue)
{
struct list *new1=(struct list *) malloc(sizeof(struct list));
struct list *temp = head;
while(temp->right!=NULL)
{
temp=temp->right;
}
new1 ->value=newvalue;
new1->right=NULL;
new1->left = temp;
temp->right=new1;
return head;
};

This is just a beginners code for the simple singly linear linked list .Once we get strong in the linear linked list, its very easy to proceed further in the complex data structures part. To understand this code you just need to know the basics of linked list,pointers,C++.

Here is the source code


/* The simple singly linear linked list program written in C/C++
This creates a head node of linked list first and insert the new nodes to the end of linked list .
You have to define the maximum size of linked list on start run .
*/
#include<iostream.h>

struct list
{
int value;
struct list * next;
};

struct list * insert( struct list *, int);

int main()
{
struct list *head=(struct list *) malloc(sizeof(struct list));
cout <<"Enter the total no of nodes to be present in the linked list\n";
int total_element;
cin >> total_element;
cout<< "Enter the head value\n";
/* Create a head node and assign the value also assign the next node address to NULL (The linked list will end with a node whose next address is NULL */
cin >> head ->value;
head->next=NULL;
for(int i=1;i<total_element;i++) {
cout<<"Enter the next node value \n";
int new1;
cin>>new1;
// The insert function gets the head pointer and new value as arguments
head= insert(head,new1);
}
// Start from the head and display all the nodes in the linked list till the node is NULL
struct list *disp=head;
cout <<" The display of the inserted linked list is \n";
while(disp!=NULL)
{
cout<<"-->"<value;
disp=disp->next;
};
}
// Here we need to goto the end of the current linked list and create a new element and link there, finally return the head pointer
struct list * insert( struct list *head, int newvalue)
{
struct list *new1=(struct list *) malloc(sizeof(struct list));
struct list *temp = head;
while(temp->next!=NULL)
{
temp=temp->next;
}
new1 ->value=newvalue;
new1->next=NULL;
temp->next=new1;
return head;
};

In general you cannot build an efficient data structure without pointers and reference.But the same pointers and reference can make things screw up also, so be careful while handling them.

What is Pointer ?

A pointer is a variable which holds the address of some variable . Obtaining the value of the variable through pointer is called de referencing.

int *p;
int a=20;
p=&a;
cout<<*p;

Null Pointer :

A null pointer has a reserved value, often but not necessarily the value zero, indicating that it refers to no object. Null pointers are used routinely, particularly in C and C++ where the compile-time constant NULL is used (though the integer literal for zero is preferred in C++), to represent conditions such as the lack of a successor to the last element of a linked list.

int *p=NULL;

Note:

An attempt to dereference a null pointer usually causes a run-time error. If this error is left unhandled, the program terminates immediately. In the case of C, execution halts with a segmentation fault because the literal address of NULL is never allocated to a running program. In Java, access to a null reference triggers a NullPointerException, which can be caught by error handling code, but the preferred practice is to ensure that such exceptions never occur.

Funny quote on null pointer : "your worries on useless things is like dereferencing a null pointer and ending up with runtime error or with a segmentation fault."


Double indirection : If a pointer refer to another pointer it is called double indirection. We need to derefer the last pointer twice to get the value of the variable.

int **p1,*p,a=20;
p=&a;
p1=&p;
cout<<**p1;

Wild Pointer : Pointers that have not been initialized (that is, a wild pointer does not have any address assigned to it) and may make a program crash or behave oddly when it is accessed.


Smart pointer : When the general pointer is made to handle automatic garbage collection or bounds checking it is called smart pointer.
Smart pointers try to prevent memory leaks by making the resource deallocation automatic: when the pointer (or the last in a series of pointers) to an object is destroyed, for example because it goes out of scope, the pointed object is destroyed too.


Segmentation Fault : A segmentation fault occurs when a program attempts to access a memory location that it is not allowed to access, or attempts to write to a memory location where only read is allowed, or to overwrite part of the operating system).


Some common code cause segmentation faults are :

int main(void)
{
main();
}

int* ptr = NULL;
*ptr = 1;

Dangling Pointer :
This arise when an object is deleted or deallocated, without modifying the value of the pointer, so that the pointer still points to the memory location of the deallocated memory.

int main()
{
char *dp = NULL;
/* ... */
{
char c;
dp = &c;
} /* c falls out of scope */
/* dp is now a dangling pointer */
}
To handle such case assign the pointer dp to null before coming out of inner loop.

The above things are for those who knows well about pointer, but they are lost in the course of time. More info can be obtained from wiki

What is data structures ?

This question has been one of the commonly asked question in all campus interviews, the best part is it has n number of answers.In simple we call data structure as efficient way of representing(structuring) data in computer memory and using it effectively to handle our needs.

Eventhough every software engineer knows and feels what exactly the data structure is, its always been a little problem to represent it in word. So lets see how Google responds for the search query what is data structure ? and define data structure .

Wikis definition of data structures( it seems quite handy) :
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently .

Webopedia seems wide enough to be general, but not sharp enough :
The term data structure refers to a scheme for organizing related pieces of information.

One more elaborated definition from web.

Data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways. In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms.

Some more common definitions are :

1) Data structure means how the data is organized in memory.There are diferent kind of data structures. Some are used to store the data of same type and some are used to store different types of data.

2) Data structure is a combination of two or more datatype elements .

3) Answers.com provide some detailed definition for data structures . " In constructing a solution to a problem, a data structure must be chosen that allows the data to be operated upon easily in the manner required by the algorithm." .

But all the above definition seems uncomplete !!! People with right definitions are welcome ....