Java programming fundamentals: Datastructures and algorithms in Java

Java 101: Datastructures and algorithms in Java, Part 5

Doubly linked and circular linked list and their algorithms in Java

1 2 Page 2
Page 2 of 2

In summary, linked lists are most appropriate when dealing with dynamic data, meaning programs where insertions and deletions are frequent. In contrast, arrays are most appropriate for programs where data is static, meaning it's rare to insert or delete new data items. (Recall that if you run out of room when adding data items to an array, you must create a larger array, copy the original array's data items to the larger array, and dispose of the original. This takes time, which affects performance -- especially when done repeatedly.)

You might think that merging a singly linked list with a one-dimensional array to access nodes via array indexes would accomplish nothing. You would waste memory because you need array elements plus nodes, and you would waste time because you need to move the array's data items whenever you insert or delete a node. In fact, it can be beneficial to integrate an array with a linked list to create a hybrid! While it's out of the scope of this series, the hash table is a great example of array/linked list cooperation.

In conclusion

This series has introduced the fundamentals of datastructures and algorithms. I've focused on two datastructure categories, Java arrays and linked lists, which are the basis of more complex datastructures such as stacks, queues, trees, graphs, dictionaries/maps, and sets. I encourage you to keep exploring and learning about datastructures, and algorithms, especially some of the newer ones such as Quick Sort and Depth First Search/Breadth First Search, used for traversing graphs. The Java Collections Framework also includes many useful datastructures and algorithms. I might write about these for a future article in the Java 101 series.

1 2 Page 2
Page 2 of 2