list.md

ArrayList

  ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일 것이다. List 인터페이스로 구현돼 있기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.

public class ArrayList extends AbstractList
                    implements List, RandomAccess, Cloneable, java.io.Serializable {
    . . .
    transient Object[] elementData;
    . . .
}

  ArrayList는 Object 배열을 이용해 데이터를 순차적으로 저장한다. 배열과 같이 순차적으로 저장하다가 공간이 없어 더 이상 저장할 수 없으면 보다 큰 새로운 배열을 생성해 기존 배열에 있던 데이터를 새로운 배열로 복사한 다음 저장한다.

❗️ Q) ArrayList를 왜 Object 배열로 구현했을까?
A) ArrayList뿐 아니라 Collection Framework에 모든 종류의 객체를 담기 위해 모든 객체의 최고조상인 Object 타입의 배열로 구현됐다.

ArrayList의 생성자와 메서드

Method	Explanation
ArrayList()	ArrayList 생성자 (default 크기: 10)
ArrayList(Collection c)	컬렉션 c가 저장된 ArrayList 생성자
ArrayList(int initialCapacity)	지정된 초기용량을 갖는 ArrayList 생성자
boolean add(Object o)	ArrayList 마지막에 객체 추가
void add(int index, Object element)	지정된 위치(index)에 객체 추가
boolean addAll(Collection c)	컬렉션 c의 모든 객체 추가
void addAll(int index, Collection c)	지정된 위치(index)에 컬렉션 c의 모든 객체 추가
void clear()	ArrayList를 완전히 비움
Object clone()	ArrayList 복제
boolean contains(Object o)	객체 o가 ArrayList에 포함돼 있는지
void ensureCapacity(int minCapacity)	ArrayList의 용량의 최소치 지정
Object get(int index)	지정된 위치(index)에 저장된 객체 반환
int indexOf(Object o)	지정된 객체가 저장된 위치를 찾아 반환
boolean isEmpty()	ArrayList가 비어있는지 확인
ArrayList의 Iterator 객체 반환
int lastIndexOf(int index)	객체 o가 저장된 위치를 끝부터 역방향으로 검색해 반환
ListIterator listIterator()	ArrayList의 listIterator 반환
ListIterator listIterator(int index)	ArrayList의 지정된 위치부터 시작되는 listIterator 반환
Object remove(int intdex)	지정된 위치(index)에 있는 객체 제거
boolean remove(Object o)	지정된 객체 제거
boolean removeAll(Collection c)	지정된 컬렉션 c에 저장된 것과 동일한 객체들 제거
boolean retainAll(Collection c)	ArraList에 저장된 객체 중 주어진 컬렉션 c와 공통된 것들을 제외하고나머지 삭제
Object set(int index, Object element)	주어진 객체를 지정된 위치(index)에 저장
int size()	ArrayList에 저장된 객체의 개수 반환
void sort(Comparator c)	지정된 정렬기준 c에 맞게 ArrayList 정렬
List subList(int fromIndex, int toIndex)	지정된 범위 내에 저장된 객체 반환
Object[] toArray()	ArrayList에 저장된 모든 객체들을 객체 배열로 반환
Object[] toArray(Object[] a)	ArrayList에 저장된 모든 객체들을 객체배열 a에 담아 반환
void trimToSize()	용량을 크기에 맞게 줄임 (빈 공간 제거)

LinkedList

  배열은 가장 기본적인 형태의 자료구조로, 구조가 간단하며 데이터 탐색 시간이 가장 빠르지만 큰 단점을 가지고 있다. 먼저 크기를 변경할 수 없다. 배열은 크기를 변경하기 위해 새로운 배열을 생성해 데이터를 복사헤야 한다는 단점이 있다. 또 비순차적인 데이터 삽입, 삭제에 시간이 많이 소요된다.

  이러한 배열의 단점을 보완하기 위해 LinkedList가 고안되었다. 배열과 다르게 LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성돼 있다. LinkedList의 각 node들은 자신과 연결된 다음 요소에 대한 주소와 데이터로 구성돼 있다.

  위의 그림은 LinkedList의 중간에 있는 node를 삭제하는 과정이다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 추가 등의 다른 과정도 이렇게 이루어지기 때문에 배열보다 오버헤드가 적다.

  이렇게 단방향으로 있는 LinkedList와 다르게 각 노드들이 가리키는 방향이 next와 previous, 양방향인 LinkedList도 있다. 이를 Double LinkedList라고 한다. 당연히 단방향일 때보다 노드 간 접근 및 이동이 쉽다. 실제로 Java의 LinkedList 클래스도 Double LinkedList로 구현돼 있다. 이보다 더 접근성을 향상한 Doubly Circular LinkedList도 있지만 구현이 복잡해 보통 Double LinkedList를 사용한다. (마지막 요소가 첫번째 요소를 가리키는 구조를 원형이라고 한다.)

Method

LinkedList()	LinkedList 생성자
LinkedList(Collection c)	주어진 컬렉션을 포함하는 LinkedList 생성자
boolean add(Object o)	지정된 객체 o를 LinkedList 끝에 삽입
void add(int index, Object element)	지정된 위치(index)에 객체를 추가
boolean addAll(Collection c)	주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가
void clear()	LinkedList의 모든 요소를 삭제
boolean contains(Object o)	지정된 객체가 LinkedList에 포함됐는지 여부
boolean containsAll(Collection c)	지정된 컬렉션이 LinkedList에 포함됐는지 여부
Object get(int index)	지정된 위치(index)의 객체 반환
int indexOf(Object o)	지정된 객체가 저장된 인덱스 반환
boolean isEmpty()	LinkedList가 비어있는지 리턴
int lastIndexOf(Object o)	지정된 객체의 index 반환 (역순 검색)
Object remove(int index)	지정된 index의 객체 삭제
boolean remove(Object o)	지정된 객체를 LinkedList에서 제거
boolean removeAll(Collection c)	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolean retainAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
Object set(int index, Object element)	지정된 위치의 객체를 주어진 객체로 바꿈

⭐️ LinkedList와 ArrayList의 차이

1. 순차적으로 삽입/삭제하는 경우, ArrayList가 효율적

  초기용량을 고려하지 않고 봤을 때, 순차적인 작업은 ArrayList가 효율적이다. 순차적으로 삭제한다는 것은 마지막 데이터부터 역순으로 삭제해나간다는 것을 의미한다. ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않으므로 상당히 빠르다. 마지막 요소를 null로 바꿔주면 되기 때문이다.

2. 중간 데이터를 삽입/삭제하는 경우, LinkedList가 효율적

  중간 요소를 추가 또는 삭제하는 경우 LinkedList는 각 요소간의 연결만 변경해주면 되지만, ArrayList는 각요소들을 재배치하여 추가할 공간을 확보 또는 빈 공간을 채워야하기 때문에 처리속도가 느리다.

3. 정리

Collection	접근시간(읽기)	삽입 / 삭제	설명
ArrayList	빠르다	느리다	✓ 순차적인 삽입삭제는 더 빠름 ✓ 비효율적인 메모리 사용
LinkedList	느리다	빠르다	✓ 데이터가 많을수록 접근성이 떨어짐