자바 LinkedList

안녕! 모든 최신 수업은 ArrayList 에 전념했습니다 . 이 데이터 구조는 매우 편리하고 유용합니다. 많은 작업을 처리할 수 있습니다. 그러나 Java에는 다른 많은 데이터 구조가 있습니다. 왜? 무엇보다 작업의 범위가 방대하고 가장 효율적인 데이터 구조가 작업마다 다르기 때문입니다. 오늘 우리는 이중 연결 목록인 Java LinkedList 라는 새로운 구조를 만날 것입니다 .

어떻게 구성되어 있는지, 이중 연결이라고 하는 이유는 무엇인지, ArrayList 와 어떻게 다른지 살펴보겠습니다 . Java LinkedList 의 요소는 실제로 단일 체인의 링크입니다. 데이터 외에도 각 요소는 이전 및 다음 요소에 대한 참조를 저장합니다. 이러한 참조를 통해 한 요소에서 다른 요소로 이동할 수 있습니다. 만드는 방법은 다음과 같습니다.

public class Main {

   public static void main(java.lang.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 Canada");

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

       System.out.println(earlBio);

   }
}

출력: [Hello World! 내 이름은 Earl이고 Java를 좋아하고 캐나다에 살고 있습니다.] 목록은 다음과 같습니다. LinkedList - 2

새 요소를 추가하는 방법을 살펴보겠습니다. 이것은 add() 메서드를 사용하여 수행됩니다 .

earlBio.add(str2);

코드의 지점에서 목록은 하나의 요소인 String str1 로 구성됩니다 . 그림에서 다음에 무슨 일이 일어나는지 봅시다. LinkedList - 3

결과적으로 str2 와 str1은 목록의 이 노드에 저장된 다음 및 이전 링크를 통해 연결됩니다 . LinkedList - 4

이제 이중 연결 목록의 주요 아이디어를 이해해야 합니다. 이 링크 체인은 정확히 LinkedList 요소를 단일 목록으로 만드는 것입니다. ArrayList 와 달리 LinkedList 에는 배열이나 내부에 배열과 유사한 것이 없습니다. 대부분의 ArrayList 작업은 내부 배열 작업으로 귀결됩니다. Java LinkedList 에 대한 모든 작업링크 변경으로 귀결됩니다. 이는 목록 중간에 요소를 추가하여 매우 명확하게 볼 수 있습니다.

public class Main {

   public static void main(java.lang.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 Canada");

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

       System.out.println(earlBio);

   }
}

보시다시피 오버로드된 add() 메서드를 사용하면 새 항목에 대한 특정 인덱스를 지정할 수 있습니다. 이 경우 str1 과 str3 사이에 문자열 str2를 추가하려고 합니다 . 이것은 내부적으로 일어날 일입니다. 내부 링크를 변경한 후 str2가 목록에 성공적으로 추가되었습니다. 이제 3개의 요소가 모두 연결되었습니다. 다음 링크를 통해 체인의 첫 번째 요소에서 마지막 요소로 이동하고 다시 뒤로 이동할 수 있습니다 . 따라서 삽입은 상당히 편하지만 요소를 제거하는 것은 어떻습니까? 원리는 완전히 동일합니다. 제거할 요소의 "왼쪽과 오른쪽" 두 요소의 링크를 업데이트하기만 하면 됩니다. LinkedList - 5

public class Main {

