기본 자료구조인 배열과 리스트는 비슷한 점도 많지만, 다른 점도 많다.
배열
메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
특징
- 선언한 자료형의 값만 저장 가능
- 배열의 값은 인덱스를 통해 참조 가능 (값에 바로 접근)
- 새로운 값을 삽입하거나 특정 인덱스의 값을 삭제하기 어렵다. 이 작업을 하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
- 배열의 크기는 선언시 지정가능하며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
- 구조가 간단하다.
리스트
값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.
특징
- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야한다. 즉 값에 접근하는 속도가 느리다.
- 포인터로 연결되어있어 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
- 선언시 크기를 별도로 지정하지 않아도 된다. 즉, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
- 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.
LinkedList와 ArrayList
LinkedList는 ArrayList와 달리 List인터페이스를 구현한 AbstractList를 상속하지않고, AbstractSequentialList를 상속하고있다.
ArrayList는 데이터들이 순서대로 쭉 늘어선 배열의 형태를 취하고있는 반면, LinkedList는 순서대로 늘어선것이 아니라 자료의 주소값으로 서로 연결되어있는 구조를 하고있다.
아래 그림처럼말이다.
LinkedList와 ArrayList 삽입 삭제
-
LinkedList는 몇개의 참조자만 바꾸어 새로운 데이터의 삽입이나 기존 자료의 삭제를 위치 관계없이 빠른 시간안에 수행할 수 있다.
반면에, ArrayList는 최대 O(N)만큼의 연산속도가 걸려 자료의 최대 개수에 영향을 받는다. -
메모리의 용량이 무한하다고 가정할 때, LinkedList는 무한 개수의 자료를 삽입할 수 있다.
하지만 , ArrayList는 크기가 한정되어있기때문에 결국 포화상태에 이르게된다.
ArrayList의 크기를 재조정하는 연산을 수행할 수 있지만, 상당한 연산량이 요구된다.
ArrayList 삽입과정
ArrayList 삭제과정
LinkedList 삽입과정
LinkedList 삭제과정
LinkedList 장단점
ArrayList는 사이즈가 고정되어있기때문에 삽입 시 크기를 늘려줘야하고, 삭제시 데이터의 빈 곳을 채워주는 연산이 추가된다. 이런 부가적인 연산은 시스템 성능저하로 이어져, 삽입과 삭제가 빈번하게 발생하는 프로세스에 치명적이다.
그리고 자료들이 지속적으로 삭제되는 프로세스에서는 그만큼 낭비되는 공간이 많아져 메모리 낭비로 이어진다.
따라서 LinkedList는 이런 문제를 연결형태로 해결하여 주소만 연결시켜주면 되기때문에, 삽입/삭제가 빈번한 프로세스에서는 LinkedList를 사용하는것이 바람직하다.
LinkedList도 단점이 있다.
ArrayList에서는 무작위접근이 가능하지만, LinkedList는 순차접근만 가능하다.
특히 단순 LinekdList는 단방향성이기때문에, 인덱스를 이용해 데이터에 접근하는 프로세스에는 적합하지않다.
사실 순차접근도 참조의 지역성때문에, LinkedList보다 ArrayList가 훨씬 빠르다.
또한 LinkedList의 또 다른 단점은, 참조자를 위한 별도의 메모리공간을 할당해야하는것이다.
성능 비교
-> Wasted space가 왜 O(n)인지 궁금해서 찾아봤다.
1. ArrayList의 Wasted space가 O(n)인 이유
Dynamic array. We need an additional O(n) memory when we have not enough space to store all elements when increasing size of a dynamic array. We need to allocate a new memory buffer and then copy elements to this buffer. Moreover, usually dynamic arrays resize by a large amount of additional memory (to get amortized O(1) add/remove operations). And the size of wasted memory is O(n) as well.
위의 말을 이해하고, 앞에서 배운것을 생각해보자.
동적으로 사이즈가 늘어날 때, 기존n의 절반이 늘어난다고 배웠다.
따라서 O((2/1)*n)에서 1/2을 무시하므로 O(n)이 된다.
https://stackoverflow.com/questions/48356418/wasted-space-in-linked-list-and-array
2. LinkedList의 Wasted space가 O(n)인 이유
So, in the first definition, a linked list has 𝑂(𝑛)
O(n)wasted space because every entry of the list contains some piece of data but also a pointer, so a constant fraction of the space taken up by the data structure is "wasted". (I think this is a silly definition of "waste": the space taken up by the pointers isn't wasted; it's an overhead.)
포인터에 할당되는 공간은 실제 데이터를 저장하는데 사용하는 공간이 아니므로 O(n)이다.
Array와 ArrayList 차이
- 배열은 크기가 고정되어있지만 arrayList는 사이즈가 동적인 배열이다.
- 배열은 primitive type(int, byte, char 등)과 object 모두를 담을 수 있지만, arrayList는 object element만 담을 수 있다.
- 배열은 제네릭을 사용할 수 없지만, arrayList는 타입 안정성을 보장해주는 제네릭을 사용할 수 있다.
- 길이에 대해 배열은 length 변수를 쓰고, arrayList는 size() 메서드를 써야한다.
- 배열은 element들을 할당하기 위해 assignment(할당) 연산자를 써야하고, arrayList는 add() 메서드를 통해 element를 삽입한다.
ArrayList의 사이즈가 동적으로 늘어나는 원리
예시
size가 6인 arrayList에 새로운 element 4를 추가하고자 한다.
그럼 내부동작은 이렇게 되는 것이다.
결론적으로는 element를 add하려고 할 때, capacity가 elementData(배열)의 길이와 같아지면
기존의 용량 + 기존 용량/2 만큼 크기가 늘어난 배열에 기존 elementData를 copy한다.
이런 원리로 arrayList가 동적으로 크기가 늘어날 수 있는 것이다.
참고사이트
https://www.nextree.co.kr/p6506/
https://zorba91.tistory.com/287
