[Java] ArrayList vs LinkedList

ArrayList vs LinkedList

ArrayList

• 기존의 Vector를 개선한 것
• Object 배열을 이용해 데이터를 순차적으로 저장
• 더이상 저장할 공간이 없으면 큰 새로운 배열을 생성하여 내용을 복사해서 확장
• 중간 요소 삭제 시 바로 아래에 있는 데이터를 한칸씩 당겨서 덮어쓰는 방식 -> 시간 오래걸림

LinkedList

• ArrayList의 단점 : 크기 변경 불가, 추가 및 삭제 오래걸림
• LinkedList는 불연속적으로 존재하는 데이터를 연결하는 구조
• 삭제와 추가가 빠르다.
• 그대신 index로 탐색하는 방식이 아니라 처음부터 n번까지 따라가야됨. 접근 시간이 오래걸린다.

class Node{
    Node next;
    Object obj;
}

데이터의 개수가 변하지 않는 경우 ArrayList > LinkedList
데이터의 개수가 자주 변한다면 LinkedList > ArrayList