배열
장점
n번쨰 요소 데이터 접근이 빠르다.
단점
- 크기를 변경할 수 없다 배열은 크기가 고정돼서 부족하지 않도록 크게 잡으면 메모리가 낭비됨
- 중간에 있는 데이터를 삭제,추가 하려면 뒤에있는 데이터를 앞으로 또는 뒤로 옮기는 과정이 실행되면서 오래걸린다.
ArrayList
배열기반으로 구현된다. ArrayList의 생성자의 parameter에 초기 크기값을 받을 수 있다.
초기 크기값 보다 많은 데이터를 넣으려고 할 때 발생하는 과정
- 기존 크기보다 더 많이 담아야하면 기존 크기의 2배만큼 메모리 공간을 할당 받는다.
- 기존 배열에 있던 데이터를 2배크기의 새로 할당받은 배열에 복사한다. - - 원래 참조변수가 새로 할당받은 배열을 가리키도록 참조 변경한다.
단점 - 중간에 있는 데이터를 추가/삭제 하려면 그 뒤에 있는 데이터들을 뒤로 또는 앞으로 한칸 씩 옮겨야한다. (배열 기반이라 배열과 단점이 같다)
LinkedList
배열의 단점을 보완한 리스트이다.
(단점; 크기 변경불가, 중간 데이터 삭제 오래걸림)
배열과 달리 불연속적으로 저장된 데이터 노드들을 연결한다.
- 장점
1.배열 기반이 아니라 초기 크기값이 정해져있지도 않다.
- 중간에 있는 데이터를 추가/삭제할 때 ArrayList보다 빠르다.
-
추가
뒤에 있는 데이터들을 옮기는 과정이 없고 바로 앞뒤 하나의 노드만 참조 변경을 해주면 된다. 1,2 노드 사이에 데이터를 추가하는 경우 1에서 2로 연결하던 참조를 1에서 new로 new에서 2로 참조를 하여 연결하면 된다. 옮기는 과정이 없다. -
삭제
1,2,3노드에서 2노드를 삭제한다면 1노드의 연결 노드 참조를 3노드로 바꿔주면 된다. 2노드는 나중에 알아서 gc가 삭제한다. -
단점
n번째 요소에 접근하려면 순차적으로 첫번째부터 n번쨰까지 모두 조회하는 수밖에 없다.
배열의 경우 연속적으로 저장돼서 계산으로 주소 구해서 바로 접근가능
n번째 주소= 시작 주소 + n * (노드크기) -
double linked list
접근성을 향상시키기위해 앞으로도 뒤로도 갈 수 있도록 참조 노드 수를 늘렸다. -
double circular linked list
끝의 다음을 맨 앞의 노드에 연결하고 맨 앞 노드의 앞 참조를 맨 끝 노드와 연결한다.
끝 노드를 구하고 싶을떄 맨 앞에서 끝까지 조회하는 것이 아닌 이전 노드로 가서 맨 끝 노드에 접근할 수 있다.
속도 차이
중간에서(비순차) 데이터를 추가, 삭제: LinkedList가 빠름
ArrayList 6600 LinkedList 380ms
처음부터(순차) 데이터를 추가, 삭제 ArrayList가 빠름
Arr 400 11 Linked 600 46
n번쨰 요소 접근 ArrayList가 빠름
Arr 1 Linked 432ms
