{"id":40,"date":"2018-07-18T08:39:52","date_gmt":"2018-07-18T08:39:52","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=40"},"modified":"2018-12-12T07:06:50","modified_gmt":"2018-12-12T07:06:50","slug":"array-implementation-of-list-adt","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/array-implementation-of-list-adt\/","title":{"rendered":"Array Implementation of List ADT"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures.This is the third module of the paper and we will be talking about the array implementation of List ADT.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022 To discuss the different implementations of List ADT\r\n\r\n\u2022 To understand the array and array based vector implementation of Lists\r\n\r\n\u2022 To outline the implementation of Lists using dynamic arrays\r\n\r\n \r\n\r\n3.1<\/strong>\u00a0Implementation of an ADT<\/strong>\r\n\r\n \r\n

Before we go on to describe the implementation of a particular type of ADT let us discuss the general issues in implementing an ADT. The first step in the implementation is the choiceof the data structure to represent the ADT\u2019s data. This choice of the data structure depends mainly on details of the ADT\u2019s operations and the context in which the operations will be used. You must remember that the implementation details should be hidden behind a wall of ADT operations. In other words a program would only be able to access the data structure using the ADT operations.<\/p>\r\n \r\n

The first step in implementing an ADT is choosing a data structure<\/strong>such as arrays, records, etc. to represent the ADT. Each operation associated with the ADT is implemented by one or more subroutines. Two standard implementations for the list ADT that we will be discussing in this paper are array-based implementation and linked list based implementation. In this module we will be discussing the array based implementation of the List ADT.<\/p>\r\n \r\n\r\n3.2 Static Implementation of ADT List<\/strong>\r\n\r\n \r\n

The simplest method to implement a List ADT is to use an array that is a\u201clinear list\u201d or a \u201ccontiguous list\u201d where elements are stored in contiguous array positions. The implementation specifies an array of a particular maximum length, and all storage is allocated before run-time. It is a sequence of n-elements where the items in the array are stored with the index of the array related to the position of the item in the list.<\/p>\r\n \r\n

In array implementation,elements are stored in contiguous array positions (Figure 3.1). An array is a viable choice for storing list elements when the elements are sequential,\u00a0because it is a commonly available data type and in general algorithm development is easy.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n

\"\"<\/p>\r\n \r\n

3.2.1List Implementation using arrays<\/strong><\/p>\r\n \r\n

In order to implement lists using arrays we need an array for storing entries \u2013 listArray[0,1,2\u2026..m], <\/strong>a variable curr<\/strong>to keep track of the number of array elements currently assigned to the list,<\/strong> thenumber of items in the list, or current size of the list size<\/strong>and a variable to record the maximum length of the array, and therefore of the list \u2013 maxsize as shown in Figure 3.2.<\/strong><\/p>\r\n \r\n\r\n\"\"\r\n

Fix one end of the list at index 0 and elements will be shiftedas needed<\/em><\/strong> when an element is added or removed. Therefore insert and delete operations will take O(n). That is if we want to insert at position 0 (insert as first element),this requires first pushing the entire array to the right one spot to make room for the new element. Similarly deleting the element at position 0requires shifting all the elements in the list left one spot.<\/p>\r\n \r\n

One of the important operations associated with lists is the initialization. In this case we need to first declare the array of list items with maximum number of items say n. This then requires an estimate of the maximum size of the list. Once we decide the size, then we `initialize the list with number of items set at 0.<\/p>\r\n \r\n\r\n3.2.1.1 Finding First Element<\/strong>\r\n\r\n \r\n

Here we define finding the first element by first calling a Boolean function \u2013 IsEmpty list. If IsEmpty listis true that is if the list is empty then there is no question of finding an element and finding the first element will return a value that is not a valid entry of the list However if IsEmpty listis false that is the list is not empty the element at the first location position (0) is returned.<\/p>\r\n\r\n<\/div>\r\n\u00a0 \u00a03.2.1.2 Insertion<\/strong>\r\n

\r\n\r\n \r\n

What happens if you want to insert an item at a specified position in an existing array?The item originally at the given index must be moved right one position, and all the items after that index must be shifted right<\/em><\/strong>(Figure 3.3).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Let us consider a specific case of Insert operation. Insert (3, K, List) In this case, 3 is the index or the point of Insertion, K is the element to be inserted & List is the list in which insertion is to be done ( Figure 3.4 (a) & Figure 3.4 (b)).<\/p>\r\n \r\n\r\n\"\"\r\n

Let us see the steps in the insertion with the example given in Figure 3.4(a) & Figure 3.4 (b). Let us assume initially that the original list contains 7 elements (that is Size =7) namely A at array location 0, X at location 1 and so on and finally Rat location 6. The steps involved are as follows:<\/p>\r\n\r\n<\/div>\r\n

\r\n

Step 1: First check whether there is place to add the new element \u2013 in other words whether the array is full. If so indicate error<\/p>\r\n \r\n

size = maxsize \u2013 Then error<\/strong><\/p>\r\n \r\n

Step 2: Now we need to make room for the new element at the index position 3. We need to shift elements from index to curr (curr position of last element of list) one position to the right.<\/p>\r\n \r\n\r\nLoop till curr<\/strong>\r\n\r\nItems[index+1] =><\/strong>tems[index]<\/strong>\r\n\r\n \r\n\r\nStep 3: Write the element into the gap created by shifting the elements to the right\r\n\r\nItems[index] <\/strong>=><\/strong> K<\/strong>\r\n\r\n \r\n\r\nStep 4: Update size and curr position of the list\r\n\r\nsize=><\/strong> size +1; curr<\/strong>=><\/strong>curr +1<\/strong>\r\n\r\n \r\n\r\n3.2.2.2 Deletion from Lists<\/strong>\r\n\r\n \r\n

What happens if you want to remove an item from a specified position in an existing array? There are two ways in which this can be done:<\/p>\r\n \r\n

\u2013\u00a0\u00a0 Leave gaps<\/em><\/strong> in the array, i.e. indices that contain no elements, which in practice, means that the array element has to be given a special value to indicate that it is \u201cempty\u201d, or<\/p>\r\n \r\n

\u2013 All the items after the (removed item\u2019s) index must be shifted left<\/em><\/strong>similar to what we did when we wanted to insert \u2013 only for insertion we shifted right.<\/p>\r\n \r\n

\u2013 Delete (3, List)<\/strong>. In this case, 3 is the index or the point of Deletion& List is the list from which deletion is to be done (Figure 3.5 (a) & Figure 3.5 (b)).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n

Let us see the steps in the deletion with the example given in Figure 3.5(a) & Figure 3.5(b). Let us assume initially that the original list contains 7 elements (that is Size =7) namely A at array location 0, X at location 1 and so on and finally R at location 6. The steps involved are as follows:<\/p>\r\n \r\n

Step 1: First check whether the list is empty that is whether there are elements in the list.<\/p>\r\nWe cannot perform deletion from an empty list.\r\n\r\nsize=0 Then error<\/strong>\r\n\r\n \r\n

Step 2: Now we need to shift elements from index position 4 to the left so that an empty locationis created due to the deletion at location 3 will be filled by elements to the left. We need to shift elements from index (i) to curr( that is the curr position of last element of list) one position to the left.<\/p>\r\n \r\n\r\nLoop till curr<\/strong>\r\n\r\nItems[index] <\/strong>=><\/strong> items[index+1]<\/strong>\r\n\r\n \r\n\r\nStep 4: Update size and curr position of the list\r\n\r\nsize=><\/strong>size-1; curr<\/strong>=><\/strong>curr-1<\/strong>\r\n\r\n \r\n\r\n3.2 Advantages of Array-Based Implementation of Lists<\/strong>\r\n\r\n \r\n\r\nSome of the major advantages of using array implementation of lists are:\r\n