Let's take your example of a Dog and a Cat class, and let's illustrate using C#:

Both a dog and a cat are animals, specifically, quadruped mammals (animals are waaay too general). Let us assume that you have an abstract class Mammal, for both of them:

```
public abstract class Mammal
```

This base class will probably have default methods such as:

All of which are behavior that have more or less the same implementation between either species. To define this you will have:

```
public class Dog : Mammal
public class Cat : Mammal
```

Now let's suppose there are other mammals, which we will usually see in a zoo:

```
public class Giraffe : Mammal
public class Rhinoceros : Mammal
public class Hippopotamus : Mammal
```

This will still be valid because at the core of the functionality `Feed()`

and `Mate()`

will still be the same.

However, giraffes, rhinoceros, and hippos are not exactly animals that you can make pets out of. That's where an interface will be useful:

```
public interface IPettable
{
IList<Trick> Tricks{get; set;}
void Bathe();
void Train(Trick t);
}
```

The implementation for the above contract will not be the same between a cat and dog; putting their implementations in an abstract class to inherit will be a bad idea.

Your Dog and Cat definitions should now look like:

```
public class Dog : Mammal, IPettable
public class Cat : Mammal, IPettable
```

Theoretically you can override them from a higher base class, but essentially an interface allows you to add on only the things you need into a class without the need for inheritance.

Consequently, because you can usually only inherit from one abstract class (in most statically typed OO languages that is... exceptions include C++) but be able to implement multiple interfaces, it allows you to construct objects in a strictly *as required* basis.

**Summary** `ArrayList`

with `ArrayDeque`

are preferable in *many* more use-cases than `LinkedList`

. If you're not sure — just start with `ArrayList`

.

TLDR, in ArrayList accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList adding an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than ArrayList.

`LinkedList`

and `ArrayList`

are two different implementations of the List interface. `LinkedList`

implements it with a doubly-linked list. `ArrayList`

implements it with a dynamically re-sizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For `LinkedList<E>`

`get(int index)`

is *O(n)* (with *n/4* steps on average), but *O(1)* when `index = 0`

or `index = list.size() - 1`

(in this case, you can also use `getFirst()`

and `getLast()`

). **One of the main benefits of** `LinkedList<E>`

`add(int index, E element)`

is *O(n)* (with *n/4* steps on average), but *O(1)* when `index = 0`

or `index = list.size() - 1`

(in this case, you can also use `addFirst()`

and `addLast()`

/`add()`

). **One of the main benefits of** `LinkedList<E>`

`remove(int index)`

is *O(n)* (with *n/4* steps on average), but *O(1)* when `index = 0`

or `index = list.size() - 1`

(in this case, you can also use `removeFirst()`

and `removeLast()`

). **One of the main benefits of** `LinkedList<E>`

`Iterator.remove()`

is *O(1)*. **One of the main benefits of** `LinkedList<E>`

`ListIterator.add(E element)`

is *O(1)*. **One of the main benefits of** `LinkedList<E>`

^{Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)}

For `ArrayList<E>`

`get(int index)`

is *O(1)*. **Main benefit of** `ArrayList<E>`

`add(E element)`

is *O(1)* amortized, but *O(n)* worst-case since the array must be resized and copied
`add(int index, E element)`

is *O(n)* (with *n/2* steps on average)
`remove(int index)`

is *O(n)* (with *n/2* steps on average)
`Iterator.remove()`

is *O(n)* (with *n/2* steps on average)
`ListIterator.add(E element)`

is *O(n)* (with *n/2* steps on average)

^{Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)}

`LinkedList<E>`

allows for constant-time insertions or removals *using iterators*, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says *"operations that index into the list will traverse the list from the beginning or the end, whichever is closer"*, so those methods are *O(n)* (*n/4* steps) on average, though *O(1)* for `index = 0`

.

`ArrayList<E>`

, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an `ArrayList`

is *O(n)* in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an `ArrayList`

is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a `LinkedList`

arise when you re-use existing iterators to insert and remove elements. These operations can then be done in *O(1)* by changing the list locally only. In an array list, the remainder of the array needs to be *moved* (i.e. copied). On the other side, seeking in a `LinkedList`

means following the links in *O(n)* (*n/2* steps) for worst case, whereas in an `ArrayList`

the desired position can be computed mathematically and accessed in *O(1)*.

Another benefit of using a `LinkedList`

arises when you add or remove from the head of the list, since those operations are *O(1)*, while they are *O(n)* for `ArrayList`

. Note that `ArrayDeque`

may be a good alternative to `LinkedList`

for adding and removing from the head, but it is not a `List`

.

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a `LinkedList`

has more overhead since pointers to the next and previous elements are also stored. `ArrayLists`

don't have this overhead. However, `ArrayLists`

take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an `ArrayList`

is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the `ArrayList`

with a higher initial capacity.

If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on...). Addition of elements takes linear time in LinkedList as stated above.

An ArrayList, is a growable array. It is just like a regular array. Under the hood, when an element is added at index i, it creates another array with a size which is 1 greater than previous size (So in general, when n elements are to be added to an ArrayList, a new array of size previous size plus n is created). The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.

## Best Solution

There's a lot more to abstract classes than default method implementations (such as private state), but as of Java 8, whenever you have the choice of either, you should go with the defender (aka.

`default`

) method in the interface.The constraint on the default method is that it can be implemented only in the terms of calls to other interface methods, with no reference to a particular implementation's state. So the main use case is higher-level and convenience methods.

The good thing about this new feature is that, where before you were forced to use an abstract class for the convenience methods, thus constraining the implementor to single inheritance, now you can have a really clean design with just the interface and a minimum of implementation effort forced on the programmer.

The original motivation to introduce

`default`

methods to Java 8 was the desire to extend the Collections Framework interfaces with lambda-oriented methods without breaking any existing implementations. Although this is more relevant to the authors of public libraries, you may find the same feature useful in your project as well. You've got one centralized place where to add new convenience and you don't have to rely on how the rest of the type hierarchy looks.