Array와 List

배열은 메모리에 연속적으로 데이터가 들어가는 자료구조.
int[] arr = {}; int형태이기때문에 4바이트의 방을 가지는 배열이 생성.

따라서 바이트단위의 주소가 4바이트씩 뛰게된다.

배열은 컴퓨터가 내부적으로 바이트의 크기가 정해져 있으므로
자료구조상에 위치를 인덱스 값만 알면 cpu가 계산을
데이터타입의 크기 * 인덱스값 하여 어느 자료구조보다 가장 빨리 위치를 알아낼 수 있다.

배열리스트에 추가적으로
하나를 add하면 기존의 배열 사이즈(2^n)만큼 확보해준다.
두번째로 하나더 add하면 2배의 배열을 확보해준다.
세번째로 하나더 add하면 4배의 배열을 확보해주고,
네번째로 하나더 add하면 8배의 배열을 확보해준다.
2의 배수로 배열이 증폭해서 만들어진다.
기존에 배열이 2개의 방이 있었을때 그다음 하나 추가하면 4개의 방을 만든다.
기존에 있던 2개를 복사해서 넣을 공간을 추가하기 위해서!

배열이라는 자료구조는 데이터 가져올때 어느 자료구조보다 빠르다.
arrayList는 배열을 사용하기때문에 리스트에 값을 추가(입력)할때 증폭해서 비용이 많이 들지만 데이터를 가져올때 빠르게 가져올 수 있으므로
arrayList를 가장 많이 사용한다.

이에 반해 입력을 빠르게 할 수 있는 자료구조로 linkedList가 있다.
링크드리스트는 배열이 아니라 아이템들로 이루어져 있다.
아이템은 메모리 상에서 각각 떨어져 있다.새로 입력되는 경우 아이템 하나가 더 추가될뿐이고 각각의 아이템들은 그 다음 아이템의 위치를 가지고 있을뿐이다.


왜 링크드리스트가 어레이리스트보다 입력이 빠른가?
예를 들어서 설명하자면, 백만개의 데이터가 있을때 백만한번째 데이터를 넣으려고 한다면
어레이리스트는 이백만개의 메모리를 확보하여 백만개를 복사해서 넣을것이다.
링크드리스트는 아이템하나만 투가해서 레퍼런스 꼬리값만 연결해주면 된다.
비용이 적고, 속도가 빠르다.


반대로 왜 어레이리스트가 링크드리스트보다 데이터를 가져오는것이 빠른가?
예를 들어 백만개의 데이터가 있을때 백만번째 데이터를  가져오려고 한다면
링트드리스트는 첫번째부터 100만번째까지 타고 가야 한다.
어레이리스트는 cpu가 100만(인덱스) X 데이터형의사이즈(바이트) 를 계산해서 빛의 속도로 가져온다.따라서 읽는 속도의 균일함(메모리의 균일한 접근시간)을 보장해준다.=성능upup

어레이리스트는 계산1번 메모리접근1번

링크드 리스트는 인덱스3번째를 가려면 

①일단한번 

②다음인덱스알아보기한번 

③다음인덱스한번 

④그다음인덱스알아보기한번 

⑤다음인덱스한번 

⑥다음인덱스확인한번 (총6번)
링크드리스트가 존재하는 이유는 데이터를 빠르게 입력하기위해사용하고
어레이리스트는 데이터를 빠르게 가져오기 위해서 사용한다.