Adt of lists

Data structure

1. ADT OF LISTS DATA STRUCTURE NADAR SARASWATHI COLLEGE OF ARTS AND SCIENCE,THENI. B.NIVEGEETHA(I-MSC(CS))

2. ADT(ABSTRACT DATA TYPES) Abstract  Data  type ( ADT ) is a type (or class) for objects whose behavior is defined by a set of value and a set of operations. We can think of  ADT as a black box which hides the inner  structure  and design of the  data  type.

3. LIST ADT We all have an intuitive understanding of what we mean by a "list". We want to turn this intuitive understanding into a concrete data structure with implementations for its operations. The most important concept related to lists is that of  position . In other words, we perceive that there is a first element in the list, a second element, and so on. So, define a  list to be a finite, ordered sequence of data items known as  elements . This is close to the mathematical concept of a  sequence .

4. GENERAL PROGRAM public interface List { // List class ADT // Remove all contents from the list, so it is once again empty public void clear(); // Insert "it" at the current location // The client must ensure that the list's capacity is not exceeded public boolean insert(Object it); // Append "it" at the end of the list // The client must ensure that the list's capacity is not Exceeded public boolean append(Object it);

5. // Remove and return the current element public Object remove(); // Set the current position to the start of the list public void moveToStart(); // Set the current position to the end of the list public void moveToEnd(); // Move the current position one step left, no change if already at beginning public void prev(); // Move the current position one step right, no change if already at end public void next(); // Return the number of elements in the list public int length(); // Return the position of the current element public int currPos(); }

6. LINKED LIST A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

7. WHY LINKED LISTS? Arrays can be used to store linear data of similar types, but arrays have following limitations. 1)  The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of them. 2)  Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

8. INSERTING AN ELEMENT IN LINKED LISTS The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node.

9. INSERTION PROGRAM void push( struct Node** head ref, int new data) {     /* 1. allocate node */      struct Node* new node = ( struct Node*) malloc ( sizeof ( struct Node));        /* 2. put in the data  */     new node->data  = new data;        /* 3. Make next of new node as head */     new node->next = (*head ref);        /* 4. move the head to point to the new node */     (*head ref)    = new node; }

10. DELETING AN ELEMENT IN LINKED LISTS To delete a node from linked list, we need to do following steps. 1) Find previous node of the node to be deleted. 2) Changed next of previous node. 3) Free memory for the node to be deleted.

11. DELETION PROGRAM void ListDelete ( nodeT ** listP , elementT value) { nodeT * currP , * prevP ; /* For 1st node, indicate there is no previous.*/ prevP = NULL; /* * Visit each node, maintaining a pointer to * the previous node we just visited. */ for ( currP = * listP ; currP != NULL; prevP = currP , currP = currP >next) { if ( currP ->element == value) { /* Found it. */ if ( prevP == NULL) { /* Fix beginning pointer. */ listP = currP ->next; }

12. DELETION Else { /* * Fix previous node's next to * skip over the removed node. */ prevP ->next = currP ->next; } /* Deallocate the node. */ free( currP ); /* Done searching. */ return; } } }

13. ARRAY BASED IMPLEMENTATION #include< stdio.h > #include< conio.h > #define MAX 10 void create(); void insert(); void deletion(); void search(); void display(); int a,b [20], n, p, e, f, i , pos; void main() { // clrscr (); int ch ; char g='y'; do { printf ("\n main Menu"); printf ("\n 1.Create \n 2.Delete \n 3.Search \n 4.Insert \n 5.Display\n 6.Exit \n"); printf ("\n Enter your Choice"); scanf ("%d", & ch );

14. void create() { printf ("\n Enter the number of nodes"); scanf ("%d", &n); for( i =0;i< n;i ++) { printf ("\n Enter the  Element:",i+1); scanf ("%d", &b[ i ]); } } void deletion() { printf ("\n Enter the position u want to delete::"); scanf ("%d", &pos); if(pos>=n) { printf ("\n Invalid Location::"); } else { for( i =pos+1;i< n;i ++) { b[i-1]=b[ i ]; } n--; } printf ("\n The Elements after deletion"); for( i =0;i< n;i ++) { printf ("\ t%d ", b[ i ]); } }

15. void search() { printf ("\n Enter the Element to be searched:"); scanf ("%d", &e); for( i =0;i< n;i ++) { if(b[ i ]==e) { printf ("Value is in the %d Position", i ); } else { printf ("Value %d is not in the list::", e); continue; } } } void insert() { printf ("\n Enter the position u need to insert::"); scanf ("%d", &pos); if(pos>=n)  {   printf ("\n invalid Location::");  }  else  {  for( i =MAX-1;i>=pos-1;i--)  {  b[i+1]=b[ i ];  }

16. PROGRAM printf ("\n Enter the element to insert::\n");   scanf ("% d",&p );  b[pos]=p;  n++;  }   printf ("\n The list after insertion::\n"); display(); } void display() { printf ("\n The Elements of The list ADT are:"); for( i =0;i< n;i ++) { printf ("\n\ n%d ", b[ i ]); } }

17. ARRAY IN LIST ADT In computer science, an  array data structure , or simply an  array , is a data structure consisting of a collection of  elements  (values or variables), each identified by at least one  array index  or  key . An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.The simplest type of data structure is a linear array, also called one-dimensional array.

18. INSERTIND AND DELETING AN ELEMENT IN ARRAY

19. APPLICATIONS OF LIST ADT Lists can be used to implement Stacks , Queues. Lists can also be used to implement Graphs. (Adjacency list representation of Graph). Implementing Hash Tables :- Each Bucket of the hash table can itself be a linked list. (Open chain hashing). Undo functionality in Photoshop or Word . list of states. A polynomial can be represented in an array or in a linked list by simply storing the coefficient and exponent of each term. However, for any polynomial operation , such as addition or multiplication of polynomials , linked list representation is more easier to deal with. lists are useful for dynamic memory allocation. The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running.

20. THE END