📚 Array & ArrayList & LinkedList
1. Array (배열)
메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 순차 자료 구조
-
논리적인 저장 순서와 물리적인 저장 순서가 일치한다.
-
index로 해당 원소에 접근하여 빠르게 값을 찾는것, Random Access가 가능하다.
-
데이터에 접근하는 Search 시간 복잡도 = O(1)
-
삽입, 삭제는 비효율적, 원래값을 뒤로 밀어내고 index에 덮어씌운다.
시간복잡도는 Shift 비용으로 worst case O(N) -
배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다.
2. ArrayList (배열 리스트)
ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느리다.
Array와 ArrayList의 차이점은 동적인가 정적인가에 있다. ArrayList 는 사이즈가 동적인 배열이다.
ArrayList에서 기존 크기를 초과하지 않을 경우, 삽입을 할때 가장 마지막 노드에 원소가 삽입된다.
반대로 ArrayList가 기존의 크기를 초과할 경우, {기존 배열 크기 + 기존 배열의 크기 / 2} 만큼 늘어난 배열에 기존 원소를 복사해 온다.
ArrayList 는 빈 element를 허용하지 않아, element 삭제의 경우 빈공간을 메꾸기 위해 뒤에 원소들을 앞으로 당겨 오고, worst case 시간복잡도는 O(N)이고, 성능 저하를 일으킬 수 있다.
시간 복잡도
1) 원소 찾기 : O(1)
2) 마지막 노드에 원소 추가/삭제 : O(1) or O(N)
3) 마지막 노드 이외의 위치에 원소 추가/삭제하기 : O(N)
4) List의 크기 구하기 : O(N)3. LinkedList (연결 리스트)
List는 Array와 달리 크기를 정해줄 필요가 없고, 순서가 중요한 자료구조
LinkedList는 각각의 원소들이 자기 자신 다음이 어떤 원소인지만 기억한다.
따라서, 데이터의 삽입 및 삭제가 빠르다.
-
배열과 다르게 논리적 저장순서와 물리적 저장 순서가 다르다
-
중간에 데이터 삽입, 삭제를 하는게 빠르다.
-
하지만 원소 찾기를 하기 위해서는 첫번째 원소부터 차례로 살펴봐야 하므로 검색에 있어서는 시간이 더 오래 걸린다.
시간복잡도
1) 임의의 위치 원소 찾기 : O(N)
2) 마지막 노드에 원소 추가/삭제 : O(1)
3) 마지막 노드 이외의 위치에 원소 추가/삭제하기 : O(1)
4) List의 크기 구하기 : O(1) or O(N)🔗 참조한 사이트
https://gwang920.github.io/datastructure/Array-ArrayList-LinkedList-%EB%B3%B5%EC%82%AC%EB%B3%B8/
