Page 2 - DATA STRUCTURE-LISTS

A QUEUE is a container of objects (a linear collection) that are inserted and removed
according to the first-in first-out (FIFO) principle. In the queue only two operations are
allowed enqueue and dequeue. Enqueue(insert) means to insert an item into the back/rear
of the queue, dequeue(delete) means removing the front item. An excellent example of a
queue is a line of students. The picture demonstrates the FIFO access. New additions to a
line made to the back of the queue, while removal happens in the front.

Linked List
One disadvantage of using arrays to store data is that arrays are static structures and
therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive
to maintain new insertions and deletions. Linked Lists addresses some of the limitations of
arrays. A linked list is a linear data structure where each element is a separate object.

Each element (we will call it a node) of a list is comprising of two items - the data and a
reference/pointer to the next node. The last node has a reference to null. The entry point
into a linked list is called the head of the list. It should be noted that head is not a separate
node, but the reference to the first node. If the list is empty then the head is a null
reference. A linked list is a dynamic data structure. The number of nodes in a list is not fixed
and can grow and shrink on demand. Any application which has to deal with an unknown
number of objects will need to use a linked list.

One disadvantage of a linked list against an array is that it does not allow direct access to
the individual elements. If you want to access a particular item then you have to start at the
head and follow the references until you get to that item.

Another disadvantage is that a linked list uses more memory compare with an array - we
extra 4 bytes (on 32-bit CPU) to store a reference to the next node.

Trees

• A tree can be defined as finite set of data items (nodes).
• Tree is non-linear type of data structure in which data items are arranged or stored
in a sorted sequence.
• Tree represent the hierarchical relationship between various elements.
• A tree can be defined as finite set of data items (nodes).
• Tree is non-linear type of data structure in which data items are arranged or stored
in a sorted sequence.
• Tree represent the hierarchical relationship between various elements.
• The tree structure organizes the data into branches, which related the information.