자료구조 - List 계열

List 계열

 

List계열은 중복을 허용하며 저장순서가 유지되는 특징이 있으며 다음과 같은 계층도를 갖는다. 

 

List 계열 

 

여기서 ArrayList는 Vector를 보완한 것으로 기능과 구현원리가 동일하므로 ArrayList를 쓰기로 한다. 

 

그럼 Vector는 왜 있는가? 

기존에 작성된 소스들과의 호환성을 위해 남겨두었을뿐 사실상 의미는 없다. 

 

 

 

 

 

---

 

 

 

 

1) ArrayList

 

ArrayList는 이름에서부터 그렇듯, 배열과 많이 닮아 있다. index로 데이터들을 구분할 수 있기 때문에 

중복된 데이터의 입력을 허용하며, index를 이용해 접근도 가능하다. 

 

배열과의 중요한 차이점이 있는데 ArrayList는 우리가 사용하기 편하게 상황에 따라 size가 변하게 된다. 

그래서 우리가 처음에 크기를 정해놓고 그만큼만 쓸수있는 배열과 달리 자유자재로 삽입, 삭제를 해도 된다.  

따라서 동적배열이라고 부르기도 하는데 물론 선언할때 ArrayList의 크기를 설정해줄 수 있지만 설정하지 않았을때 default 용량은 10이다.

 

하지만, 중요한 점은 우리가 선언한 그 ArrayList의 size가 실제로 변하는것이 아니라는 점이다. 

사용할 때 외부적으로 size가 자유자재로 변하는 것처럼 보이도록 내부적으로 구현해 놓은것일뿐이다. 

따라서 ArrayList의 데이터 추가, 삭제의 내부구현을 보면 다음과 같다. 

 

데이터를 중간에 추가하는 과정

중간에 있는 데이터를 삭제하는 과정

 

데이터를 추가하다가 capacity 만큼 데이터가 꽉차게 되면 기존의 크기에 1.5배에 해당하는 새로운 배열을 생성 후 

기존의 데이터를 모두 새로운 배열에 옮기고, 기존의 배열을 버리게 된다.