리스트(List)

리스트의 정의

배열이 가지고 있는 인덱스라는 장점 대신, 빈틈없는 데이터의 적재라는 장점을 취한 선형자료구조

→ 하지만, 메모리에서 순차성을 보장하지는 못하기 때문에 locality는 보장되지 않는다. 따라서 cash hit가 어렵다.

java에서의 list

java에서 List를 구현하여 사용할 수 있는 방법은 두가지로 나뉜다.

링크드리스트(LinkedList)

연결로 구현한 리스트

시간복잡도

추가/삭제: O(1)

접근: O(n)

어레이리스트(ArrayList)

배열을 이용하여 리스트를 구현한 것

시간복잡도

추가/삭제: O(n)

접근: O(1)

array(배열)와 arrayList의 차이점

array는 사이즈를 고정으로 사용하기 때문에, 사이즈 변경이 필요하다면 새로 선언해야한다.

arrayList는 리스트가 꽉차면, 사이즈를 동적으로 늘려준다.

java가 arrayList를 동적으로 늘리는 방법?

동적으로 늘리는 방식을 흐름대로 살펴보자면,

add()를 통해 새로 들어오는 값을 list에 추가한다. 그때 들어가는 위치가 마지막이라면 grow()를 호출한다.

grow는 list 사이즈가 java에서 정해놓은 최소값보다 작다면 최소값으로 만들어주고, 그 이상의 값이라면 1.5배만큼 list size를 증가시킨다.

만약 사이즈를 증가시킬 때, java에서 정해놓은 MAX size보다 크다면 에러를 띄운다.

arrayList와 linkedList 비교

삽입과 삭제는 linkedList가 훨씬 빠르지만, 조회를 할 때는 arrayList가 훨 낫다.

만약 조회가 많은 서비스라면 arrayList가, 삽입과 삭제가 많은 linkedList가 더 적합하다!