[Java] ArrayList, LinkedList

ArrayList

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)의 시간복잡도를 가지게 된다.

특정인덱스에 데이터가 삽입 -> 뒤에 데이터 뒤로 이동

 

특정데이터삭제

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));

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

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

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

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

 

 

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

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

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

 

---

LinkedList

 

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

 

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

단점 : 검색이 느리다.

 

 

get / set  -> O(n)

조회 또는 값 설정

 

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

 

 

 

 

데이터 삽입 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)

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

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

 

그게아닌경우는 O(n)

 

 

시간복잡도 비교

 

 

 

선택하기

 

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

https://girawhale.tistory.com/8

ArrayList와 LinkedList의 차이, 선택하기