Abstract data type ADT

1. What is meant by an Abstract data type (ADT)?
          An Abstract data type (ADT) is a set of operations. Abstract data types are
    Mathematical abstractions.
    Example:
        Object such as set, list, and graphs along their operations can be viewed as 
    ADT.
    Union, intersection, size, complement and find are the various operations of ADT.

2.What does List ADT mean?
General list: A1, A2, A3,…………..An

• A1-> first element
• An-> last element
• In general Ai is an element in a list I
• Ai-> current element position
• Ai+1-> predecessor

3. What are the various operations done under list ADT?

• Insert –element insertion 

                                                 Ex: Insert (x, 3)                       
                                                             Insert the element X in 3rd position

• Delete-Element deletion

                  Ex: Delete (52)
                              Deletes the element

• Find-searching an element in the list

                 Ex: find (34)
                            Finds the element
* Next             -Successor
* Previous       -predecessor
* Print list       -Print all the elements in the list
*Make empty  - Emptying the list

4.What is the basic idea behind ADT?
          The various operation of ADT such as union, intersection, sizes etc. are  
    Written once in the program and any other part of the program that needs to
     Perform an operation on ADT can do so by calling the appropriate function.

5. What are advantages in the array implementation of list?
           The advantages in the array implementation of list are,

• Print – list operation can be carried out at the linear time.
• Find – Kth operation takes a constant time.

6.What are the disadvantages in array implementation of stacks?
       Disadvantages in array implementation of stacks are,
a. Array implementation requires the maximum size of the list in prior, which sometimes becomes an overestimate and which wastages considerable space when we use lists of unknown size.
b .bisection and deletion operation are expensive

• To insert a element at position 0, we need to push the entire array down one spot to make room.
• To delete a element requires shifting all the elements in the list up one.
• Hence the process is very slow.

  7. What is a linked list?
                 Linked list is a kind of series of data structure, which are not necessarily
       adjacent in memory. Each structure contains the element and a pointer to a
       record containing its successor.
8. How do you insert an element in the array?

A (0)     A (1)      A (2)      A (3)      A (4)………………………………………….A (50)

To insert the element x in the array at position ‘0’.

Step 1: Create a place at position zero by pushing all other data.

  A (0)   A (1)      A (2)      A (3)      A (4)       A (5)………………………………. A (50)

Step 2: Insert the element x,

A (0)    A (1)       A (2)      A (3)       A (4)      A (5)………………………………..A (50)

9. How do you delete an element from the array?
                         Consider the list

A (0) A (1) A (2) A (3) A (4) A (5) A (6)………………………………..A (50)

To delete ‘L’

    Step 1: Find the position of the element.
   Step 2: Delete the data and push all other data up

A (0) A (1) A (2) A (3) A (4) A (5)……………………………………….A (50)

10.What is doubly liked list?
          In a simple linked list , there will be one pointer named as ‘NEXT POINTER’ to point the next element /data location, where as in a doubly linked list, there will be two pointers one to point the next and other to point the previous element location

11.Define double circularly linked list.
       In doubly circular linked list, if the last node or pointer of the list, points to the first element of the list, then it is a circularly linked list
12. List three examples that use linked list.
           Linked list are used by,

• Polynomial ADT
• Radix sort
• Multi lists.

13. What is the cursor implementation of linked list? 

• Data is stored in a collection of objects; each object contains the data and a pointer to the next object.
• A new object that can be obtained from the system is global memory by a call to new and released by a call to delete

14. What are the applications of stack?
Stack can be applied in different situations. Some of the examples where is applied are explained below.

• Infix, Prefix & Postfix expression.
• Conversion of infix to postfix expression.
• Evaluating postfix expression.
• Balancing symbols.
• Tower of Hanoi.

20. What is meant by list ADT?
        List ADT is a sequential storage structure, general list of the form a1, a2, a3…an and the size of the list is ‘n’. any element in the list at the position  ‘i’ is defined to be ai.ai+1 is the successor of ai and ai-1 is the predecessor of ai.

21. What are the different ways to implement the list?
             Ways to implement the lists are,

• Simple array implementation of list
• Linked list implementation of list

22. What is a pointer?
             Pointer is a variable, which stores the address of the next element in the list. Pointer is basically a number.