ArrayList
ArrayList는List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고, 중복을 허용한다는 특징을 가짐.ArrayList는 기존의Vector를 개선한 것으로Vector의 구현원리와 기능적인 측면에서 동일하다고 할 수 있으나, 기존에 작성된 소스와의 호환성을 위해 남겨 두고 있을 뿐이기 때문에 가능하면ArrayList를 사용해야 함.ArrayList는Object 배열을 이용해서 데이터를 순차적으로 저장함. 배열에 더이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음 저장됨.
==============================================================================
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, Java.io.Serializable {
....
transient Object[] elementData; // Object 배열
============================================================================== - 위으 코드는
ArrayList의 소스코드 일부인데,ArrayList는elementData라는 이름의Object 배열을 멤버변수로 선언하고 있다는 것을 알 수 있음. 선언된 배열의 타입이 모든 객체의 최고조상인Ojbect이기 때문에 모든 종류의 객체를 담을 수 있음.
ArrayList의 메서드
ArrayList의 추가와 삭제
ArrayList 의 요소를 삭제하는 경우, 삭제할 객체의 바로 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 객체를 덮어쓰는 방식으로 처리함. 아래의 그림은 remove(2) 를 호출했다고 가정하고, 그 수행 과정의 일부를 단계별로 나타낸 것임.
LinkedList
배열은 ① 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 하며, ② 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸림. 이러한 단점을 보완하기 위해서링크드 리스트(linked list)라는 자료구조가 고안됨.LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있음.- 아래 그림에서 알 수 있듯이
LinkedList의 각요소(node)들은자신과 연결된 다음 요소에 대한 참조(주소값)와데이터로 구성되어 있음.
==============================================================================
class Node {
Node next; // 다음 요소의 주소를 저장
Object obj; // 데이터를 저장
}
============================================================================== LinkedList의 추가와 삭제
LinkedList에서의 데이터 삭제는삭제하고자 하는 요소의이전 요소가삭제하고자 하는 요소의다음 요소를 참조하도록 변경하면 됨.
- 새로운 데이터를 추가할 때는
새로운 요소를 생성한 다음, 아래 그림과 같이 참조를 변경해주면 됨.
ArrayList와 LinkedList의 비교
배열 의 경우 만일 인덱스가 n 인 원소의 값을 얻어 오고자 한다면 아래와 같은 수식을 계산함으로써 해결됨.
인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
배열 은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만, LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있음.
다루고자 하는 데이터의 개수가 변하지 않는 경우면, ArrayList가 최상의 선택이 되겠지만, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 됨.
