his course introduces fundamental data structures and the underlying widely-used algorithms. They include various implementations of arrays, lists, maps, hash tables, priority queues, search trees, graphs, and their algorithmic applications. We express these structures in an Object-Oriented Programming (OOP) context and use the Java Programming Language for this purpose.
The course discusses a number of key concepts in OOP. Abstraction and encapsulation are two such concepts. Abstraction at the data level gives rise to expressing a data structure as an Abstract Data Type (ADT). The concept of data abstraction (ADT) predates OOP. OOP adopts a higher level of abstraction, namely objects. A data structure, like any other abstracted entity, is encapsulated as an object with state (data) and behaviour (functionality). An object is an instance of its class type. This facilitates a higher level of procedural abstraction: hierarchical inheritance & polymorphism. Parameters in method calls can now be objects of any specified type, possessing not only pure data, but also specified functional behaviour.
An ADT's client is any (user application) class that accesses and invokes the ADT. Through encapsulation, a client can directly access only externally visible members of the ADT, namely its Application Programming Interface (API), and is oblivious to the internal details, hence to any particular implementation, of the ADT. The interaction between the client and the ADT implementation is through this API which acts as a contract between them. This contract is expressed by public & protected class member signatures, pre/post conditions, and invariants. Implementing an API means implementing the corresponding ADT that respects the API contract. An important benefit is code flexibility: the ADT implementation can be changed and improved over time without changing its API, and hence, without breaking any client code.