자바의 LinkedList

안녕하세요! 최근의 모든 강의는 ArrayList 목록을 연구하는 데 전념했습니다 . 이 데이터 구조는 매우 편리하며 많은 문제를 해결할 수 있습니다. 그러나 Java에는 다른 많은 데이터 구조가 있습니다. 왜? 우선, 기존 작업의 범위가 매우 넓고 작업마다 다른 데이터 구조가 가장 효과적이기 때문입니다 . 오늘 우리는 새로운 구조인 이중 연결 목록 LinkedList 에 대해 알아 보겠습니다 . 이것이 어떻게 작동하는지, 왜 이중 연결이라고 부르는지, ArrayList 와 어떻게 다른지 알아봅시다 . LinkedList 에서 요소는 실제로 체인의 링크입니다. 각 요소에는 저장되는 데이터 외에도 이전 및 다음 요소에 대한 링크가 있습니다 . 이러한 링크를 사용하면 한 요소에서 다른 요소로 이동할 수 있습니다. 다음과 같이 생성됩니다.

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);

   }
}

결론:

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

목록의 구조는 다음과 같습니다. 새 요소가 어떻게 추가되는지 살펴보겠습니다. 이는 add().

earlBio.add(str2);

이 코드 줄에서 목록은 문자열이라는 하나의 요소로 구성됩니다 str1. 그림에서 다음에 무슨 일이 일어나는지 봅시다: 결과적으로 str2, 그 안에 저장된 str1링크를 통해 연결되고 next: 이제 이중 연결 목록의 주요 아이디어를 이해해야 합니다. 이러한 링크 체인 덕분에 요소는 정확하게 단일 목록이 됩니다. 내부에는 in 이나 이와 유사한 배열이 없습니다. ArrayList를 사용한 모든 작업은 대체로 내부 배열 작업으로 귀결됩니다. 모든 작업은 링크 변경으로 귀결됩니다. 이는 목록 중간에 요소를 추가하면 매우 명확하게 알 수 있습니다. previousLinkedListLinkedListArrayListLinkedList

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);

   }
}

보시다시피 오버로드된 메서드를 사용하면 add()새 요소에 대한 특정 인덱스를 지정할 수 있습니다. 이 경우 와 str2사이에 줄을 추가하려고 합니다 . 내부에서 일어나는 일은 다음과 같습니다. 내부 링크를 변경한 결과 요소가 목록에 성공적으로 추가되었습니다. 이제 3개 요소가 모두 연결되었습니다. 체인의 첫 번째 요소에서 마지막 요소로 이동할 수 있습니다. 삽입에 대해 어느 정도 알아냈지만 요소를 삭제하는 경우는 어떻게 되나요? 작동 원리는 동일합니다. 제거되는 요소의 "측면"에 있는 두 요소의 링크를 재정의하기만 하면 됩니다. str1str3str2next

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);
   }
}

인덱스 1이 있는 요소(목록 중간에 있음)를 삭제하면 다음과 같은 일이 발생합니다. 링크를 재정의한 후 원하는 결과를 얻습니다. 삭제 ArrayList와 달리 배열 요소의 이동 등은 없습니다. str1간단히 및 요소 의 참조를 재정의합니다 str3. 이제 그들은 서로를 가리키며 개체는 str2이 링크 체인에서 "빠져 나와" 더 이상 목록의 일부가 아닙니다.

방법 개요

방법 LinkedList과 많은 유사점이 있습니다 . ArrayList예를 들어 add(), remove(), indexOf(), clear()( contains()목록에 포함된 요소), set()(대체 요소를 삽입)과 같은 메서드 size()가 두 클래스 모두에 존재합니다. add()(예제 및 에서 알 수 있듯이 remove()) 대부분은 내부적으로 다르게 작동하지만 궁극적으로는 동일한 작업을 수행합니다. 그러나 LinkedList목록의 시작과 끝을 작업하기 위한 별도의 메서드가 있는데, 이는 다음에는 없습니다 ArrayList.

• addFirst(), addLast(): 목록의 시작/끝에 요소를 추가하는 방법

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 + '\'' +
               '}';
   }
}

결론:

[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'}]

그 결과 Ford가 1위에 올랐고, Fiat가 맨 마지막에 올랐습니다.

• peekFirst(), peekLast(): 목록의 첫 번째/마지막 요소를 반환합니다. null목록이 비어 있으면 반환합니다 .

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());
}

결론:

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

• pollFirst(), pollLast(): 목록의 첫 번째/마지막 요소를 반환 하고 목록에서 제거합니다 . null목록이 비어 있으면 반환

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);
}

결론:

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

• toArray(): 목록 요소의 배열을 반환합니다.

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));
}

결론:

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

이제 우리는 그것이 어떻게 작동 LinkedList하고 ArrayList. 그것을 사용하면 어떤 이점이 있습니까 LinkedList? 우선, 목록의 중간 부분을 작업할 때 . 중간에 삽입하고 삭제하는 것이 LinkedList에서보다 훨씬 간단합니다 ArrayList. 우리는 단순히 이웃 요소의 링크를 재정의하고 불필요한 요소는 링크 체인에서 "떨어집니다". 우리 가 있는 동안 ArrayList:

