링크드 목록이 색인 기반 컬렉션이 아니라고 말하는 이유는 무엇입니까?

Question

나는 linkedlist와 arraylist의 차이를 이해할 수 없다. 아래의 구현은 나를 혼란스럽게합니다. Uptil 이제는 LinkedList가 인덱스 기반 데이터 구조가 아니라고 가정합니다.

package com.rnd.core.collections; 

import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.List; 

public class LinkedListTest { 
    public static void main(String[] args) { 
     List<String> myLinkedList = new LinkedList<String>(); 
     myLinkedList.add("Spring"); 
     myLinkedList.add("Struts"); 
     myLinkedList.add("EJB"); 
     myLinkedList.add("Hibernate"); 
     myLinkedList.add(1, "Collections"); 
     myLinkedList.add(1, "JMS"); 

     System.out.println(""+myLinkedList.subList(1, 3)); 
     System.out.println("Search result for \"Hibernate\":" + myLinkedList.contains("Hibernate")); 
     System.out.println("Search result for \"Hibernate\":" + myLinkedList.contains("ibatis")); 
     for(String item: myLinkedList){ 
      System.out.println(item.toString());  
     } 

     System.out.println("<><>"+myLinkedList.get(1)); 

     List<String> myArrayList = new ArrayList<String>(); 

     myArrayList.add("Spring"); 
     myArrayList.add("Struts"); 
     myArrayList.add("EJB"); 
     myArrayList.add("Hibernate"); 
     myArrayList.add(1, "Collections"); 
     myArrayList.add(1, "JMS"); 

     myArrayList.subList(1, 2); 
     System.out.println("*****************"+myArrayList.subList(1, 3)); 

    } 

} 

이 점에 대해 도움을 주실 수 있습니다.

Answer 1

차이점은 기본 구현에 있습니다. 배열은 고정 크기의 메모리 블록으로 청크로 나뉘며 각 청크는 하나의 요소를 담고 있습니다. 인덱스 번호를 사용하여 개별 요소로 쉽게 이동하고 요소 하나를 수정해도 나머지 배열에는 영향을주지 않습니다. 배열에 요소를 추가하는 것은 비용이 많이 든다. 새로운 요소를위한 공간을 만들기 위해 전체 배열을 큰 공간에 복사해야하기 때문이다. (실제로 필요한 것보다 더 많은 공간을 미리 할당하여 어레이의 끝에 추가하는 것이 더 빠를 수 있지만 결국에는 전체 배열을 다시 복사해야합니다.)

링크 된 목록은 저장소의 각 요소와 목록의 다음 항목에 대한 포인터를 포함하는 독립적 인 메모리 블록. 목록의 크기에 관계없이 새로운 메모리 블록을 잡고 작은 수의 포인터를 수정하기 만하면되므로 (목록에 추가하려는 위치에 대한 포인터가있는 경우) 그러한 목록에 추가하는 것이 빠릅니다. 전체적으로. 비용은 으로 중간에있는 임의의 노드에 대한 포인터 인을 얻으려면 처음부터 목록의 길이를 따라야합니다.

이것은 약간 단순한 것이지만 기본 아이디어는 각 기본 데이터 형식이 "목록"의 추상적 개념의 다양한 응용 프로그램에 적합하며 작업 유형 (조회, 추가 사항)을 고려해야한다는 것입니다. , 삭제 등)을 선택하기 전에 수행해야합니다.