Data Structures In Java - Linear Array

Ankur Soni
7 years ago
7.6k
0
1
Article

Data structure means organizing the data by using models in the 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, where as 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 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 access all these 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]" and 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 and LB referred 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 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 list 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

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 element

Here, LA 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;
// elements before inserting new elements
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.