• 공간이 충분한지 확인(삽입 시)
• 부족하다면 새로운 배열을 생성하고 거기에 데이터를 복사(붙여넣기 시)
• 요소를 삭제/삽입하고 다른 모든 요소를 ​​오른쪽/왼쪽으로 이동합니다(작업 유형에 따라 다름). 게다가 이 프로세스의 복잡성은 목록의 크기에 따라 크게 달라집니다. 10개의 요소를 복사/이동하는 것과 백만 개의 요소로 동일한 작업을 수행하는 것은 전혀 다릅니다.

즉, 프로그램에서 삽입/삭제 작업이 목록 중간에서 더 자주 발생 LinkedList하면 ArrayList.

이론에 의하면

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));
   }
}

결론:

Время работы для 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));
   }
}

결론:

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

갑자기! LinkedList우리는 훨씬 더 효율적인 작업, 즉 목록 중간에 100개의 요소를 삽입하는 작업을 수행하고 있었던 것 같습니다 . 그리고 우리의 목록은 엄청납니다. 요소가 5,000,000개입니다. ArrayList요소를 삽입할 때마다 수백만 개의 요소를 이동해야 했습니다! 그의 승리 이유는 무엇인가? 첫째, 요소는 ArrayList고정된 시간 내에 액세스됩니다. 귀하가 표시할 때:

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

[2_000_000] 의 경우 ArrayList내부에 배열이 있기 때문에 이는 메모리의 특정 주소입니다. 배열 은 LinkedList그렇지 않습니다. 링크 체인을 따라 요소 번호 2_000_000을 찾습니다. 그에게 이것은 메모리의 주소가 아니라 여전히 도달해야 하는 링크입니다.

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………

결과적으로 목록 중간에 삽입(삭제)할 때마다 ArrayList액세스해야 하는 메모리의 정확한 주소를 이미 알고 있지만 LinkedList여전히 올바른 위치를 "찾아내야" 합니다. 둘째 , 문제는 'a' 자체의 구조에 있다 ArrayList. 내부 배열 확장, 모든 요소 복사 및 요소 이동은 특수 내부 기능인 에 의해 수행됩니다 System.arrayCopy(). 이 작업에 특별히 최적화되어 있기 때문에 매우 빠르게 작동합니다. 그러나 원하는 인덱스로 "구르기"할 필요가 없는 상황에서는 LinkedList실제로 더 나은 결과를 보여줍니다. 예를 들어 목록의 시작 부분에 삽입이 발생하는 경우입니다. 거기에 백만 개의 요소를 삽입해 보겠습니다.

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());
       }
   }

}

결론:

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

전혀 다른 결과! 목록의 시작 부분에 백만 개의 요소를 삽입하는 데 43초 이상이 걸렸는데 ArrayList, LinkedList0.1초 만에 완료되었습니다! LinkedList이 상황에서 우리는 매번 목록의 중간에 대한 링크 체인을 "실행"할 필요가 없다는 사실이었습니다 . 그는 즉시 목록 시작 부분에서 필요한 색인을 찾았고 이미 작동 원리의 차이가 그의 편이었습니다. :) 실제로 " ArrayList대 LinkedList" 논의가 매우 널리 퍼져 있으며 현재로서는 이에 대해 깊이 다루지 않겠습니다. 수준. 기억해야 할 주요 사항:

• "종이에 있는" 특정 컬렉션의 모든 장점이 실제로 작동하는 것은 아닙니다. (목록 중간의 예를 사용하여 이를 살펴보았습니다.)
• 컬렉션을 선택할 때 극단적으로 접근해서는 안 됩니다(“ ArrayList항상 더 빠르므로 사용하면 실수하지 않을 것입니다. LinkedList오랫동안 사용한 사람은 없습니다.”).

비록 제작자 LinkedListJoshua Bloch도 그렇게 말하지만 :) 그러나 이러한 관점은 100% 정확하지는 않으며 우리는 이를 확신합니다. 이전 예에서는 LinkedList400(!)배 더 빠르게 작동했습니다. LinkedList또 다른 점은 그것이 최선의 선택이 될 상황이 실제로 거의 없다는 것입니다 . 그러나 그들은 존재하며 적시에 LinkedList진지하게 당신을 도울 수 있습니다. 강의 시작 부분에서 우리가 이야기한 것을 잊지 마십시오. 다양한 데이터 구조는 다양한 작업에 가장 효과적입니다. 문제의 모든 조건이 알려질 때까지는 어떤 데이터 구조가 더 좋을지 100% 확신을 가지고 말할 수 없습니다. 나중에 이러한 컬렉션에 대해 더 많이 알게 될 것이며 선택을 하는 것이 더 쉬울 것입니다. 그러나 가장 간단하고 효과적인 옵션은 항상 동일합니다. 즉, 프로그램의 실제 데이터에 대해 두 가지를 모두 테스트하는 것입니다. 그러면 두 목록의 결과를 직접 눈으로 확인할 수 있으며 절대 잘못될 일이 없을 것입니다 :)