99클럽 코테 스터디 17일차 TIL + ArrayList vs LinkedList

학습 키워드

ArrayList vs LinkedList

 

공부한 내용

ArrayList vs LinkedList

• LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성한 이유는 ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.

ArrayList LinkedList

컬렉션 구성	배열을 이용	노드를 연결 (linked)
데이터 접근 시간	모든 데이터 상수 시간 접근	위치에 따라 이동시간 발생
삽입 / 삭제 시간	삽입/삭제 자체는 상수 시간	삽입/삭제 자체는 상수 시간
삽입 / 삭제 시간	삽입/삭제 시 데이터 이동이 필요한 경우 추가시간 발생	삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리사이징 필요	공간이 부족할경우 새로운 배열에 복사하는 추가 시간 발생	-
데이터 검색	최악의 경우 리스트에 있는 아이템 수 만큼 확인	최악의 경우 리스트에 있는 아이템 수 만큼 확인
CPU Cache	캐시 이점을 활용	-

ArrayList의 문제점

• ArrayList는 배열 공간(capacity)가 꽉차거나, 요소 중간에 삽입을 행하려 할 때 기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.
• 이러한 부가적인 연산은 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적일 수 있다. 그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 되고 또한 리사이징 처리에서 시간이 소모된다.

LinkedList의 장단점

• LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(Link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며, 삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다. 따라서 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현하는 것이 바람직하다.
• 그러나 LinkedList에도 단점이 존재하는데 요소를 get하는 과정에서 ArrayList와 굉장한 성능 차이를 보인다. ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access)만 가능하다.
• 예를 들어 n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다.
• 그래서 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 있어 ArratList보다 당연히 긴 지연 시간이 소모되게 된다. 특히 Singly LinkedList는 단방향성만 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 접합하지 않다.
• LinkedList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 하는 점이다. 배열 같은 경우 그냥 데이터 그대로만 정장하면 되지만, LinkedList의 노드 같은 경우 데이터 이외에 next 나 prev 같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요할 수 밖에 없다.

LinkedList 장점 LinkedList 단점

자료의 삽입과 삭제가 용이	포인터의 사용으로 인해 저장 공간의 낭비
리스트 내에서 자료의 이동이 불필요	알고리즘이 복잡
사용 후 기억 장소의 재사용이 가능	특정 자료의 탐색 시간이 많이 소요
연속적인 기억 장소의 할당이 불필요

LinkedList vs ArrayList 성능 비교

시간 복잡도 비교

• LinkedList를 처음 배울 때 요소를 추가하는 것과 요소를 삭제하는 것의 시간 복잡도가 오로지 O(1) 이라는 점이다. 맨 앞이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 시간복잡도는 O(1)이 맞지만, 중간에 요소를 추가 / 삭제 한다면 그 중간 위치까지 탐색을 해야 하므로 최종적으로 O(N)이 된다.

• 그래도 탐색 시간(search time)에 시간이 그리 소요되지않으면 ArrayList보다 삽입 속도가 빠르기 때문에 표기만 저렇지 왠만한 상황에선 LinkedList가 ArrayList보다 우위로 보면 된다.

• 위의 표에서 ArrayList에서 첫번째 삽입이 O(N)인 이유는 무조건적으로 요소들을 뒤로 이동해야 되기 때문이다. 그리고 마지막 위치 삽입이 O(1) 또는 O(N)이 되는 이유는 만일 공간 부족으로 인해 배열 복사가 일어나면 시간이 소요되기 때문이다.

LinkedList는 의외로 잘 사용되지 않는다

• 보통 ArrayList 와 LinkedList 중에 어느걸 사용하면 되냐고 묻는다면, 삽입 / 삭제가 빈번하면 LinkedList를, 요소 가져오기가 빈번하면 ArrayList를 사용하면 된다 라고들 가르쳐 주지만, 사실 성능면에서 둘은 큰 차이가 없다.
• 예를들어 ArrayList는 리사이징 과정에서 배열 복사하는 추가 시간이 들지만, 배열을 새로 만들고 for문을 돌려 기존 요소를 일일히 대입하는 그러한 처리가 아니라, 내부적으로 잘 튜닝이 되고 최적화 되어있어 우리가 생각하는 것처럼 전혀 느리지 않다.
• 위의 성능 코드 예시 역시 두각을 나타내기 위해 극단적으로 나노초로 비교해서 차이가 확연히 보여서 그렇지 체감상 차이가 그리 큰 편도 아니다.
• 몇몇은 FIFO(선입선출)이 빈번할 경우, ArrayList 경우 첫번째에 요소를 추가할 때마다 자주 데이터 이동(shift)가 일어나기 때문에 큐(queue)를 사용해야 할때 LinkedList를 사용한다 라고 말하지만, 차라리 그런경우엔 따로 ArrayDeQue라는 더욱 최적화된 컬렉션을 쓰는 것이 훨씬 좋다.

 

회고

발생한 문제

- LinkedList 와 ArrayList 의 차이에 대해 알아보았다. 

 

해결 방법

- LinkedList 와 ArrayList의 차이에 대해 공부해보았다.

 

알게된 내용

- LinkedList 와 ArrayList 의 차이와 대부분 ArrayList를 사용한다는 사실을 알게 되었다. 

 

 

참고 자료

- https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-ArrayList-vs-LinkedList-%ED%8A%B9%EC%A7%95-%EC%84%B1%EB%8A%A5-%EB%B9%84%EA%B5%90