Ø The data item entered first will come out as first item.
Ø Two variables are used to maintain the front position ,
and rear position of the queue .
Ø Insert is a function to insert a data into queue .
Ø Remove is a function to delete / retrieve data from, queue.
Example . Like a QUEUE near a cinema theatre.
Ø A list can also be circular
which is called as circular queue or a circular list.
Ø Instead of using a linear list ,a circular list is prefered
Ø That is items in a circular list are arranged in circular
Ø A circular list does not have any starting or ending point
,so we have an advantage of starting from any point of the list.
Ø A circular QUEQE is as follows..
A circular queue.
Advantages of circular queue :
1. In the case of a circular queue , the last element points back to the first element
of the queue.
So no null pointer is required .
2.Every node as a predecessor , thus there is no special requirement of a ‘first’
CONCEPTS OF LINKED LIST:
v List refers to a set of items
organized sequentially .
v An array is an example of list
v In an array , the sequential organization
is provided implicitly by its index .
v We use the index for accessing
& manipulating array elements .
v One major problem with the array
is that the size of an array must be specified precisely at the beginning of the program .
v As pointed out practical applications
v A completely different way to
represent list to make each item in the list part of a structure that also contains “a link” to the structure
containing the next item as shown in the following figure ,this type of list is called a linked a linked list because it is
a link whose order is given by links from one item to other/next.
v Concepts of linked list ..
v Node: each structure of list is
called as node and it consists of two parts.
· A different
to represent a list is to make each item in part of a structure that also contains a “link” to the structure containing
the next item.
· As shown….
Each structure of the list is called the node and consists of two fields ,one containing
the item, and the other containing the address of the next item in the list .
· A linked list is a collection of structures ordered
not by their physical placement in memory but by their logical links.
· These logical links are stored as part of the data
in the structure itself.
· Example of a structure representation….
· A structure which contain a member field that that
points to the same structure type are called self referential structures.
struct link_list *next;
· The structure may contain more than one item with
different data types.
· However , one of the items must be a pointer of the
Linked list with header node.:
Header node is the node which holds the related
information of linked list .
Number of nodes e. t. c.
Header nodes link part will hold address of first node in the list.
It is a collection of nodes .
A tree is represented as follows ..
Here 4 & 5 are siblings of
2 , similarly 6 & 7 are siblings
Here 2,4,5 are left sub tree.
3,6,7 are right sub tree .
and 4,5,6,7 are descendents of 1.
v A node can have only less than two nodes.
v Strictly binary :-
v It should have not empty left and right sub tree.
This is strictly binary tree
not strictly binary tree
Tree traversal :
Passing through each & every node is called as tree traversal
. There are three types of tree traversal
order traversal &
Preorder traversal :
1.visit root node .
2.visit left sub tree .
3.visit right sub tree .
+AB is pre order traversal for this tree.
Post order traversal:
sub tree .
AB+ is post
sub tree .
3.visit root node .
A+B is in order
2.visit left sub tree .