7주차, 자료구조 배열 리스트 (ArrayList)

list

・ 선형적인 자료구조

・ 데이터를 일렬로 늘여놓은 형태

・ 순서

 

list의 연산

・ 데이터 삽입

・ 데이터 삭제

・ 데이터 탐색 

 

list의 종류

・ ArrayList

・ LinkedList

  ・ Single Linked List

  ・ Double Linked List

 

ArrayList는 자바에서 이미 구현되어 있다.

・ 배열 기반 리스트

・ 메모리 공간을 연속적으로 사용

 

List<원하는 자료형> 변수 이름 = new ArrayList<>();

list.add(??); 로 추가가 가능하다.

 

list.remove(??); 로 삭제가 가능하다.

 

list.get(인덱스) 로 인덱스 번호로 데이터를 받을 수 있다.

 

만약 데이터를 추가할 경우, 원하는 위치에 집어넣는 대신, 그 뒤에 있는 데이터는 다 밀려나게 된다.

뒤에 있는 데이터가 n개면 n번 이동하기에 시간복잡도는 O(N)이 된다.

 

이렇게 미는 과정 없이 그냥 넣게되면 기존 인덱스칸의 내용이 없어진다.

 

삭제할 때도, 데이터를 안쪽으로 땡겨오는 작업이 필요하고, 여기서도 인덱스 위치로부터 뒤에있는

양만큼 O(N)의 시간복잡도가 된다.

 

데이터를 탐색할 경우, 인덱스에 랜덤 엑세스를 하기 때문에 데이터가 아무리 많아도 한번에 찾는

O(1)의 시간복잡도가 된다.