[Algorithms & Data structure] ArrayList VS LinkedList

Queue 문제를 풀때 LinkedList를 쓰는데 그냥 왜 쓰는지 궁금하기도 하고 쨋든 쓰는 이유를 알아야 하니 글을 끄적끄적 적어본다..

 

먼저 ArrayList와 LinkedList 각각에 대해 알아보자.

 

 

 

ArrayList 란?

중복을 허용하고 순서를 유지

Index로 원소들을 관리 배열과 상당히 유사

그러나 배열은 크기가 값이 고정적이지만 ArrayList는 클래스로 배열을 추가, 삭제, 할 수 있는 메소드들도 존재 -> 이때 배열이 동적으로 늘어나는 것이 아닌 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 함

add(E element) 

• 배열 마지막에 원소를 추가 --> 빠르다!

 

add(int index, E element)

• 배열에 마지막이 나닌 처음, 중간에 즉 원하는 위치에 넣을수 있으나 원소들을 뒤로 한칸씩 미뤄야 함 --> 느리다!

 

remove(int index)

• 마지막 원소는 쉽게 삭제 가능 but! 중간이나 처음 원소 삭제시 빈공간을 다시 채워야 해서 비효율적--> 느리다! 

 

get(int index)

• 배열은 인덱스에 해당하는 원소를 O(1)에 찾아올 수 있기 때문에 탐색에는 매우 유리

 

ArrayList 정리

• 탐색은 빠르게 할 수 있음
• 중간에서 추가, 삭제가 빈번하게 일어나면 비효율적인 특징을 가짐

 

 

LinkedList 란?

양방향 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향 도는 역순으로 순회가 가능

크기도 고정되어 있음 --> 새로운 배열을 생성해 복사해야 함 (느림)

중간에 추가 or 삭제 시 빈공간을 만들고 채우기 위해 데이터 이동이 필요

add(E element)

• 배열처럼 인덱스를 가지고 있지 않음 따라서 원소를 추가하기 위해서 Head에서 부터 마지막까지 찾아가야 함 --> 느리다!

 

add(int index, E element)

• Index를 지정해서 추가하는 것도 마찬가지로 해당 위치로 가려면 Head부터 탐색해야 가야함 --> 느리다!

 

remove(int index)

• 원소 삭제 시 배열의 경우 배열의 경우는 삭제하면 빈 공간을 다시 채워주는 작업이 필요 but 삭제 시 원소 앞 or 뒤로 가서 가르키는 값을 null로 바꿔주면 됨

 

get(int index)

• ArrayList와 다르게 Index 통해 검색을 하는게 아님 Head에서 부터 해다 원소까지 검색해야함

 

성능 차이 결론

• 순차적으로 추가 or 삭제하는 경우 ArrayList가 LinkedList보다 빠르다.
• 중간 데이터를 추가 or 삭제하는 경우 LinkedList가  ArrayList보다 빠르다.

 

 

 

시간복잡도

 

그렇다면 Queue에서 LinkedList를 사용하는 이유는 ? 

Queue는 선입선출 즉, FIFO구조로 만약 ArrayList를 사용하게 된다면 어떨까?

맨 앞에 것을 꺼내야하는데, 꺼내고 나면 그 앞자리를 채우기 위해 모든 원소들을 한 칸씩 앞으로 옮겨야한다.

원소의 수가 많아지면 그만큼 비효율적인 것이다.

그렇다면 LinkedList를 사용하면 어떨까?

LinkedList의 remove 함수 설명을 보면 '빈 공간을 채울 필요가 없다'고 되어 있으므로, 삭제하고 싶은 원소를 null로 변경하기만 하면 되기때문에 매우 효율적이다.