Inserting an Element into a Sorted List in java

Although binarySearch() is used to locate existent elements, it can also be used to determine the insert index for non-existent elements. Specifically, the insertion index is computed in the following way: insert-index = (-return-value)-1

// Create a list with an ordered list of items
List sortedList = new LinkedList();

sortedList.addAll(Arrays.asList(new String[]{"ant", "bat", "cat", "dog"}));

// Search for the non-existent item
int index = Collections.binarySearch(sortedList, "cow"); // -4

// Add the non-existent item to the list
if (index < 0) { sortedList.add(-index-1, "cow"); }

Finding an Element in a Sorted List in Java

 // Create a list with an ordered list of strings
List sortedList = new LinkedList();
sortedList.addAll(Arrays.asList(new String[]{"ant", "bat", "cat", "dog"}));
// Search for the word "cat"

int index = Collections.binarySearch(sortedList, "cat"); // 2

// Search for a non-existent element
index = Collections.binarySearch(sortedList, "cow"); // -4
A negative return value indicates that the element is not in the list. However, the actual return value can be used to determine where that non-existent element should be inserted in the list if that were desired; see Inserting an Element into a Sorted List.

ArrayList example 2

// Create the list
List list = new LinkedList(); // Doubly-linked list
list = new ArrayList(); // List implemented as growable array
// Append an element to the list

list.add("a"); 

// Insert an element at the head of the list

list.add(0, "b"); 

// Get the number of elements in the list

int size = list.size(); // 2 

// Retrieving the element at the end of the list

Object element = list.get(list.size()-1); // a

// Retrieving the element at the head of the

list element = list.get(0); // b

// Remove the first occurrence of an element boolean
b = list.remove("b"); // true
b = list.remove("b"); // false // Remove the element at a particular index element = list.remove(0); // a