[자료구조]ArrayList와 LinkedLis의 차이

김피자·2023년 3월 17일
0

자료구조

목록 보기
4/4
post-thumbnail

들어가기전

List<Integer> list = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();

위 코드는 같은 결과를 나타낸다.

list와 ArrayList의 차이는 뭘까

ArrayList는 클래스이고, List는 인터페이스다.

결론부터 적으면 List는 인터페이스고 ArrayList는 List에 상속된 클래스이다.

자바의 다형성에 의해 리스트를 List 자료형으로 선언한 경우, 그 구현체를 ArrayList로 구현할 수 있지만 LinkedList로도 구현할 수 있다.

그럼 ArrayList와 LinkedList의 차이는 뭘까?

List의 인터페이스 구현체로는 위에서 말한 ArrayList, LinkedList말고도 Stack, Vector 등이있다. 이 중에서 ArrayList와 LinkedList의 차이는 뭘까????


ArrayList

ArrayList는 중복을 허용하고 순서를 유지하며, 인덱스로 원소들을 관리한다는 점에서 배열과 유사하다.
배열은 크기를 지정해주어야하지만, ArrayList는 클래스이기 때문에 배열을 추가, 삭제할 수 있는 메소드 들이 존재한다. .add .remove

하지만 값을 추가했을 때 배열의 크기가 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우, 더 큰 용량의 배열을 만들어 옮기는 작업을 하게된다.

ArrayList 객체 생성 시 초기 용량을 설정하는 것이 좋다.

많은 원소들의 추가와 삭제가 진행되면 배열의 복사가 자주 발생할 것이다.
배열의 초기 용량을 미리 예상하는 것은 쉽지 않지만 대략적으로 초기 용량을 생각하고 그 예상치보다 살짝 더 여유있는 값으로 초기 용량을 설정하는 것이 좋다.

LinkedList


LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어있다.
참조하려는 원소에 따라 처음부터 순방향 혹은 역방향으로 순회할 수 있다.
(배열의 단점인 크기 변경 문제, 비순차적 데이터 추가, 삭제시 오랜 시간 소요되는 단점을 보완)


ArrayList와 LinkedList의 성능차이

  • 순차적으로 추가와 삭제를 하는 경우에는 ArrayList가 LinkedList보다 빠르다.
    마지막 요소부터 순차적으로 삭제할 경우, 각 요소들의 재배치가 필요하지 않기 때문에 더 빠른 성능을 보인다.
  • 중간 데이터를 추가/ 삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
    LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 빠르다.
    반면 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 느리다.

다루고자하는 데이터의 개수가 변하지 않는 경우라면 ArrayList를 선택!
데이터 개수의 변경이 잦다면 LinkedList를 선택하자!


출처
https://yoon-dailylife.tistory.com/7
https://kjw1313.tistory.com/16
https://dev-coco.tistory.com/19
https://devlog-wjdrbs96.tistory.com/64

profile
제로부터시작하는코딩생활

0개의 댓글