세 자료구조를 한 문장으로 정의하면 아래와 같이 말할 수 있다.
- Array는 index로 빠르게 값을 찾는 것이 가능함
- LinkedList는 데이터의 삽입 및 삭제가 빠름
- ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림
좀 더 자세히 비교하면?
우선 배열(Array)는 선언할 때 크기와 데이터 타입을 지정해야 한다.
int arr[10];
String arr[5];이처럼, array은 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조다.
-
따라서 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합하다.
-
또한 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적이다.
-
4번째 index 값에 새로운 값을 넣어야 한다면? 원래값을 뒤로 밀어내고 해당 index에 덮어씌워야 한다. 기본적으로 사이즈를 정해놓은 배열에서는 해결하기엔 부적합한 점이 많다.
-
대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다.
이를 해결하기 위해 나온 것이 List다.
List는 array처럼 크기를 정해주지 않아도 된다. 대신 array에서 index가 중요했다면, List에서는 순서가 중요하다.
-
크기가 정해져있지 않기 때문에, 중간에 데이터를 추가하거나 삭제하더라도 array에서 갖고 있던 문제점을 해결 가능하다. index를 가지고 있으므로 검색도 빠르다.
-
하지만, 중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재한다. (더하거나 뺄때마다 줄줄이 당겨지거나 밀려날 때 진행되는 연산이 추가, 메모리도 낭비..)
그렇다면 LinkedList는?
연결리스트에는 단일, 다중 등 여러가지가 존재한다.(Doubly, Circular 등 종류 다양)
종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있다.
단일은 뒤에 노드만 가리키고, 다중은 앞뒤 노드를 모두 가리키는 차이
이런 방식을 활용하면서, 데이터의 중간에 삽입 및 삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.
이렇게만 보면 가장 좋은 방법 같아보이지만, List의 k번째 값을 찾아라에서는 비효율적이다.
array나 arrayList에서 index를 갖고 있기 때문에 검색이 빠르지만, LinkedList는 처음부터 살펴봐야하므로(순차) 검색에 있어서는 시간이 더 걸린다는 단점이 존재한다.
