arraylist linkedlist 시간복잡도

 

 

ArrayList, LinkedList

 

이번엔 java의 List를 한번 알아보겠습니다.

 

List란?

List 인터페이스는 java의 Collection을 확장한 인터페이스 입니다.

index를 기반으로 list가 구성됩니다.

순서를 가지며 추가, 탐색이 가능합니다.

ArrayList

ArrayList는 배열(array)을 기반으로 두고 있습니다.

장점

• 데이터에 순서가 있음
• 데이터의 중복 저장 허용
• index를 통한 검색 빠름

단점

• 데이터 추가, 삭제가 느림

ArrayList의 데이터는 위와같이 저장되고 관리됩니다.

 

데이터의 일반적인 삽입 O(1)

ArrayList<String> ar = new ArrayList<>();
ar.add("data");
ar.add("data2");

일반적인 add의 경우 마지막에 데이터가 삽입되며 시간복잡도는 O(1) 입니다.

 

데이터의 특정 index 삽입 O(n)

데이터의 index 삽입은 ArrayList에서 좋은 성능을 기대하기 힘듭니다. 위의 그림과 같이 특정 index에 삽입되게 되면 뒤에 있는 요소들을 하나씩 뒤로 이동시켜 주는 작업이 추가되기에 O(n)의 시간복잡도를 가지게 됩니다.

 

데이터의 특정 index 삭제 O(n)

데이터의 삭제 또한 삽입과 같은 맥락입니다. 중간에 삭제된 데이터의 자리를 매꾸기 위해 뒤에 있는 요소들의 자리를 한칸씩 앞으로 이동시켜 주는 작업이 추가되기에 O(n)의 시간복잡도를 가지게 됩니다.

 

LinkedList

LinkedList는 각 노드(node)가 서로 연결되어 있는 형태입니다.

장점

데이터의 추가, 삭제가 빠름 O(1)

단점

검색이 느림 O(n)

 

LinkedList는 위와 같은 형태로 현재 노드와 다음노드를 참조하여 관리됩니다.

 

데이터의 삽입 O(1)

LinkedList는 ArrayList 와 다르게 중간삽입이 발생하여도 참조하고 있는 다음노드를 새로 삽입된 노드로 바꿔주는 작업만 일어나기 때문에 O(1)의 시간 복잡도를 가집니다.

 

데이터의 삭제 O(1)

데이터의 삭제 또한 참조된 삭제 노드를 그 다음노드로 바꾸어 주면 됩니다. 그렇기에 O(1)의 시간 복잡도를 가집니다.

 

하지만 여기서 간과하지 말아야 할 것이 있습니다. LinkedList의 경우 삽입과 삭제를 위해서는 해당 노드까지 이동하는 작업이 필요합니다. 그렇기에 O(n)의 시간복잡도를 가지는 이동시간이 추가 될 수 있다는 것 입니다. 많은곳에서 설명하기를 단순 삽입과 삭제가 O(1)의 시간복잡도만 가지고 있다고 말하고 있습니다. 하지만 해당 노드까지 이동하는 작업을 생각한다면 단순 ArrayList보다 성능이 좋다고 말하기도 힘듭니다.

친절하게도 java에서 구현된 LinkedList 에서는 추가 또는 삭제될 자리를 빠르게 이동하기 위해 head(처음) 에서 해당 자리를 찾거나 tail(마지막) 노드에서 출발하여 해당하는 노드의 위치까지 이동합니다. 그러기에 O(n/2) 이 보장되는 것으로 보입니다.

 

위의 설명을 토대로 시간복잡도를 나열 해 보자면

ArrayList

• 삽입/삭제 위치 찾기 O(1)
• 삽입/삭제 수행 O(n)

LinkedList

• 삽입/삭제 위치 찾기 O(n)
• 삽입/삭제 수행 O(1)

https://wlswoo.tistory.com/58

참고:https://yeon-kr.tistory.com/152

(Java)ArrayList vs LinkedList 시간 복잡도

결론:arraylist는 array 를 사용하기에 메모리에 연속적으로 데이터가 할당이 되어서
index를 통해서 해당 값을 찾는게 시간이 빠르다.0(1)

하지만 linkedlist는  메모리가 불연속적으로 할당이 되어서 노드를 통해 연결이 
되다 보니 해당 인덱스에 가기 위해서 는 노드를 통해서 순차적으로 접근을 해야 한다.
그렇다보니 arraylist에 비해 참조가 느리다.O(n)

하지만 arraylist는  메모리를 연속적으로 배치하다보니 메모리를 효율적으로 사용하지 못하는 단점이 있고,
중간에 데이터 삽입시에 나머지 값을 뒤로 복사후에 null값으로 바꾸고 배열길이를 삭제 해야 하는 
작업들이 있어서 시간 복잡도가 O(n)이된다.
하지만 LinkedList는 노드값만 변경해 주면되기에 arraylist에비해서 더 효율 적이다.

만약 일반적인 삽입,삭제 시에는 array는 값을 넣는 것이 메모리 주소값을 통해 넣다보니 O(1)이다. 하지만 할당된 메모리를 초과 할시는 새로운 배열을 또 생성해서 복사해야 하기 에 O(n)이 된다.
LinkedList도 오직 삽입시에는 O(1)이된다.