Summary

We covered a few basic data structures and the algorithms for manipulating them. In addition to this, we also found out their running time complexities. To summarize this, an array provides you with the fastest random access there is with this time complexity: O(1). But arrays cannot change size; the only modification they allow is to change the value of an element. A linked list allows fast append at the end and insertion at the beginning at O(1) time. However, O(1) removal is only available for removing the first element. This is resolved by a doubly linked list that also allows O(1) removal from the end. A circular linked list holds a reference to the first element in the next reference of the last element. This makes the list a circular structure that allows one to loop indefinitely.

In the upcoming chapters, we will discuss the abstraction of data structures called abstract data types. We will use the data structures we have seen in this chapter to implement the abstract data types, which in turn will be used in later chapters.