Data Structures : Linear List

Introduction

Data Structure   

A Data Structure is a named group of data of different data types which is stored in a specific way and can be processed as a single unit. A data structure has well-defined operations, behavior and properties. 

Different Data structures 

Data structures are very important in a computer system, as these not only allow the users to combine various data types in a group but also allow processing of the group as a single unit thereby making things much simpler and easier. 

The data structures can be classified into two  types:

 1. Simple Data Structures : These data structures are normally built from primitive data types like integers, characters, boolean etc. For example:- Arrays, Linear lists.

2. Compound Data Structures : Simple data structures can be used in various ways to form more complex structures called compound data structures. Compound data structures are classified into following two types:-

• Linear Data Structures: These data structures are single level data structures. A dat structure is said to be linear if its elements form a sequence . For example:- Stack, Queue, Linked lists.
• Non-linear Data Structures: These are multilevel data structures. For example:- Tree.

Linear Lists 

A linear data structure is that whose elements form a sequence. When elements of linear structures are homogeneous and are represented in memory by means of sequential memory locations, these linear structure are called arrays. 

Linear list or Arrays are one of the simplest data structures and are very easy to traverse, search, sort etc. An array stores a list of finite number (n) of homogeneous data elements (i.e. the data elements of the same type). The number n is called length or size or range of a linear list. 

 When upper bound and lower bound of a linear list are given, its size is calculated as follows:

Linear list size(length) = UB - LB +1                         ( UB- upper bound, LB- lower bound)

For instance, if a linear list or an array has elements numbered as -7,-6,-5....0,1,2,.....15, then its UB is 15 and LB is -7 and array length is 

= 15 - (-7) + 1

= 15 + 7 + 1 =23

Linear List Data Structure

Searching in a Linear List

There are many different searching algorithms: linear search and binary search. 

Linear Search 

In  linear search, each element of the array/linear list is compared with the given Item to be searched for, one by one. This method, which traverses the array/linear list sequentially to locate the given  Item  is called linear search or sequential search .

Algorithm :-

Linear search in linear list -

#Initialise the counter by assigning lower bound value of the linear list

Step 1. Set ctr = L            # L (Lower bound) is 0 (zero)

            # Now search for the ITEM

Step 2. Repeat steps 3 through 4 until ctr > U  

             # U(upper bound) is size-1

Step 3. IF AR[ctr] == ITEM then

            {        print("Search Successful")

                      print(ctr, " is the location of ",ITEM)

                      break               # go out of loop

            }

Step 4. ctr = ctr+1

            # End of Repeat

Step 5. IF ctr> U then 

                    print("Search Unsuccessful !")

Step 6. End

Explaination: The above algorithm searches for ITEM in linear list AR with lower bound L and upper bound U. As soon as the search is successful, it jumps out of the loop (break statement), otherwise continues till the last element. 

Binary Search

This popular search technique searches the given ITEM in minimum possible comparisons. The binary search requires the array, to be scanned, must be sorted in any order. In binary search, the ITEM is searched for in smaller segment after every stage. For the first stage, the segment contains the entire array.

To search for ITEM in a sorted array, the ITEM is compared with middle element of the segment (i.e., in the entire array for the first time). If the ITEM is more than the middle element, latter part of the segment becomes new segment to be scanned; if the ITEM is less than the middle element, former part of the segment becomes new segment(s) until either the ITEM is found (search successful) or the segment is reduced to the single element and still the ITEM is not found (search unsuccessful). 

Algorithm :-

Binary search in Linear List

Case I : Array AR[L : U] is sorted in ascending order

#Initialise segment variables

1. Set beg = L , last = U        # L is 0 and U is size-1

2. while beg <= last, perform  steps 3 to 6  

3.        mid = INT((beg+last)/2)

4.        if AR[mid] == ITEM then

                print("Search successful")

                print(ITEM," found at ", mid)

                break                # go out of the loop 

5.        if AR[mid] < ITEM then

                beg = mid+1

6.        if AR[mid] > ITEM then

                last = mid-1

7.        if beg  != last

                print("Unsuccessful Search")

8. END.

Case II : Array AR[L : U] is sorted in descending order

#Initialize 

:

if AR[mid] == ITEM then

:

if AR[mid] < ITEM then

        last = mid - 1

if AR[mid] > ITEM then 

        beg = mid + 1

:       # Rest is similar to the algorithm in case I.

Insertion in a Linear List 

Insertion of new element in array can be done in two ways:
(i) if the array is unordered, the new element is inserted at the end of the array, 
(ii) if the array is sorted then new element is added at appropriate position without altering the order and to achieve this, rest of the elements are shifted. 
Note: if array is already full, then insertion of an element into it results into OVERFLOW.

Deletion of an Element from  a Sorted Linear List

The element to be deleted is first searched for in the array using one of the search techniques i.e., either linear search and binary search. If the search is successful, the element is removed and rest of the elements are shifted so as to keep the order of array undisturbed. 

Algorithm:-

Deletion in Linear List

# Considering that ITEM's search in array AR is successful at location pos

Case I : Shifting upwards (or in left side)

# Initialize counter 

1. ctr = pos 

2. while ctr < U perform steps 3 and 4

3.        AR[ctr] = AR[ctr + 1]

4.        ctr = ctr + 1

# End of while

Case II : Shifting downwards (or in left side)

1. ctr = pos 

2. while ctr > 1 perform steps 3 and 4

3.        AR[ctr] = AR[ctr - 1]

4.        ctr = ctr - 1

# End of while

👉 Python provides a remove() method that itself takes care of shifting of elements.

-----------------------------------------------------------

Resources:- 

1. Computer Science with Python , Sumita Arora (Dhanpat Rai & Co.)