List(리스트)

List

값(value)들을 저장하는 추상자료형(ADT)을 의미하며, 순서가 있고 데이터의 중복을 허용한다.
set이나 map을 사용하는게 더 적절한 상황이 아니면 대부분 list를 사용한다고 봐도 무리 없다.

list 구현체

• ArrayList
• LinkedList

ArrayList

배열(Array)을 사용하여 list를 구현한다. 그렇기에 데이터 삽입 시 배열의 크기를 초과한다면 2배의 배열을 만든 뒤 배열값을 카피한다. 그 후 데이터를 삽입한다.

ex) 배열의 크기 4 / [1,2,3,4] -> 5 삽입 → 크기가 8인 배열 생성 후 카피 → [1,2,3,4, , , , ] → 데이터 삽입 [1,2,3,4,5, , , ]

LinkedList

노드를 연결(linked)시키는 형태로 구현한다. 노드에 값을 저장하는 공간과 다음 노드를 가르키는 포인트가 할당된다. 마지막 노드(tail)는 null을 가르킨다.

ex) 데이터 10 삽입 → 10,null(head,tail) → 10 뒤에 데이터 20 삽입 → (10,20의 노드(head)→20,null(tail)) → 맨 앞에 30 삽입 → (30,10의 노드(head)→10,20의 노드→20,null(tail))

인덱스 호출 시 head부터 출발하여 포인트를 따라 이동하여 호출한다.
인덱스를 사용하여 바로 접근되는 array와 다르게 head부터 이동해야 하기 때문에 시간적 딜레이가 발생한다.

ArrayList와 LinkLise의 차이

ArrayList

• 배열을 사용하여 연속적인 메모리 공간에 데이터를 저장한다
• 데이터 접근 시, 모든 데이터 상수 시간 접근
• 삽입, 삭제 시 데이터 시프트가 필요한 경우 추가시간 발생
• CPU cache 이점 활용 가능하다.

LinkedList

• 노드 각각이 포인트를 이용해서 다음 노드를 가르키기에 메모리 공간에서 따로따로 저장된다.
• 데이터 접근 시, 위치에 따라 이동 시간 발생
• 삽입, 삭제 위치에 따라 해당 위치까지 이동하는 시간 발생

공통점

• 데이터 검색 시, 최악의 경우 리스트에 있는 아이템 수 만큼 검색 시간 소요
• 데이터의 삽입,삭제 자체는 상수 시간 소요

프로젝트의 요구 사항에 따라 적재적소에 필요한 List의 사용이 필요할 것 같다.