   public static void main(java.lang.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 Canada");

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

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

인덱스가 1인 항목(목록 중간에 있음)을 삭제하면 다음과 같은 일이 발생합니다. LinkedList - 7

링크를 업데이트한 후 원하는 결과를 얻습니다. ArrayList LinkedList - 8

의 제거 작업과 달리 여기서는 배열 요소를 이동하거나 수행할 필요가 없습니다. 어떤 종류의. str1 및 str3 에 대한 링크만 업데이트합니다 . 그들은 이제 서로를 가리키고 str2는 링크 체인에서 " 탈락 "했으며 더 이상 목록의 일부가 아닙니다.

방법 개요

LinkedList 에는 ArrayList 와 공통된 메서드가 많이 있습니다 . 예를 들어 두 클래스 모두 add() , remove() , indexOf() , clear() , contains() (항목이 목록에 있는지 여부를 나타냄), set() (기존 요소를 대체함) 및 크기() . 그들 중 다수가 내부적으로 다르게 작동하지만( 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"를 목록의 맨 위에 놓았습니다 . 마지막에 "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 on the list?");
   System.out.println(cars);
}

Output: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} 목록에 남은 것은? [자동차{모델='부가티 베이론'}]

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개의 요소를 복사/이동하는 것과 100만 개의 요소로 동일한 작업을 수행하는 것은 또 다른 일입니다.

즉, 프로그램에서 목록 중간의 삽입/제거 작업이 가장 일반적이라면 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 taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

출력: LinkedList에 걸린 시간(밀리초) = 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 taken by 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));

그런 다음 ArrayList [2_000_000]은 특정 메모리 주소입니다(결국 목록에는 내부 배열이 있음). 그러나 LinkedList에는 배열이 없습니다. 링크 체인을 따라 요소 번호 2_000_000을 검색합니다. LinkedList의 경우 이것은 메모리 주소가 아니라 여전히 도달해야 하는 링크입니다 . next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next…… . 그 결과 각 리스트의 중간에 삽입(제거)할 때마다 , ArrayList는 액세스할 정확한 메모리 주소를 이미 알고 있지만 LinkedList는 여전히 "거기"에 도달해야 합니다. 둘째, 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("The 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 이제 완전히 다른 결과를 얻습니다! ArrayList는 목록 앞에 백만 개의 항목을 삽입하는 데 43초 이상을 소비했지만 LinkedList는 0.1초 만에 처리했습니다! LinkedList는 매번 목록 중간에 대한 링크 체인을 통해 실행할 필요가 없기 때문에 여기에서 이점을 얻었습니다. 목록의 시작 부분에서 필요한 인덱스를 즉시 찾으므로 다른 알고리즘이 이미 장점입니다. :) 사실, " ArrayList 대 LinkedList " 논의는 매우 광범위하며 현재 수준에서 깊이 파고들지는 않을 것입니다. 기억해야 할 주요 사항은 다음과 같습니다.

특정 컬렉션의 모든 이론적 이점이 항상 실제로 작동하는 것은 아닙니다(목록 중간과 관련된 예에서 이를 확인했습니다).
컬렉션 을 선택할 때 극단적인 입장을 취하지 마십시오 .

LinkedList 의 저자인 Joshua Bloch 도 이것이 사실이라고 말합니다. :) 그래도 이 관점은 100% 정확하지 않으며 우리는 이를 확신했습니다. 이전 예제에서 LinkedList는 400(!)배 더 빠릅니다. 또 다른 것은 LinkedList가 최선의 선택인 경우가 거의 없다는 것입니다 . 그러나 그것들은 존재하고 적절한 순간에 LinkedList후하게 보상할 수 있습니다. 수업 시작 부분에서 말한 것을 잊지 마십시오. 가장 효율적인 데이터 구조는 작업마다 다릅니다. 작업의 모든 조건을 알 때까지 어떤 데이터 구조가 가장 좋을지 100% 확신하는 것은 불가능합니다. 나중에 이러한 컬렉션에 대해 더 많이 알 수 있으므로 선택이 더 쉬워집니다. 그러나 가장 간단하고 효과적인 옵션은 항상 동일합니다. 프로그램에서 사용되는 실제 데이터에 대해 두 가지를 모두 시도하십시오. 그런 다음 두 유형의 목록이 어떻게 수행되는지 직접 확인할 수 있으며 확실히 잘못되지 않을 것입니다. :) 배운 내용을 보강하려면 Java 과정에서 비디오 강의를 시청하는 것이 좋습니다.

더 읽어보기:
LinkedList Java 데이터 구조