Array 와 ArrayList 와 LinkedList 의 차이

/*

서론. 

자료구조를 공부하면서 Array를 배웠고, LinkedList를 구현하는 법도 배웠다. 

JAVA 수업을 들으면서 ArrayList를 사용했다.  

얼핏 기억하고 있던 각 자료구조의 특징은 다음과 같다.

• Array는 index로 빠르게 값을 찾을 수 있다.
• LinkedList는 데이터를 삭제하고 삽입하는데 빠르다
• ArrayList는 데이터를 찾는데 빠르지만 데이터의 삽입과 삭제가 느리다.

창피하지만 그 차이가 뭔지 와닿지가 않았고, 이해가지 않았다. 

DP로 자료구조 공부를하면서 이제야 조금 이해했다. 물론, 아직 다 이해하지 못했을 것이다.

이걸 그동안 몰랐다니 넘나 부끄럽지만 나중에라도 다시 이 바보스러움을 느끼기 위해 조금이나마 이해한 바를 정리해본다.

*/

1. array는 뭘까?

array는 뭘까? array는 배열이지. 

일반적으로 array는 array의 크기와 데이터 타입을 함께 선언해야 한다. 

이를테면, 이런식으로

int arr[6]; 

String arr[12];

array는 왜 선언하기 전에 자료형과 사이즈를 함께 적어줘야할까? 뭐 배열이 커질수도 있구 어떻게 될지 알지도 못하는 일인데 말이다.

int arr[6]을 예로 들면, 괄호 안 6은 배열의 길이를 뜻한다. int형 데이터가 들어갈 공간 6개가 메모리 공간에 할당된 것이다.

즉, 특정 자료형의 변수가 들어갈 공간을 몇개나 할당할지를 정한다. 

array는 데이터를 줄줄이 저장한다. 그래서 각 데이터가 줄줄이 저장될 것이기 때문에 자료형을 미리 적어주어야 한다. 

array는 데이터를 찾는게 빠르다. 

왜? index가 있으니까. 이 array는 데이터를 줄줄줄 저장하다 보니까. 위치를 바로 알 수가 있다. 

내가 arr[4]를 찾는다고 하면 arr라는 것의 주소값에서 바로 +4만해서 찾으면 되니까. 검색이 빠르다. 

array[4]에다가 t새로운 값을 넣으면 어떻게 될까? 덮어씌워진다. 

array[4]를 삭제하면 어떻게 될까? 그냥 텅 비어있을 뿐이다. 

그래서 arrayList가 나오게 된다. 

2. List는 뭘까?

나는 넘나 헷갈렸었다. 무엇이? array나 list나 그게 뭔 차이가 있는 건지.

array와 list의 가장 큰 차이점은. 

array는 크기를 정해주어야 한다는 것. index가 중요하다는 것. 

list는 크기가 정해지지 않아도 된다는 것. 순서가 중요하다는 것이다. 

이 차이를 알기 위해 arrayList를 보자.

array에서는 arr[4]에 새로운 값을 대입하면 덮어씌워진다.

array에서는 arr[4]를 삭제하면 텅비어있다. 

arrayList에서 만약 arrList.add()하면 어떻게 될까? 4번째 에다가 더한다면? 그러면 얘는 4번쨰에 들어간다. 

arrayList.remove()하면 어떻게 될까? 다 줄줄이 당겨진다. 

그래서 arrayList에서 값을 맨앞에 넣거나 맨뒤에 넣으면 상관이 없는데 중간에 값을 더하거나, 빼면 오래걸리는 거다. 

대신 array의 성질, 즉 index를 그대로 가지고 있기 때문에 자료를 검색하는데는 빠르다. 

List는 크기를 미리 정해줄 필요가 없다. 쭉쭉 이어진다. 

LinkedList는 그럼 어떨까?

단일 연결리스트, 다중 연결리스트 등. 여러 Linked list가 존재한다. 

단일이든, 다중이든 링크드 리스트는 한 노드에 연결될 노드의 포인터 위치를 가르킨다. 

다중은 앞뒤 모두 다 가르키는 거고, 단일은 뒤에것만 가르키는 거구 

이렇게 되니까, 데이터를 중간에 넣고 뺀다고 해도 이전에 가르치는 값, 다음 값이 가르켰던 값만 연결시켜주면 되니 빠르다.

그렇지만 11번 째 값을 찾는다고 생각해보자. 

그러면 얘는 맨처음부터 굽이굽이 건너가야 한다. 그래서 값을 찾는데는 arrayList나 array보다는 좀 걸린다.