Week 2. Data Structures

3.1 Key Concepts

3.1.1 LinkedList and ArrayList

In Java, you are probably familiar with the following Data Structures or Data Types:

• Array
• ArrayList
• LinkedList

What is the difference between them?

Array is a primitive data type. Let’s leave that aside for now.

Both ArrayList and LinkedList are classes inheriting the abstract class List. Therefore they share a number of methods.

• add(index,element)
• get(index)
• remove(index)

There are others, but these three are particularly interesting from an algorithmic point of view. We shall discuss their complexity.

3.1.2 ADT (Abstract Data Type)

In Object Oriented Programming the set of operations will normally be a set of methods. Java can codify an ADT as an interface, and to implement the ADT a class must implement the interface. However, the ADT define the semantics (behaviour) of the methods, while the interface only defines the syntax (call signature). Thus an implementation of the interface is not necessarily an implementation of the ADT.

The ADT itself, is the mathematical model describing the interface and its semantics. An API, in contrast, is the interface of the implementation.

1.

Static and Dynamic Definitions

• Java Generics
• Type parameters

3.1.3 The Array ADT

The Array ADT would normally provides methods to

• get the element at a given position
• set (change) the element at a given position

The Java ArrayList class in Java provides many more methods. Most importantly, you can change the size of the ArrayList. Adding or removing an element at the end of the ArrayList is an important functional extension. When Arrays are used in the theoretical literature, the size is usually assumed to be fixed.

THe other methods of ArrayList are convenience methods which can be implemented using the methods above.

3.1.4 The List ADT

The List ADT is stateful. It always has a cursor pointing to the current position.

• add an element at the current position
• remove an element at the current position
• next get the next element in the list

The ListIterator Notably, the list classes in Java does not implement an interface representing the List ADT. Instead, the List interface has the listIterator() which returns an object implementing the ListIterator interface, which represents the List ADT.

This makes it possible to access the same List concurrently in different subprograms, because each iterator maintains its own cursor.

In Java:

• AbstractList (Abstract Class)
• LinkedList and ArrayList (Concrete Classes)
• List (interface) $\sim$ Array (ADT)
• ListIterator (Java) $\sim$ List (ADT)
• LinkedList also implements the Deque ADT

3.1.5 Algorithm Theory

The interesting questions in algorithm theory is how we implement the ADTs so that they are correct and efficient, and exactly how efficient each operation is in terms of complexity.

3.1.6 Copies

1.

Equality

2.

Cloning - shallow and deep copies