LinkedList in Java

Hello! All recent lectures have been devoted to studying the ArrayList list . This data structure is very convenient and allows you to solve many problems. However, Java has many other data structures. Why? First of all, because the range of existing tasks is very wide, and for different tasks different data structures are most effective . Today we will get acquainted with a new structure - a doubly linked list LinkedList . Let's figure out how it works, why it's called doubly connected, and how it differs from ArrayList . In a LinkedList, the elements are actually links in a chain. Each element, in addition to the data it stores, has a link to the previous and next element . These links allow you to move from one element to another. It is created like this:

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Conclusion:

[Hello World! My name is Earl, I love Java, I live in Moscow]

This is what the structure of our list will look like: Let's see how a new element is added. This is done using the add().

earlBio.add(str2);

At the time of this line of code, our list consists of one element - the string str1. Let's see what happens next in the picture: As a result str2, and str1become connected through the links stored in them nextand previous: Now you should understand the main idea of ​​​​a doubly linked list. The elements LinkedListare a single list precisely thanks to this chain of links. There is no array inside LinkedList, like in ArrayList, or anything similar. All work with ArrayList (by and large) comes down to working with the internal array. All work with LinkedListcomes down to changing links. This is very clearly seen by adding an element to the middle of the list:

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

As you can see, the overloaded method add()allows you to specify a specific index for the new element. In this case, we want to add a line str2between str1and str3. This is what will happen inside: And as a result of changing the internal links, the element str2is successfully added to the list: Now all 3 elements are linked. From the first element along the chain nextyou can go to the last and back. We have more or less figured out the insertion, but what about deleting elements? The operating principle is the same. We simply redefine the links of the two elements “on the sides” of the one being removed:

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

This is what will happen if we delete the element with index 1 (it is in the middle of the list): After redefining the links, we get the desired result: Unlike deleting, there ArrayListare no shifts of array elements and the like. We simply redefine the references of the str1and elements str3. Now they point to each other, and the object str2has “dropped out” of this chain of links and is no longer part of the list.

Overview of methods

It LinkedListhas many similarities with ArrayListthe methods. For example, methods such as add(), remove(), indexOf(), clear(), contains()(is the element contained in the list), set()(inserting an element with replacement) size()are present in both classes. Although (as we found out in the example add()and remove()) many of them work differently internally, but ultimately they do the same thing. However, it LinkedListhas separate methods for working with the beginning and end of the list, which are not present in ArrayList:

• addFirst(), addLast(): methods for adding an element to the beginning/end of the list

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Conclusion:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

As a result, Ford ended up at the top of the list, and Fiat at the end.

• peekFirst(), peekLast(): return the first/last element of the list. Return nullif the list is empty.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Conclusion:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): return the first/last element of the list and remove it from the list . Return nullif the list is empty

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println("What's left on the list?");
   System.out.println(cars);
}

Conclusion:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): returns an array of list elements

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Conclusion:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Now we know how it works LinkedListand how it differs from ArrayList. What are the benefits of using it LinkedList? First of all, in working with the middle of the list . Inserting and deleting in the middle LinkedListis much simpler than in ArrayList. We simply redefine the links of neighboring elements, and the unnecessary element “falls out” from the chain of links. While in ArrayListwe:

• check if there is enough space (when inserting)
• if it’s not enough, create a new array and copy the data there (when pasting)
• delete/insert an element, and shift all other elements to the right/left (depending on the type of operation). Moreover, the complexity of this process greatly depends on the size of the list. It's one thing to copy/move 10 elements, but quite another to do the same with a million elements.

That is, if in your program insertion/deletion operations occur more often with the middle of the list, LinkedListit should be faster than ArrayList.

In theory

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for(int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusion:

Время работы для LinkedList (в мorсекундах) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for (int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusion:

Время работы для ArrayList (в миллисекундах) = 181

Suddenly! It would seem that we were performing an operation that LinkedListshould have been much more efficient - inserting 100 elements into the middle of the list. And our list is huge - 5,000,000 elements: ArrayListwe had to shift a couple of million elements each time we inserted them! What is the reason for his victory? First, an element is accessed in ArrayLista fixed amount of time. When you indicate:

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

then in the case of ArrayList[2_000_000] this is a specific address in memory, because it has an array inside. While the LinkedListarray does not. It will look for element number 2_000_000 along the chain of links. For him, this is not an address in memory, but a link that still needs to be reached:

fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next………

As a result, with each insertion (deletion) in the middle of the list, ArrayListit already knows the exact address in memory to which it should access, but LinkedListit still needs to “find out” to the right place. Secondly , the matter is in the structure of ArrayList'a itself. Expanding the internal array, copying all elements and shifting elements is carried out by a special internal function - System.arrayCopy(). It works very quickly because it is specially optimized for this job. But in situations where there is no need to “stomp” to the desired index, LinkedListit really shows itself better. For example, if the insertion occurs at the beginning of the list. Let's try to insert a million elements there:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       //write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //calculate the difference
       System.out.println("Result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Conclusion:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

A completely different result! It took more than 43 seconds to insert a million elements into the beginning of the list ArrayList, while LinkedListit was completed in 0.1 seconds! It was precisely the fact that in this situation LinkedListwe did not have to “run” through the chain of links to the middle of the list each time. He immediately found the required index at the beginning of the list, and there the difference in operating principles was already on his side :) In fact, the “ ArrayListversus LinkedList” discussion is very widespread, and we will not go deep into it at the current level. The main thing you need to remember:

• Not all the advantages of a particular collection “on paper” will work in reality (we looked at this using the example from the middle of the list)
• You shouldn’t go to extremes when choosing a collection (“ ArrayListit’s always faster, use it and you won’t be mistaken. LinkedListNo one has been using it for a long time”).

Although even the creator LinkedListJoshua Bloch says so :) However, this point of view is far from 100% correct, and we are convinced of this. In our previous example LinkedListit worked 400 (!) times faster. Another thing is that there are really few situations when LinkedListit would be the best choice. But they exist, and at the right time LinkedListthey can seriously help you out. Don't forget what we talked about at the beginning of the lecture: different data structures are most effective for different tasks. It is impossible to say with 100% confidence which data structure will be better until all the conditions of the problem are known. Later you will know more about these collections, and it will be easier to make a choice. But the simplest and most effective option is always the same: test both on real data from your program. Then you can see with your own eyes the results of both lists and you definitely won’t go wrong :)