ArrayList
ArrayList는 배열을 기반에 두고있다.
장점 : 인덱스를 통한 데이터의 삽입,삭제,조회가 편하다.
단점 : 데이터의 추가,삭제가 느리다.
![[Java] ArrayList, LinkedList - ArrayList [Java] ArrayList, LinkedList - ArrayList](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
get / set
ArrayList는 조회 또는 값설정할때 시간복잡도는 O(1) 이다.
배열의 인덱스를 통해 접근하는 방식이므로 속도가 빠르다.
ArrayList.add(data)
List<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
맨뒤에 데이터가 추가된다.
시간복잡도는 O(1)이다.
ArrayList.add(index,data)
numbers.add(0, 11);
원하는 인덱스에 데이터를 삽입한다.
특정 인덱스에 데이터를 삽입하게되면 그 뒤에 요소들은 하나씩 뒤로 이동시켜주는 작업이 추가되므로
O(n)의 시간복잡도를 가지게 된다.
![[Java] ArrayList, LinkedList - ArrayList.add(index,data) [Java] ArrayList, LinkedList - ArrayList.add(index,data)](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
특정데이터삭제
List<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(1);
numbers.add(4);
numbers.remove(0);
numbers.remove(Integer.valueOf(2));
![[Java] ArrayList, LinkedList - 특정데이터삭제 [Java] ArrayList, LinkedList - 특정데이터삭제](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
1. ArrayList.remove(index) : 인덱스를 입력하여 삭제
위에 코드예시에서 0을 입력하여 인덱스 0의 값인 5를 삭제해줬다.
2. ArrayList.remove(Object) : 객체를 입력하여 해당 객체 삭제
위에 코드예시에서 Integer 2를 입력하여 2객체값을 삭제해줬다.
삭제또한 삽입과 마찬가지로 O(n)
![[Java] ArrayList, LinkedList - 삭제또한 삽입과 마찬가지로 O(n) [Java] ArrayList, LinkedList - 삭제또한 삽입과 마찬가지로 O(n)](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
중간에 삭제된 데이터의 자리를 매꾸기 위해 나머지값들이 앞으로 전진할것이므로 시간복잡도 O(n)
맨뒤에 값이 삭제된 경우는 O(1)?
LinkedList
LinkedList는 각 노드가 서로 연결되어있는 형태이다.
장점 : 데이터의 추가,삭제가 빠르다.
단점 : 검색이 느리다.
![[Java] ArrayList, LinkedList - LinkedList [Java] ArrayList, LinkedList - LinkedList](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
get / set -> O(n)
조회 또는 값 설정
연결 리스트의 형태를 띄고있기에 원하는값까지 시작이나 끝에서부터 이동하는데 걸리는 시간복잡도는 O(n)이다.
데이터 삽입 O(1) , O(n)
![[Java] ArrayList, LinkedList - 데이터 삽입 O(1) , O(n) [Java] ArrayList, LinkedList - 데이터 삽입 O(1) , O(n)](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
LinkedList는 ArrayList와 다르게 중간삽입이 발생하여도 참조하고 있는 다음노드를 새로 삽입된 노드로 바꿔주는
작업만 하면 되기때문에 O(1)의 시간 복잡도를 가진다. ( 맨앞을 삽입하는경우 O(1) == head 노드를 이용하면 되므로,
맨뒤를 삽입하는경우 O(1) tail 노드를 사용하면 되므로 ))
그게아닌경우는 O(n)
(삽입하는 행위 자체는 O(1)이고, 해당 노드까지 이동하는데 O(n)가 걸린다.)
맨앞, 맨뒤는 이동하는데 O(1))
데이터 삭제 O(1) , O(n)
![[Java] ArrayList, LinkedList - 데이터 삭제 O(1) , O(n) [Java] ArrayList, LinkedList - 데이터 삭제 O(1) , O(n)](https://blog.kakaocdn.net/dn/SbJT8/btrSJXwhyHp/0HSlKWM0f0OLDT17LK2QOk/img.png)
데이터 삭제 또한 삭제노드 이전노드의 다음노드를 삭제노드 다음노드와 연결시켜주면 되므로
O(1)의 시간복잡도를 가진다. ( 맨앞을 삭제하는경우 O(1))
그게아닌경우는 O(n)
시간복잡도 비교
![[Java] ArrayList, LinkedList - 시간복잡도 비교 [Java] ArrayList, LinkedList - 시간복잡도 비교](https://blog.kakaocdn.net/dn/Rl0oL/btrSISPYRu1/XYMQZFfKXA89zBEIMxS6l1/img.png)
선택하기
ArrayList
일반적으로 get/set을 자주 사용한다면 -> ArrayList
(배열처럼 인덱스를 가지고 접근하니까 속도가 빠름)
값의 조회, 값의 수정 -> 인덱스를 가지고 접근하니까 O(1)
값의 추가 -> 맨뒤에 추가할때는 O(1) (다른 데이터를 옮길필요가 없으므로)
맨 앞 또는 다른곳에 추가하고 싶을때는 O(n) 이다. (데이터를 해당 인덱스에 옮기고 그 뒤에 데이터들을 한칸씩 뒤로 이동시켜야하므로)
값의 삭제 -> 맨뒤를 삭제할때는 O(1) ( 삭제후 다른 데이터를 옮길필요가 없으므로)
맨 앞 또는 다른곳을 삭제하고 싶다면 O(n) (해당 위치의 데이터를 삭제하면 그 뒤에 데이터들을 한칸씩 앞으로 이동시켜야하므로)
LinkedList
처음이나 끝에 잦은 삽입,삭제가 발생한다면 -> LinkedList
(노드의 연결상태만 바꿔주면 되니까 속도가 빠름)
큐는 linked List를 이용한다.
값의 조회 및 수정 -> 연결리스트라 원하는값이 나올때까지 이동해야하므로 O(n)이다.
값의 추가 -> 노드가 연결된 그림이고, head,tail을 사용할것이기 떄문에 앞뒤에 값을 추가하는것은 O(1)이다.
노드를 추가하고 연결시키는것만 하면되니까.
하지만 어떤 인덱스(순서)까지 이동하려면 연결된 노드들을 지나서 가야하므로 O(n) 거기다가 추가하는 작업 O(1) 해서 O(n+1) -> O(n)
(head, tail을 이용하여)
값의 삭제 -> 삭제도 추가와 같은 이유로 앞뒤는 O(1) 다른 위치는 O(n)
출처,더 자세한정보
https://webprogramcustom.tistory.com/47
java ArrayList, LinkedList
ArrayList, LinkedList 이번엔 java의 List를 한번 알아보겠습니다. List란? List 인터페이스는 java의 Collection을 확장한 인터페이스 입니다. index를 기반으로 list가 구성됩니다. ArrayList ArrayList는 배열(array)을...
webprogramcustom.tistory.com
https://girawhale.tistory.com/8
ArrayList와 LinkedList의 차이, 선택하기
알고리즘 문제를 풀면서 List를 사용해야 되는 일이 자주 발생한다. 차이를 알아보고 효율적인 Collection을 선택해보자 ArrayList 구조 ArrayList는 내부적으로 배열의 형태를 지니고 있다. get / set 배열...
girawhale.tistory.com
'자바 > 자료구조' 카테고리의 다른 글
[Java] 우선순위 큐 (Priority Queue) (0) | 2022.12.24 |
---|---|
[Java] Heap, 힙 , 트리, 이진트리, 완전 이진트리 (0) | 2022.12.24 |
[Java] Stack, 스택 (0) | 2022.12.20 |
[Java] Set [HashSet] (0) | 2022.12.05 |
[Java] HashMap (1) | 2022.12.04 |
댓글