Linked lists are great data structures if you want to be able to perform the following operations efficiently:

1. Add an element to the start or end of the list Time complexity: \(O(1)\).

2. Remove the first or the last element of the list Time complexity: \(O(1)\).

3. Get the first and last elements on the list Time complexity: \(O(1)\).

4. Get the number of elements stored in the list Time complexity: \(O(1)\).

5. Iterate over all elements in the list. Time complexity: \(O(n)\) where \(n\) is the number of elements on the list.

All these operations can be perfomed optimal time. This means that operations 1., 2., 3., 4. are perfomed in constant time and operation 5. is performed in linear time. Note that operation 5. could not be faster since we cannot get away without inspecting each element in order to iterate over all elements.

Download the following program and execute it on this input

This program simply reads lines until an end of file is reached. When reading files from the standard input you can signal the end of file by clicking ctrl + d on Linux or OS X. On Windows use ctrl + z.

After reading the input, the program will perform the following steps:

1. Print the number of lines
2. Print all the lines
3. Print the first and last lines
4. Remove the first and last lines
5. Print the first and last lines

Thus, you should get the following output:

4
line1
line2
line3
line4
first: line1
last: line4
new first: line2
new last: line3

The LinkedList class offers others methods. But we strongly recommend that you stick to these ones and you usually want to use such a linked list only when the above operations are the set of operations that you want to perform on your data. More other kinds of operations there are probably other data structures that are more suited.

NEVER USE LINKED LISTS IF YOU WANT TO ACCESS YOUR ELEMENTS BY INDEX OR VALUE

A common example that we often see students do, is to call the method public E get(int index). This method will return the element at position index in the list. So, for instance, after reading 4 lines, you can get each of those lines by calling list.get(0), list.get(1), list.get(2) and list.get(3). This is a very bad idea since in constrast with, for instance, an array, this funtion does not run in constant time. Instead it runs in linear time \(O(n)\) where \(n\) is the number of elements in the list.

The same is true for accessing elements by value int indexOf(Object o) or checking whether the list contains a given element with boolean contains(Object o). Never use these methods unless efficieny is not a concern for the problem your are solving (which is rarely the case...)

Note: It is possible to actually implement some of these methods efficiently using position aware linked lists but this is not really useful as we will see other simples data structures for achieving this.

In the next task, we will teach you how to implement linked lists because we believe that it is educational to do so and is a good skill to have when trying to develop more complex data structures.

However, unless the problem really requires you to be able to access the internal structure of the linked list, in a contest situation you should use the implementation provided by the language that you are using. This will save a good amount of time and help you avoid bugs in you implementation.

We thus recommender that you linked lists when the operations required on your data are the ones mentioned above. In Java that roughly corresponds to limiting yourself to using the following methods:

1. addFirst(E e), addLast(E e)
2. removeFirst(), removeLast()
3. getFirst(), getLast()
4. toString(), size()
5. Iterating ovar all elements with for(E e : myList) { ... } where E is the type of the elements on the list.