칸비

개발 찍어먹기

[자료구조]-ArrayList와 LinkedList

ArrayList & LinkedList 비교

개념

자바에서 ArrayList와 LinkedList를 모두 지원한다 ArrayList와 LinkedList는 Java에서 제공하는 Collections으로 List 인터페이스를 상속한다.

ArrayList

  • 대량의 자료를 추가/삭제 하는 경우 대량의 데이터 복사가 많이 일어나게 되어 성능 저하
  • 하지만 데이터는 인덱스를 가지고 있기 때문에 데이터 검색에 유리

LinkedList

  • 데이터를 저장하는 노드가 이전 노드와 다음 노드의 상태만 알고 있다고 생각하면 된다.
  • 데이터 추가/삭제시 불필요한 데이터 복사가 없어 데이터 추가/삭제시 유리
  • 하지만 데이터 검색시 처음부터 노드를 순회해야 해서 성능 저하

검색

ArrayList

  • ArrayList는 LinkedList에 비해 굉장히 빠름(인덱스 기반 자료구조이기 때문) - O(1)의 시간 복잡도

LinkedList

  • 모든 요소 탐색 때문에 최악의 경우 - O(N)의 시간 복잡도

삽입 & 삭제

ArrayList

  • 데이터 삽입, 삭제 이후 다른 데이터를 복사해야 하기 때문에 최악의 경우 - O(N)의 시간복잡도

LinkedList

  • LinkedList에서 데이터 삽입, 삭제 시에는 ArrayList와 비교해 굉장히 빠름, 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문 - O(1)의 시간 복잡도

Stack API

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

ArrayList<T> list = new ArrayList<T>(); // 객체 선언
LinkedList<T> list2 = new LinkedList<T>(); // 객체 선언

list.add(E element) // 마지막에 원소 추가
list.add(int index, E element) // 지정된 인덱스에 원소 추가
list.size() // 크기를 integer형태로 반환
list.remove(int index) // 인덱스의 원소 삭제
list.clear();  // 모든 값 제거
list.get(int index); // 인덱스의 원소 반환
list.contains(E element); // list에 원소가 있는지 확인, 있으면 true반환
list.indexOf(E element); // 원소가 있는 인덱스 반환, 없으면 -1 반환
list.set(int index, E element) // 인덱스의 원소 변경

요약

  • 검색에는 인덱스가 있는 ArrayList가 유리하다
  • 삽입, 삭제에는 노드 링크만 바꿔주면 되는 LinkedList가 유리하다

참고