자바/자료구조

[Java] ArrayList, LinkedList

backend dev 2022. 12. 3.

ArrayList

ArrayList는 배열을 기반에 두고있다.

 

장점 : 인덱스를 통한 데이터의 삽입,삭제,조회가 편하다.

단점 : 데이터의 추가,삭제가 느리다.

 

 

[Java] ArrayList, LinkedList - ArrayList
내부적으로 다음과 같은 배열의 형태를 띄고있다.

 

 

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)
특정인덱스에 데이터가 삽입 -> 뒤에 데이터 뒤로 이동

 

특정데이터삭제

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 - 특정데이터삭제

1. ArrayList.remove(index) : 인덱스를 입력하여 삭제

위에 코드예시에서 0을 입력하여 인덱스 0의 값인 5를 삭제해줬다.

2.  ArrayList.remove(Object) : 객체를 입력하여 해당 객체 삭제

위에 코드예시에서 Integer 2를 입력하여 2객체값을 삭제해줬다.

 

 

삭제또한 삽입과 마찬가지로 O(n)

[Java] ArrayList, LinkedList - 삭제또한 삽입과 마찬가지로 O(n)

중간에 삭제된 데이터의 자리를 매꾸기 위해 나머지값들이 앞으로 전진할것이므로 시간복잡도 O(n)

맨뒤에 값이 삭제된 경우는 O(1)?

 


LinkedList

 

LinkedList는 각 노드가 서로 연결되어있는 형태이다.

 

장점 : 데이터의 추가,삭제가 빠르다.

단점 : 검색이 느리다.

 

[Java] ArrayList, LinkedList - LinkedList

 

get / set  -> O(n)

조회 또는 값 설정

 

연결 리스트의 형태를 띄고있기에 원하는값까지 시작이나 끝에서부터 이동하는데 걸리는 시간복잡도는 O(n)이다.

 

 

 

 

데이터 삽입 O(1)  , O(n)

[Java] ArrayList, LinkedList - 데이터 삽입 O(1)  , O(n)

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)

데이터 삭제 또한  삭제노드 이전노드의 다음노드를 삭제노드 다음노드와 연결시켜주면 되므로

O(1)의 시간복잡도를 가진다.  ( 맨앞을 삭제하는경우 O(1))

 

그게아닌경우는 O(n)

 

 

시간복잡도 비교

 

[Java] ArrayList, LinkedList - 시간복잡도 비교

 

 

선택하기

 

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

댓글