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

위와 같은 결과가 될것입니다. 여기에서 LinkedList가 우위를 점할수 있는 상황은 여러개의 노드를 삽입 또는 삭제할때 만약 3개의 노드 삽입이 한번에 이루어진다고 가정 해 보겠습니다.

 

3개의 노드 삽입이 이루어질때

ArrayList

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

LinkedList

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

위의 표현이 맞을지 모르겠으나 LinkedList의 경우 각각의 삽입 위치를 찾을때마다 삽입을 해줄 수 있기 때문에 위와같은 우위를 점할 수 있다는 점입니다.

 

java의 List에 대해 알아보았습니다. 알고 있는 내용이었지만 포스팅하며 좀더 자세히 조사해보는 시간을 갖게된것 같습니다.

틀린 내용은 지적 부탁드리며 읽어주셔서 감사합니다.