Sorted Linked Lists and Sorted Arrays Java Example

If there is requirement for an application to maintain the data in sorted order within the list, then you need to use sorted linked lists. In this tutorial you will see how to implement sorted linked list using Java.

In a sorted list, the items are sorted by key value. You often delete the smallest or largest item in the list. But you can also use find() and delete() methods to search and delete specific links in the list.

Sorted Linked Lists Vs Sorted Arrays

In general you use sorted list in many situations where you use sorted array. The advantage of sorted list over sorted array is speed of insertion and the list can expand and fill available memory, while an array is limited to a fixed size.

Sorted list is difficult to implement when compared to sorted array.

Application: When to use Sorted Linked List ?

If an application frequently accesses the smallest item from the list, and fast insertion is not critical then Sorted Linked List is the effective choice

Sorted Linked List Example

In the main() method we insert two items with key values 30 and 60. Then we insert four  more items 20, 10, 40 and 50. These values are inserted at the appropriate places so that the end list is sorted.

Finally, we delete one item, to show that the items will always be deleted from the beginning of the list. After each change, the list is displayed. Here is the output from SortedLinkedListExample.java

Output

Efficiency of sorted linked list

Sorted Linked List requires O(N) comparisons or O(N/2) comparisons on average for insertion and deletion, since the appropriate location must be found by traversing through the list.

If the item to be inserted or deleted is in/at the beginning of the list then it requires O(1) time.

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of