List
List는 배열과 같이 객체를 일렬로 늘어놓은 구조이며 객체를 저장하면 자동으로 인덱스를 부여한다.
또한 순서가 있으며 데이터의 중복을 허용한다!
🔎 List 인터페이스 주요 메서드
| 메서드 | 설명 |
|---|---|
| void add(int index, Object element) boolean addAll(int index, Collection c)) boolean addAll(Collection c) | 지정된 위치(인덱스)에 객체 또는 컬렉션에 포함된 객체들 추가 |
| Object get (int index) | 주어진 위치에 있는 객체 반환 |
| int indexOf (Object o) int lastIndexOf (Object o) | 순방향/역방향으로 탐색하여 주어진 객체의 위치 반환 여부 |
| ListIterator listIterator() ListIterator listIterator(int index) | List의 객체에 접근할 수 있는 ListIterator 반환 |
| Object remove (int index) | 지정된 위치에 있는 객체를 삭제하고 삭제된 객체 반환 |
| Object set(int index, Object element) | 지정된 위치에 객체 저장 |
| void sort (Comparator c) | 지정된 비교자로 List 정렬 |
| List subList(int fromIndex, int toIndex) | 지정된 범위(fromIndex부터 toIndex까지)에 있는 객체 반환 |
ArrayList
- 가장 많이 사용되는 컬렉션 프레임 워크
- 기능적으로 Vector와 동일 / Vector을 개선한 것
- 저장 용량을 초과하여 객체들이 추가되면, 자동으로 저장용량이 늘어남
- 데이터 순서 유지, 중복 허용
ArrayList <String> arr1 = new ArrayList<String>(30); // String 타입의 객체를 저장하는 ArrayList 생성 // 초기 용량 30으로 설정 (초기 용량을 정해주지 않으면 기본적으로 10 지정)
예) 추가, 검색, 삭제
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
// 데이터 추가
list.add("Spring");
list.add("Summer");
list.add("Winter");
// 저장된 총 객체의 수 얻기
int size = list.size();
System.out.println(size); // 3
// 0번 인덱스의 객체 얻기
String season = list.get(0);
System.out.println(season); // Spring
// 저장된 총 객체 수 만큼 조회
for(int i=0; i<size; i++){
String str = list.get(i);
System.out.println(i + ":" + str);
}
// 0:Spring
// 1:Summer
// 2:Winter
//0번 객체 삭제
list.remove(0);
}
LinkedList
- 데이터를 효율적으로 추가, 삭제, 변경하기 위해 사용
- 각 요소(node)들은 자신과 연결된 다음 요소의 주소값과 데이터로 구성
class Node { Node next; // 다음 요소의 주소를 저장 Object obj; // 데이터를 저장 }
- 배열처럼 데이터를 이동하기 위해 복사할 필요가 없기 때문에 처리 속도가 훨씬 빠르다
데이터를 추가할때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 된다.
데이터를 삭제할때는 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 된다.
Double LinkedList
링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다.
이점을 보완한것이 더블 링크드 리스트다.
class Node { Node next; // 다음 요소의 주소를 저장 Node previous; // 이전 요소의 주소를 저장 Object obj; // 데이터를 저장 }
🔎 ArrayList와 LinkedList의 차이
성능
public class ArrayListLinkedListTest {
public static void main(String args[]) {
// 추가할 데이터의 개수를 고려하여 충분히 잡하야한다.
ArrayList al = new ArrayList(2000000);
LinkedList ll = new LinkedList();
System.out.println("= 순차적으로 추가하기 =");
System.out.println("ArrayList : " + add1(al));
System.out.println("LinkedList : " + add1(ll));
System.out.println();
System.out.println("= 중간에 추가하기=");
System.out.println("ArrayList : " + add2(al));
System.out.println("LinkedList : " + add2(ll));
System.out.println();
System.out.println("= 중간에서 삭제하기 =");
System.out.println("ArrayList : " + remove2(al));
System.out.println("LinkedList : " + remove2(ll));
System.out.println();
System.out.println("= 순차적으로 삭제하기 =");
System.out.println("ArrayList : " + remove1(al));
System.out.println("LinkedList : " + remove1(ll));
}
public static long add1(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) list.add(i + "");
long end = System.currentTimeMillis();
return end - start;
}
public static long add2(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) list.add(500,"X");
long end = System.currentTimeMillis();
return end - start;
}
public static long remove1(List list) {
long start = System.currentTimeMillis();
for (int i = list.size() - 1; i >= 0; i--) list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
public static long remove2(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
}결과
= 순차적으로 추가하기 =
ArrayList : 284
LinkedList : 406
= 중간에 추가하기 =
ArrayList : 3453
LinkedList : 16
= 중간에서 삭제하기 =
ArrayList : 2641
LinkedList : 234
= 순차적으로 삭제하기 =
ArrayList : 0
LinkedList : 31✔️ ArrayList
순차적으로 추가/삭제 할때는 데이터를 이동하지 않아도 되므로 작업 속도가 빠름
데이터를 읽어들이는 경우 인텍스를 통해 바로 데이터에 접근 가능하여 검색 빠름
-> ( 배열의 주소 + n * 데이터 타입의 크기)
✔️ LinkedList
중간에 위치한 객체를 추가 및 삭제할때 ArrayList보다 더 빠름
데이터를 검색할 때는 시작 인덱스에서부터 찾고자하는 데이터까지 순차적으로 접근해야해서 느림
| 컬렉션 | 읽기(접근시간) | 추가/삭제 | 비 고 |
|---|---|---|---|
| ArrayList | 빠르다 | 느리다 | 순차적인 추가삭제는 더 빠름 (뒤에서부터) 비효율적인 메모리 사용 |
| LinkedList | 느리다 | 빠르다 | 데이터가 많을수록 접근성이 떨어짐 |
개발자로 가는 👣