Linked List

Two of the more common data objects found in computer algorithms are stacks and queues. Both of these objects are special cases of the more general data object, an ordered list.

A stack is an ordered list in which all insertions and deletions are made at one end, called the top. A queue is an ordered list in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front.
Given a stack S=(a[1],a[2],.......a[n])
Then, we say that a1 is the bottommost element and element a[i]) is on top of element a[i-1], 1<i<=n. When viewed as a queue with a[n] as the rear element one says that a[i+1] is behind a[i], 1<i<=n.

The restrictions on a stack imply that if the elements A,B,C,D,E are added to the stack, in that order, then the first element to be removed/deleted must be E. Equivalently we say that the last element to be inserted into the stack will be the first to be removed. For this reason stacks are sometimes referred to as Last In First Out (LIFO) lists. The restrictions on queue imply that the first element which is inserted into the queue will be the first one to be removed. Thus A is the first letter to be removed, and queues are known as First In First Out (FIFO) lists.

We have seen arrays and structures as means of storing data. We have known their limitations. Here we will study linked list as data structures. Linked list which is based on structures, self referential pointers and dynamic memory allocation have a lot of applications. Since here we use dynamic memory allocation, the memory available is the limit for storing data whereas in arrays the memory allocated is the limit.

It can be used in line editors to implement polynomials & to implement space matrices. It is used by operating system for memory allocation or to maintain job queues in multi-user system. Variable length string can be easily represented using linked list.
In this chapter we will see what is a linked list, how it is represented, how are nodes of a list created, & how are they inserted and how they are deleted.

struct tag
{
member 1;
member 2;
…………
…………
struct tag *name;
};