ArrayList, LinkedList

출처 - Java의 정석 기초편 (남궁 성)

 

 

1. ArrayList

- List인터페이스를 구현: 순서 O, 중복 O

- 배열 기반: 데이터 저장공간으로 배열 사용

- 기존 Vector 개선: 구현원리와 기능적인 면 동일, Vector는 자체 동기화 가능

 

ArrayList() // 기본 생성자(크기 0)
ArrayList(Collection c)
ArrayList(int initialcapacity) // 초기용량, 배열의 길이 지정
boolean add(Object o) // 마지막에 객체 추가
void add(int index, Object element)
boolean addAll(Collection c)
boolean addAll(int index, Collection c)
void clear() // 모든 객체 삭제
Object clone() // 복제
boolean contains(Object o) // 지정된 객체 포함되어 있는지
void ensureCapacity(int minCapacity)
Object get(int index) // 지정된 위치 객체 반환
int indexOf(Object o) // 순방향, 못찾으면 -1 반환
int lastIndexOf(Object o) // 역방향
boolean isEmpty()
Iterator iterator()
ListIterator listIterator()
ListIterator listIterator(int index) // 지정된 위치부터 시작하는 ListIterator 반환
Object remove(int index)
boolean remove(Object o)
boolean removeAll(Collection c) // 지정한 컬렉션에 저장된 것과 동일한 객체들 삭제
boolean retainAll(collection c)
Object set(int index, Object element) // 객체 변경(치환)
int size()
void sort(Comparator c) // 정렬
List subList(int fromIndex, int toIndex) // 일부 뽑아 새로운 List 생성
Object[] toArray()
Object[] toArray(Object[] a)
void trimToSize() // 공백 제거

 

 

2. ArrayList 추가, 삭제

① 삭제할 데이터의 아래의 데이터 한 칸씩 위로 복사해 덮어씀

② 마지막 데이터는 null로 변경: data[size-1]=null;

③ 데이터의 개수(size)의 값 1 감소: size--;

- 첫 번째 객체부터 삭제시 배열 복사 발생: 다 지워지지 않고 저성능

- 마지막 객체부터 삭제시 배열 복사 발생 안 함: 다 지워지고 고성능

 

 

3. LinkedList

- 배열 장점: 간단한 구조, 데이터를 읽는데 걸리는 시간(접근 시간, acess time)이 빠름

- 배열 단점: 크기 변경 불가(새로운 배열 생성→데이터 복사→참조 변경)로 큰 배열 생성시 메모리 낭비, 비순차적인 데이터 추가, 삭제시 느림

- 연결 기반: 배열의 단점 보완→불연속적으로 존재하는 데이터를 연결(link)→변경 유리

- 자신과 연결된 다음 요소의 참조(주소값), 데이터

- 링크드 리스트: 연결 리스트, 단계 이동→데이터 접근성 나쁨

- 더블리 링크드 리스트: 이중 연결 리스트, 참조 2개(다음 요소, 이전 요소)→접근성 향상

- 더블리 써큘러 링크드 리스트: 이중 원형 연결 리스트→맨 끝 이동

 

class Node {
    Node next; // 다음 요소의 주소 저장
    Object obj; // 데이터 저장
}

 

 

4. LinkedList 추가, 삭제

- 삭제: 한 번의 참조변경

- 추가: 한 번의 Node객체 생성과 두 번의 참조변경

 

 

5. ArrayList와 LinkedList

- ArrayList(연속적): 순차적으로 데이터 추가/삭제 빠름

- LinkedList(불연속적): 비순차적으로 데이터 추가/삭제 빠름

- 접근 시간: ArrayList가 빠름

- 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기