Data Structures In Java - Linear Array

Introduction 

 

Data structure means, organizing the data by using models, in computer memory.  We can represent the data in two ways - linear data structure and non-linear data structure. A linear data structure, that represents a relationship between elements by successive memory location, is known as an array.  Whereas, a linear data structure that represents a relationship between elements, by a pointer and link, is known as a linked list.  Common non-linear data structures are a tree, graph, etc.

 

Linear Array (One dimension array)

 

A linear array, is a list of finite numbers of elements stored in the memory.  In a linear array, we can store only homogeneous data elements.  Elements of the array form a sequence or linear list, that can have the same type of data.

 

Each element of the array, is referred by an index set.  And, the total number of elements in the array list, is the length of an array.  We can accessthese elements with the help of the index set.

 

For example, consider an array of employee names with the index set from 0 to 7, which contains 8 elements as shown in fig:

 

 

 

Now, if we want to retrieve the name 'Alex' from the given array, we can do so by calling "employees [3]".  It gives the element stored in that location, that is 'Alex', and so on.

  

We can calculate the length, or a total number of elements, of a linear array (LA), by the given formula:

 

Length (LA)=UB-LB+1

 

Here, UB refers to the upper bound, the largest index set of the given array list.  LB refers to the lower bound, smallest index set of the given array list.

 

For example, we have an array of employees, in which lower bound is 153 and the upper bound is 234, so we can calculate the total number of elements in the list, by giving the formula.

 

234-153+1=82

 

We can perform various operations on a linear array:

• Traversing-  processing each element of the array list.
• Inserting- adding new elements in the array list.
• Deleting- removing an element from the array list.
• Sorting- arranging the elements of the list in some sorting order.
• Merging- combining the elements of two array lists in a single array list.

Note

 

Basically, an array is recommended when we have to perform operations, like retrieving the data, or reading the data.  But, for the operations like insertion and deletion, array is not recommended.

 

Traversing Linear Array

 

We can process each element of an array with the help of an index set.

 

Consider a Linear Array(LA) list given with lower bound(LB) and upper bound(UB) that contains 'n' number of elements.  We can traverse the list with the given algorithm.

 

ALGORITHM 

(initialized counter) K = LB
Repeat
while k <= UB
Process LA[k]
K = k + 1(End of loop)
Exit

 

Program

public class Traverse {
 public static void main(String args[]) {
  String[] employee = {
   "john",
   "alex",
   "rone",
   "mike",
   "zeny",
   "crist"
  };
  for (int k = 0; k < employee.length; k++) {
   System.out.println(employee[k]);
  }
 }
}

Output

 

 

 

Inserting and Deleting in Array

 

Array insertion, of an element at the end of the list, is quite simple.  We can do so by providing the unallocated space to the new element.  On the other hand, if we need to insert an element in the middle of an array, lots of internal shifting is required to insert the new element.  I.e. half of the elements must be moved downward, to the new location, to enter the new element.

 

Similarly, deletion of the element from the end of the array, is quite simple.   But, if we need to delete an element from the middle of the array, then on average, half of the elements must be moved upward, in order to fill the blank space, after deleting the element from the specified location.

 

Algorithm for insertion of an element

 

Here, LA is a linear array with n number of elements, where K is a positive integer, i.e. K<=n.  This algorithm inserts an element item into the Kth position.

(Initialized counter) J = n
Repeat step 3 & 4
while j >= k[Move downward] set LA[J + 1] = LA[J]
 [Decrement counter] set j = j - 1;
End of step 2[Insert element] set LA[k] = ITEM[Reset n] set n = n + 1
Exit

 

Program

public class InsertElement {
 public static void main(String args[]) {
  int n = 6;
  String name[] = new String[n];
  name[0] = "mike";
  name[1] = "rick";
  name[2] = "max";
  name[3] = "christ";
  name[4] = "larry";
  String new_item = "jack";
  int k = 2;
  int j = n - 1;
  System.out.println("elements before inserting new elements");
  for (int i = 0; i < n; i++) {
   System.out.println("position" + "(" + i + ") " + name[i]);
  }
  System.out.println("elements after inserting new elements");
  while (j >= k) {
   name[j] = name[j - 1];
   j = j - 1;
  }
  name[k] = new_item;
  for (int i = 0; i < n; i++) {
   System.out.println("position" + "(" + i + ") " + name[i]);
  }
 }
}

Output

 

 

 

Algorithm for deleting an element

 

Here, LA is a linear array with 'n' number of elements and K is a positive integer number, such that k<=N.  This algorithm removes the element from the Kth position. 

Set Item = LA[k]
Repeat
for J = k to N - 1[move J + 1 st element upward] LA[J] = LA[J + 1]
 [End of step 2]
 [Reset the number of element] N = N - 1
Exit

 

Program

public class Deleting {
 public static void main(String args[]) {
  int n = 5;
  String name[] = new String[n];
  name[0] = "mike";
  name[1] = "rick";
  name[2] = "max";
  name[3] = "christ";
  name[4] = "larry";
  String del_item;
  int k = 2;
  System.out.println("elements before inserting new elements");
  for (int i = 0; i < n; i++) {
   System.out.println("position" + "(" + i + ") " + name[i]);
  }
  System.out.println("elements after deleting the elements");
  del_item = name[k];
  for (int j = k; j < n - 1; j++) {
   name[j] = name[j + 1];
  }
  n = n - 1;
  for (int i = 0; i < n; i++) {
   System.out.println("position" + "(" + i + ") " + name[i]);
  }
 }
}

Output