Collection framework에 대해 (3)

ArrayList의 장점과 단점

- 장점

배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(Access time)이 짧다.

- 단점

크기를 변경할 수 없어 크기를 변경해야 할 때 새로운 배열을 생성 후 데이터를 복사하는 방식으로 크기를 변경해야 한다. 이러한 작업은 메모리 비용이 많이 들기 때문에 가급적이면 피해야 한다.

크기 변경을 피하기 위해서 큰 배열을 생성하게 될 경우 메모리 낭비가 발생하게 된다.

비순차적인 데이터의 추가 및 삭제에 시간이 오래 걸린다.

데이터를 추가하거나 삭제하기 위해서 관련이 없는 다른 데이터들까지 이동시켜야 한다.

순차적인 데이터를 추가(끝에 추가) 및 삭제(끝부터 삭제)하게 될 경우 속도가 빠르다.

LinkedList

-배열의 단점을 보완하기 위해 고안되었다.

- LinkedList는 불연속적으로 존재하는 데이터를 연결(link)하게 된다.

- 데이터의 삭제는 단 한번의 참조 변경(노드 간 연결만 변경)으로 가능하게 되었는데 이것이 원활히 되는 이유로는 링크드 리스트가 노드로 이루어져있기 때문이다.

- 데이터의 추가는 한 번의 Node객체생성과 두 번의 참조변경으로 가능하게 되었다.

LinkedList의 종류

- 링크드 리스트

연결 리스트라고도 한다. 앞 노드에 대한 참조가 존재하지 않아 데이터 접근성이 나쁜 편이다.

class Node {

Node next;

Object obj;

}

- 더블리 링크드 리스트

이중 연결리스트라고도 한다. 앞 뒤 노드 전부에 대한 참조를 하여 접근성이 향상되었다. 대신 노드를 추가 삭제해야 할 때 참조해야 할 노드의 수가 하나 늘어나게 된다.

class Node {

Node next;

Node previous;

Ovject obj;

}

- 더블리 써큘러 링크드 리스트

이중 원형 연결리스트라고도 한다. 앞 뒤에 대한 참조 뿐 아니라 맨 뒤 노드와 맨 앞 노드도 연결하여 원 모양을 이루도록 만든다.

- 기본적인 LinkedList라고 한다면 이중 연결리스트로 구현된 리스트라고 생각하면 된다. 처음에는 이중 원형 연결리스트로 구현하였으나, 맨 뒤와 맨 앞의 연결을 해두어도 쓸 일이 별로 없는 반면 관리해야 하는 연결만 늘어나게 되는 문제가 발생했다.

ArrayList와 LinkedList의 성능 비교

- 순차적으로 데이터를 추가 / 삭제 : ArrayList > LinkedList

- 비순차적으로 데이터를 추가 / 삭제 : ArrayList  < LinkedList

- 접근 시간(Access Time) : ArrayList > LinkedList

배열의 요소에 접근하는 것은 간단한 공식을 적용하기만 하면 되지만, LinkedList는 각 요소를 건너띄지 않고 하나하나 접근해야 하기 때문에 시간이 더 오래 걸린다.

n번째 데이터 주소 = 배열의 주소 + (n - 1) * 데이터 타입의 크기

- ArrayList는 읽는 시간이 빠르며 추가와 삭제는 느리다고 볼 수 있다. 순차적인 추가 삭제의 경우에는 오히려 더 빠르며 비효율적인 메모리 사용 경향을 보인다.

- LinkedList는 읽는 시간은 느리지만 데이터를 추가하고 삭제하는 시간은 빠르다고 할 수 있다. 또한 데이터가 많을 수록 접근성이 떨어지는 경향을 보인다.