ArrayList와 LinkedList

List 인터페이스 : 순서가 있는 집합, 데이터의 중복을 허용하는 컬렉션을 구현하는 데 사용된다.
List인터페이스를 구현한 클래스 중에 가장 많이 사용되는 클래스는 ArrayList와 LinkedList가 있다.
 

1️⃣ ArrayList 

• Vector와 구현원리나 기능적인 측면에서 동일하다.(Vector클래스는 소스와의 호환성을 위해서 남겨둔 것이므로 사용하지 말자)
• List인터페이스를 구현한다
• ArrayList는 말 그대로 배열의 원리를 이용한 컬렉션 클래스다.(배열의 사이즈는 ArrayList에서 알아서 조절한다)
• ArrayList가 허용하는 범위(capacity)를 넘어가는 경우 경우 기존배열의 사이즈에 *2 사이즈의 배열을 만들고 거기에 요소를 복사하여 배열을 만들어 사용한다.
• 배열에 요소를 삭제하거나 추가하면 모든 배열의 요소를 옮겨야 해서 성능이 좋지 않다.(효율성이 떨어진다)
  • 만일 변수를 삭제할때 1,3,4를 삭제하는 경우 1->3->4를 차례로 삭제한다면 요구대로 삭제되지 않는다. 
  • 왜냐하면 1을 삭제한후에 기존에 1번 자리를 뒤에 있던 값을 당겨서 채우고 그다음에 3번을 삭제하게 되어서 원하는 대로 삭제되지 않는다
  • 이런 경우에는 4->3->1 순서로(거꾸로) 삭제하면 이런 문제는 발생하지 않는다.
• ArrayList의 초기 사이즈는 10이고 사용자가 초기 사이즈를 지정할 수 있다  (ArrayList의 생성자로 initialCapacity를 줄 수 있다) 

//실제 ArrayList의 생성자 중 용량을 초기에 결정하는 경우
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

ArrayList<Integer> arr1 = new ArrayList<>();
ArrayList<Integer> arr2 = new ArrayList<>(20);
ArrayList<Integer> arr3 = new ArrayList<>(List.of(1, 2, 3));

---

2️⃣ LinkedList

• 각 요소들이 노드로 연결되어 있어서 ArrayList에서 배열을 추가하거나 삭제하는 경우처럼 모든 데이터를 옮기지 않고 노드의 이전, 이후 노드의 참조만 수정하면 된다.(빠르게 요소를 삽입하고 제거할 수 있다)
• LinkedList는 List,Queue, Deque 인터페이스를 구현한다. ( Queue <Integer> q = new LinkedList <>()처럼 사용가능한 이유)
• 자바에서의 linkedlist는 더블 링크드 리스트로 구현되어 있다( 노드가 다음노드와 이전노드를 가지고 있어 참조 편리성이 좋다.
• n번째 인덱스를 가진 데이터를 찾기위해서 n번째 노드까지 모두 탐색해야 한다. 

LinkedList<Integer> arr1 = new LinkedList<>();
Queue<Integer> queue = new LinkedList<>();

 

---

3️⃣ ArrayList VS LinkedList 

ArrayList는 대량의 데이터에 대하여 추가/삭제에는 불리하고, 참조에는 유리하다.
반면 LinkedList는 대량의 데이터에 대하여 참조에는 불리하고, 추가/삭제에는 유리하다
 

• 임의 요소를 탐색하는 경우(get(),set())
  • ArrayList의 경우는 어떤 index의 요소를 찾으려고 하는 경우
    "인덱스가 n인 데이터의 주소 = 배열의 주소 + n*데이터 타입의 크기"를 통해서 수식만 계산하여 찾을 수 있다(O(1))
  • LinkedList의 경우에는 모든 노드를 탐색해야 한다. (O(n)) 
• 임의 요소를 추가하는 경우(add(), remove())
  • Linked List에서 데이터를 추가, 삭제하는 경우 이전노드와 이후노드의 참조요소만 변경해 주면 된다.
    해당 요소까지 탐색하는데 O(n)이 들기 때문에 O(n), 헤드와 테일에 추가하는 경우라면 탐색 시간이 들지 않아 O(1)이다.
  • ArrayList에서는 모든 요소의 위치를 이동해야 하는 과정이 있으므로 추가 삭제에 시간이 많이 든다. 
    탐색 시간이 들지 않지만 모든 요소를 뒤로 미루거나 당기는 과정이 필요해서 O(n)이다.

4️⃣ 결론 

• 요소를 자주 추가하거나 제거하고 임의의 위치에서 요소에 자주 액세스해야 하는 경우 ➡️ ArrayList가 가장 적합하다.
• 컬렉션의 중간에 요소를 자주 삽입하거나 제거하고 임의의 위치에서 요소에 많이 액세스 하지 않는 경우, LinkedList가 가장 적합하다.

 
 ➕) 두 클래스의 장점을 사용하는 법
처음에 작업하기 전에는 ArrayList를 이용해서 저장하고 실제 작업 시에는 LinkedList로 옮겨서 작업하는 방법이 있다.
 
 
[🌟참고✨]
자바의 정석 3판