What is LIST ADT?

If you want to know about ADT, please have a look at What is Abstract Date Type?

What is List???

    a number of connected items or names written or printed consecutively, typically one below the other.

  List play a important role in our daily life.

 List may be Prayer List, Check list, Home work List, Shopping List, Friends list, even somebody have their own enemy list but i will not encourage enemy list....

Let us assume, each row as one item. If you see every list in detail, you can get something in common.I also listed those common things below.

   1.  Item
   2.  Link between each Item (Sl. No. Continuity)
   3. Structure of each row.(Each row have same fields for each list)
   4. All item is in same material(Paper/Excel/Application/Computer Memory/etc.,)

How can I prepare List?

 1. Decide the material

        First we have to choose the material(Paper/Excel/Application/Computer Memory/etc.,) in which we are going to prepare our list.

2. Form the structure

        Second, We have to form the structure of list i.e., How to organize the multiple item in a list?. We have to decide that what are the fields/headers(such as Sl. No., Item, Quantity, Amount) we need for our list.

3. Enter the details

        And finally we can enter our item/row in our list.

What are the operation we can do with our list?

1. Add

    We can add new item/row in our list at first or at last or at any position.

2. Edit

    If we entered wrong value for a item/row, don't worry we can edit/enter the right value at any point of time.

3.Search

   If we want to search for a value in a big List, We can use CTRL+F to search and we can find the value which we need or position of row/item which contains the value which we need.

What is LIST ADT????

         A List is a dynamic, ordered tuple of homogeneous elements.

List Will be in the form: 

A₁, A₂, A₃, .... A_n

First Element of the List: 

A₁

Last Element of the List: 

A_n

ith  Element of the List: 

A_{i ,}  

Position of Element A_i : 

i , Position ranges from 0 to N

Size of the List: N

Empty List: If Size of the list is Zero (i.e N=0), it is Empty List.

Precedes and Succeeds: For any list except empty list, we say that Ai+1  follows (or succeeds) A_i (i<N) and that A_i-1  precedes Ai (i>1)

LIST Operations:

L==> List
x==>Element
p==>Position

1. Insert (x,p,L)

   Insert x at position p in list L

   If p = END(L), insert x at the end

   If L does not have position p, result is undefined

2. Locate(x,L) 

   returns position of x on L

   returns END(L) if x does not appear

3. Retrieve (p, L)

   returns element at position p on L

   undefined if p does not exist or p = END(L)

4. Delete (p, L) 

   delete element at position p in L

   undefined if p = END(L) or does not exist

5. Next (p, L)

   returns the position immediately following position p
6. Prev (p, L)

   returns the position previous to p
7. Makenull (L)

   causes L to become an empty list and returns position END(L)
8. First (L)

   returns the first position on L
9. Printlist (L)
   print the elements of L in order of occurrence

References:
http://www.csee.umbc.edu/courses/undergraduate/341/spring00/frey/Lectures/Lists/List1.html
http://lcm.csa.iisc.ernet.in/dsa/node15.html

Goto Data Structure Concepts

Goto CSR Initiative