[컬렉션 프레임웍] ArrayList와 LinkedList

ArrayList

---

• List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다.
• Object배열을 이용해 데이터를 순차적으로 저장하고 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성하여 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음 저장된다.
• ArrayList의 요소를 삭제하는 경우, 삭제할 객체의 바로 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 객체를 덮어쓰는 방식으로 처리한다. 

 

==> 배열에 객체를 순차적으로 저장할 때와 객체를 마지막에 저장된 것부터 삭제하면 데이터를 옮기지않아도 되어 작업시간이 짧다.

 

        but, 배열의 중간에 위치한 객체를 추가, 삭제하는 경우, 다루는 데이터의 개수가 많을 수록 작업시간이 오래 걸린다. 

 

ArrayList list1 = new ArrayList(); //ArrayList 생성

//추가
list1.add(new Integer(5));
list1.add(new Integer(4));
list1.add(new Integer(2));
list1.add(new Integer(0));
list1.add(new Integer(1));
list1.add(new Integer(3));

//1~4사이(1~3) 의 객체를 반환하여 ArrayList생성
ArrayList list2 - new ArrayLsit(list1.subList(1,4));

//list 정렬(오름차순)
Collections.sort(list1);
Collections.sort(list2);

//list1이 list2의 모든 요소를 포함할 때만 true
System.out.println(list1.contiansAll(list2));

//추가
list2.add("B");
list2.add("C");
list2.add(3, "A")  //인덱스가 3인 곳에 "A" 추가

list2.set(3, "AA")  //인덱스가 3인 곳을 "AA"로 변경

list1.retainAll(list2); //list1에서 list2와 겹치는 부분만 남기고 나머지 삭제.

//list2에서 list1에 포함된 객체들을 삭제.
for(int i = list2.size()-1; i >=0; i--){
if(list1.contains(list2.get(i)))
list2.remove(i);  //인덱스가 i인 곳에 저장된 요소를 삭제.
}

 

 

 

LinkedList

---

• 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성.
• 각 요소(node)들이 자신과 연결된 다음 요소에 대한 참조(주소값) 과 데이터로 구성되어 있다.

class Node {
   Node next;   //다음 요소의 주소 저장
   Object obj;  //데이터 저장
   }

 

• 데이터 추가 시, 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고 새로운 요소가 그 다음 요소를 참조하도록 변경한다. 데이터 삭제 시, 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면된다.  ==> 처리속도가 매우 빠르다.

      but, 검색속도가 느리다.

 

ArrayList vs LinkedList

---

• - 배열의 경우,

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

위의 수식으로 간단하데 인덱스가 n인 원소의 값을 얻어올 수 있다.(각 요소들이 연속적으로 메모리상에 존재하기때문에 읽는 시간이 빠르다. 그렇지만 메모리사용이 비효율적이다.) 

 

but, LinkedList는 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있기 때문에 데이터의 개수가 많아질수록 데이터를 읽어오는 시간(접근시간) 이 길어진다.

 

따라서, 데이터의 개수가 변하지 않는 경우 -> ArrayList

             데이터의 추가,삭제가 많다면 -> LinkedList

 

참고) 자바의 정석 기초