📍ArrayList
ArrayList는 List 인터페이스를 구현하는 크기가 조정 가능한 배열 데이터 구조이다.
동적 배열이라고도 하는 크기가 조정가능한 배열로, 요소를 순차적으로 저장하고 요소를 추가하거나 제거함으로써 사이즈를 늘리거나 줄일 수도 있다.
The efficiency of some common ArrayList operation:
- Retrieval(검색)
ArrayList.get(i)메소드를 통해 i 인덱스의 요소를 빠르게 검색할 수 있다.
- Addition(추가)
- 새로운 요소를 빠르게 ArrayList에 추가할 수 있다.
- Array(배열)과 대비되는 장점이다. 배열이 가득찬 경우, 새로운 요소를 추가하기 위해선 배열의 크기를 먼저 확장해야 하므로 더 많은 시간이 필요하다.
- Deletion(삭제)
- ArrayList에서 요소를 삭제하는 것은 상대적으로 느리다. 삭제된 요소 이후의 모든 요소를 왼쪽으로 한 자리 이동시켜 삭제로 인해 생긴 배열의 빈 공간을 채워야하기 때문이다.
Syntax
List<E> list = new ArrayList<E>();
E: 타입 파라미터ArrayList를 생성하기 위해선
- 저장할 객체를 E 타입 파라미터 자리에 표기하고 기본 생성자를 호출한다.
String을 저장하는 ArrayList는 아래와 같이 생성할수 있다.
public class Main2 {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
}
}- ArrayList의 E타입 파라미터를 생략하면 왼쪽 List에 지정된 타입을 따라간다. 위 코드는 동일하게 String을 저장하는 ArrayList 객체를 생성한다.
- 기본 생성자로 ArrayList 객체를 생성하면 내부 10개의 객체를 저장할 수 있는 초기용량을 갖게된다. 저장되는 객체 수가 늘어나면, 용량은 자동으로 증가한다.
- ArrayList에 객체를 추가하면 0번 인덱스부터 차례대로 저장되고, ArrayList에서 특정 인덱스의 객체를 제거하면 → 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다.
때문에, 저장된 객체수가 많고 특정 인덱스에 객체를 추가하거나 제거하는 일이 잦다면 LinkedList를 사용하는 것이 적절하다.
하지만, 인덱스를 이용해서 객체를 찾거나 맨 마지막에 객체를 추가하는 경우 ArrayList가 더 좋은 성능을 발휘한다
📍 LinkedList (연결리스트)
- 연결리스트는 연속적인 메모리 위치에 저장되지 않는, 선형 데이터 구조이다. 각 요소는 포인터를 사용해서 연결된다. 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된다.
- ArrayList는 내부 배열에 객체를 저장해서 관리하지만 LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.
Linkedlist Data Structure (연결리스트 데이터 구조)
- Node(노드)
- 데이터 저장 단위 (데이터값 + 포인터) ⇒ 하나의 데이터
- Pointer(포인터)
- 각 노드 안에서 다음 노드의 연결 정보를 가지고 있는 공간
- Head(헤드)
- 리스트에서 가장 앞부분에 위치한 노드
Advantages & Disadvantages of LinkedList (장/단점)
이점
- 동적 크기
- 메모리 사이즈는 삽입, 삭제에 따라 할당되거나 할당 해제될 수 있다.
- 삽입/삭제가 용이
- 배열보다 삽입/삭제가 용이하기 때문에 삽입/삭제 이후 각 요소가 이동될 필요가 없다. 각 요소의 주소지만 업데이트 해주면 된다.
- ArrayList는 중간 인덱스 객체를 제거하면 뒤에있는 객체의 인덱스가 1씩 앞으로 당겨지기 때문에, 빈번한 객체의 삽입/삭제가 일어난다면 LinkedList가 더 좋은 성능을 발휘한다.
- 미리 공간을 할당하지 않아도 됨.
단점
- 임의로 액세스 허용할 수 없음.
HEAD부터 순차적으로 요소에 접근해야함 (이진검색수행 불가능)
- 저장공간 비효율적
- 포인터를 위한 별도의 메모리 공간이 필요하기 때문
Syntax
List<String> list1 = new LinkedList<>();LinkedList를 생성하기 위해선 저장할 객체 타입을 타입 파라미터 에 표시하고, 기본 생성자를 호출하면 된다.
Why we use LinkedList?
왜 연결리스트를 사용하나?
- 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음.
- 배열은 크기가 고정되어 미리 요소의 수를 할당해줘야 함.
- 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간 만들고, 기존 요소를 전부 이동해줘야 함)
- → LinkedList는 배열보다 삽입, 삭제가 용이하기 때문에 삽입/삭제 이후 각 요소가 이동될 필요가 없음.
Why? So when should you use ArrayList and when should you use LinkedList?
Why? 왜? 그래서 언제 ArrayList를 사용하고, 언제 LinkedList를 사용해야 하는가?
- 끝에서부터(순차적으로) 추가 or 삭제하는 경우엔
ArrayList가 빠르지만, 중간에 추가/삭제하는 경우 앞,뒤 링크 정보만 변경하면 되는LinkedList가 더 빠르다. - ArrayList는 뒤쪽 인덱스를 모두 1씩 증가, 감소시키는 시간이 필요하므로 처리속도가 느리다.
Example
public class Main {
public static void main(String[] args) {
List<String> list1 = new LinkedList<>();
List<String> list2 = new ArrayList<>();
long startTime;
long endTime;
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
list1.add(0, String.valueOf(i));
}
endTime = System.nanoTime();
System.out.println("LinkedList 걸린시간: " + (endTime - startTime));
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
list2.add(0, String.valueOf(i));
}
endTime = System.nanoTime();
System.out.println("ArrayList 걸린시간: " + (endTime - startTime));
}
}LinkedList 걸린시간: 1312375
ArrayList 걸린시간: 5493250ArrayList와 LinkedList의 0번 인덱스에 String 객체를 10,000번 추가한 성능을 테스트했다.
실행결과를 보면LinkedList가 훨씬 빠른 성능을 발휘한다.왜?.. LinkedList는 인접 노드 링크의 정보만 변경해주면 돼서 중간에 삽입/삭제 할 경우 빠른데, ArrayList는 뒤쪽 인덱스들을 모두 1씩 증가시키는 시간이 필요하니까.
Single-linked list (단일 연결 리스트)
단일 연결리스트의 각 노드는 다음 노드에 대한 참조를 포함한다. 단일 연결리스트의 순회는 정방향으로 수행된다.
Double-linked list (이중 연결 리스트)
이중 연결 리스트는, 각 노드는 이전 노드와 다음 노드에 대한 참조를 포함한다. 정방향, 역방향 순회 가능하나 → 역방향 참조는 추가적 메모리가 필요함.
Tail- 가장 뒤에 있는 노드는 Tail을 갖게 된다. 덕분에 양방향 노드 탐색이 가능하다. 만약 뒤 쪽에 위치한 데이터를 찾을 때 Tail로부터 검색한다면 더 빠르게 검색할 수 있다.
Summary
LinkedList
- 연속적 메모리 위치에 저장되지 않는, 선형적인 데이터 구조
- 포인터를 사용해서 연결된다.
- 각 노드는 데이터+포인터(다음 노드를 참조하는) 로 구성 → 각 노드엔 포인터를 위한 별도의 공간 필요
장점
1. 동적인 크기, 삽입/삭제가 용이
2. 미리 공간 할당하지 않아도 됨단점
1. HEAD부터 순차적으로 접근해야함 → 이진 검색 수행 불가능
2. 비효율적인 메모리 사용: 포인터를 위한 별도의 메모리 공간이 필요하기 때문
ArrayList vs LinkedList
어떤걸 왜 언제 사용하는가?
1. ArrayList와 달리, 각 요소는 링크형태로 참조 되기때문에 중간에 삭제/삽입이 빈번하게 일어나는 경우 ArrayList보다 훨씬 빠른 성능을 발휘함.
2. ArrayList는 끝에서부터 순차적으로 추가/삭제하는 경우에 사용하는 것이 적절.
