Data structure except the reported one

Linked List

is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order.

How it access

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).

Actual structuring

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.


How is data kept

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.