리스트(List)

1. 리스트(List)란?

- 리스트는 데이터를 순차적으로 관리하는 컬렉션 프레임워크의 한 종류로 순서가 유지되며 중복된 요소를 허용한다는 특징이 있다. 자주 사용되는 구현체로는 ArrayList(배열기반)와 LinkedList(노드기반)가 있다.

 

1-1. ArrayList의 특징

- 연속된 메모리 공간에 데이터를 저장하며 인덱스를 이용한 접근은 O(1)의 복잡도를 가진다.

- 중간에 요소를 삽입하거나 삭제할 때 뒤에 요소를 이동시켜야 하므로 O(n)의 복잡도를 가진다.

- 추가적인 참조가 필요없어 메모리 오버헤드가 적다.

- 연속된 메모리 공간에 저장되어 있어 캐시 효율성이 좋다.

 

1-2. LinkedList의 특징

- 각 노드가 다음 노드에 대한 참조를 가지고 있으며 인덱스를 통한 접근은 순차적으로 탐색해야 되서 O(n)의 복잡도를 가진다.

- 노드의 삽입 및 삭제가 인접 노드의 참조 변경으로 이루어지므로 빠른 삽입과 삭제가 가능하여 O(1)의 복잡도를 가진다.

- 각 노드가 이전 노드와 다음 노드의 참조를 저장하기 때문에 메모리 오버헤드가 크다.

- 노드들이 메모리 상에 흩어져 저장될 가능성이 있어 캐시 효율성이 떨어진다.

 

2. 주요 메소드

- add(E element): 리스트의 끝의 요소를 추가한다.

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

arrayList.add("Apple"); // 0번 인덱스에 "Apple" 추가
linkedList.add("Banana"); // 0번 인덱스에 "Banana" 추가

 

- add(int index, E element): 특정 인덱스 위치에 요소를 삽입한다.

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

arrayList.add(1, "Apple"); // 1번 인덱스에 "Apple" 추가
linkedList.add(1, "Banana"); // 1번 인덱스에 "Banana" 추가

 

- get(int index): 해당 인덱스의 요소를 반환한다.

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

arrayList.add("Apple");
linkedList.add("Banana");

arrayList.get(0); // 0번 인덱스의 요소인 "Apple" 조회
linkedList.get(0); // 0번 인덱스의 요소인 "Banana" 조회

 

- remove(int index): 인덱스에 해당하는 요소를 삭제한다.

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

arrayList.add("Apple");
linkedList.add("Banana");

arrayList.remove(0); // 0번 인덱스의 요소인 "Apple" 삭제
linkedList.remove(0); // 0번 인덱스의 요소인 "Banana" 삭제

 

- contains(E element): 리스트에 해당 요소가 존재하는지 확인한다.

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

arrayList.add("Apple");
linkedList.add("Banana");

arrayList.contains("Apple"); // "Apple"이 존재하므로 true 반환
linkedList.contains("Apple"); // "Apple"이 존재하지 않으므로 false 반환