🏃‍♂️ 들어가기 앞서..

본 게시물은 스터디 활동 중에 작성한 게시물로 자바의 정석-기초편 교재를 학습하여 정리하는 글입니다.
※ 스터디 Page : 〔투 비 마스터 : 자바〕

＊해당 교재의 목차 순서와 구성을 참고하여 작성하며
각 내용마다 부족할 수 있는 내용이나 개인적으로 궁금한 점은
추가적인 검색을 통해 채워나갈 예정입니다.

---

🧶 ArrayList

기존의 Vector를 개선한 컬렉션 클래스로
구현원리와 기능적 측면은 동일하다.

ArrayList는 Object배열을 이용해서 " 데이터를 순차적으로 저장 "한다.

배열의 타입이 Object이기 때문에
" 모든 종류의 객체 "를 담을 수 잇다.

배열에 " 더 이상 저장 공간이 없으면 "

<보다 큰 배열>을 새로 생성해서
기존의 배열 내용을 복사한 다음 저장하게 된다.

🔧 메서드

※ 생성자

Method	설명
ArrayList()	크기 0인 " ArrayList 생성
ArrayList( Collection c )	지정 Collection이 저장된 " ArrayList 생성
ArrayList( int initialCapacity )	해당 값의 초기용량을 갖는 *ArrayList 생성
List subList( int fromindex, int toindex )	해당 범위의 객체들을 List로 반환
Iterator iterator()	ArrayList의 Iterator 반환
ListIterator listIterator()	ArrayList의 ListIterator 반환
Object[] toArray()	ArrayList 저장 객체를 " 객체배열 "로 반환
Object[] toArray( Object[] a )	" 지정된 배열 "에 ArrayList의 객체를 저장해서 반환
[ 복사 ]
Object clone()	ArrayList 복제

※ 추가

Method	설명
boolean add( Object o )	끝에 객체를 추가
void add( int index, Object element )	지정 위치에 객체 저장
boolean addAll( Collection c )	주어진 Collection의 모든 객체 추가
boolean addAll( int index, Collection c )	지정 위치부터에 주어진 Collection의 모든 객체 추가

중간 위치에 추가되게 되면
기존 index 뒤에 있던 값들 은 자동으로 뒤로 밀리고 길이가 늘어난다.

※ 삭제

Method	설명
Object remove( int index )	위치 지정 삭제
boolean remove( Object o )	객체 지정 삭제
boolean removeAll( Collection c )	지정 Collection에 포함된 객체 삭제
boolean retainAll( Collection c )	지정 Collection에 포함된 객체 제외 나머지 삭제 ( 변화 有 : true / 변화 無 : false )

※ 조회

Method	설명
boolean contains( Object o )	지정된 객체가 ArrayList에 포함되어 있는지 확인
int size()	개수 조회
[ 호출 ]
Object get( int index )	index 위치의 객체 반환
int indexOf( Object o )	객체의 index 반환
int lastIndexOf( Object o )	해당 객체의 위치 반환 ( 역순 )

※ 수정 / 변환

Method	설명
Object set( int index, Object o )	수정
[ 길이 조절 ]
void ensureCapacity( int minCapacity )	최소 필수 용량 설정
void trimToSize()	빈 공간 제거 : 실 데이터 개수에 맞게끔
[ 정렬 ]
void sort( Comparator c )	지정된 정렬 기준(c)으로 정렬

＊ sort()메서드 : Collections클래스의 메서드

❓ 추가 / 삭제

ArrayList는 순차적으로 연속적인 하나의 List를 가진다.

<삭제>의 경우는
삭제할 객체의 바로 아래 객체를
한 칸씩 위로 복사해서 " 덮어쓰는 방식 " 으로 처리된다.
( 마지막 데이터 삭제라면 그저 null로 변경해주기만 하면 된다. )

그렇기 때문에
마지막부터 순서대로 삭제/추가하는 경우엔 작업시간이 빠르지만

중간을 조작할 경우,
다른 데이터들의 이동때문에 작업시간이 기하급수적으로 증가하게 된다.

※ remove 메서드 ( remove() )
JAVA의 " 오토박싱 " 기능으로 인한 주의점이 있는데

만약 데이터가 String타입의 1 ( "1" ) 이나 Integer타입의 1 ( 1 ) 을 지우려고 할 때,
단순히 remove(1)을 하게 된다면 index로 처리되기 때문에
두 번째 객체 가 지워지게 된다.

그렇기 때문에
remove( new Integer(1) )이나
remove( new String(1) )의 방법을 사용해야 한다.

---

앞서 살펴봤었던 배열은 가장 기본적인 형태의 자료구조로서

구조가 간단하고
사용 용이성이 좋고
접근 시간( 데이터 읽기 소요시간 )이 빠르다는 장점이 있다.

하지만 단점도 당연히 있는데

• " 크기 변경 "이 불가능하다.
  : 단순히 크기를 변경하려면 새로운 배열 생성 & 데이터 복사의 과정 필요
• 데이터의 " 비순차적 추가/삭제 "의 경우는 소요시간이 길다.
  : 차례대로 데이터 추가 & 뒤에서부터 순서대로 삭제는 빠르지만 중간에서 작업하면 일일이 복사&덮어쓰기

위와 같은 서로 독립적이지 못한 순차적인 특징이 오히려 단점으로 작용하는 것을
보완하기 위해 고안된 자료구조가
바로 LinkedList이다.

🧶 LinkedList

앞서 알아본 ArrayList는 배열 기반의 List이지만
이 Linked List는
Node(요소) 연결 기반의 List로

불연속 적으로 각 요소마다 독립된 객체들이
서로 " 연결 "되어 하나의 List가 구성되는 것이다.

기본적으로
각 Node에는 데이터와 더불어
" 다음 요소(Node)의 주소 값 "을 가지고 있다.

❓ 추가 / 삭제

서로 독립적으로 있는 요소들이
각자 뒤에 있는 노드의 주소값을 참조함으로서 연결되어 있기 때문에

'삭제'가 매우 간단하다.
삭제하려는 노드 이전 Node의 " 다음 Node (삭제 Node) 참조 주소값 "을
삭제 노드 " 뒤 Node의 주소값 "으로 바꿔주기만 하면 된다.

ArrayList에서 일일이 복사해서 붙여주는 방식이 아닌
그저 """ 참조 주소값 수정 """ 만 하면 처리되니

불연속적인 처리에 대해
처리속도(access time)이 훨씬 빠르다.

---

💢 비교

서로의 작업 방식이 다른만큼
장단점도 극명하게 갈린다.

""" 인덱스(index)가 N인 원소의 값 """ 을 가져오려고 할 때

ArrayList(배열) 의 경우,
매우 단순하다.

메모리에 데이터들이 연속적으로 차례대로 붙어있기 때문에
【(배열의 주소) + ( N * 데이터타입 크기[Byte] )】 수식으로
금방 추출할 수 있다.

하지만
LinkedList(요소 연결)의 경우,

불연속적인 각각의 Node(요소)들이
다음 Node의 주소 참조값으로 연결되어있기 때문에

N번째 데이터까지 가기 위해선
그 이전의 Node들의 연결을 모두 거쳐서 가야한다.

그렇기 때문에
단순한 기본 Linked List에서는
데이터 개수가 많아질수록

Access Time이 길어지는 단점이 있다.

	ArrayList	LinkedList
읽기 (Access Time)	빠름	느림
추가 / 삭제	느림	빠름
비고	비효율적인 메모리 사용 복잡한 처리 (단, 순차적인 추가삭제는 빠름)	데이터가 많을수록 " 접근성 떨어짐"

《 Linked List 개선 》

• Linked List ▶ " Doubly Linked List ( 이중 연결 리스트 ) "
  : " 양방향 이동 " 가능하게끔 _ Next 노드 주소 참조 & Previous 노드 주소 참조
  
  
• Doubly Linked List ▶ " Doubly Circular Linked List ( 이중 원형 연결 리스트 ) "
  : 양방향 이동과 " 첫 Node에서 마지막 Node까지 한 번에 이동 " 가능하게끔
  첫 Node의 Previus 노드 주소로 마지막 Node 주소 참조

---