저번 포스팅에서 ArrayList 를 정리해봤다. 사실 면접 질문에서 ArrayList와 LinkedList의 차이에 대해 질문 받은 적이 있다. 그때는 LinkedList에 대해서 정확히 정리가 안된 상태여서 제대로 답을 하지 못했다ㅠㅠ 앞으로 다시 같은 질문을 받으면 제대로 답할 수 있도록, 정리해봤다!
LinkedList
LinkedList는 ArrayList 와 장단점이 비교되는 리스트이다.
ArrayList에서 빈번하게 중간 인덱스에서 데이터의 삽입이나 삭제가 발생할 경우, 인덱스를 조정하기 위해 그 뒤의 원소들을 하나씩 옮겨줘야하는 작업이 문제가 될 수 있다 (효율성이 떨어진다!).
이런 경우에는 양방향 연결 리스트(Doubly Linked List - 다음 원소와 이전 원소를 가리킴)로 구현된 LinkedList를 사용하는 것이 성능적으로 더 낫다!
- LinkedList는 각 원소(노드)를 링크로 연결한다.
- 맨 처음 시작 노드는 데이터가 없다. 이 노드는 처음 노드가 추가될 때 다음 노드를 가리키기만한다.
- 각 노드는 데이터를 가지고 있다.
- 각 데이터는 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.
- 각각의 노드는 데이터와 함께 next(다음 노드)와 prev(이전 노드) 값을 내부적으로 가지고 있다.
- 데이터를 추가하거나 삭제하는 것이 원활하다 (추가 / 삭제 시 변경되는 노드만 연결해주면 된다) = ArrayList와 달리 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기 때문!
LinkedList 선언 방법
LinkedList<Integer> intList1 = new LinkedList<>(); // 타입 생략 가능
LinkedList<Integer> intList2 = new LinkedList<Integer>(); // 타입 지정
LinkedList<Integer> intList3 = new LinkedList<>(intList2); // 다른 Collection값으로 초기화
LinkedList<Integer> intList4 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5)); // 초기 값 세팅
ArrayList 와 다른 점은 가용량이 의미가 없기 때문에, 초기 용량 세팅이 불가능하다.
LinkedList 값 추가 / 변경
add(Object): ArrayList 의 마지막에 데이터 추가
add(int index, Object): ArrayList 의 index 에 데이터 추가
set(int index, Object) 를 통해 값 변경
LinkedList<String> list = new LinkedList<>();
list.add("apple"); // 추가
list.add("mango");
list.add(0, "banana");
list.add("kiwi");
// [banana, apple, mango, kiwi]
list.set(0, "peach"); //수정
// [peach, apple, mango, kiwi]
LinkedList 값 삭제
remove(): 0 번째 index 제거
remove(int index): index에 해당하는 값 삭제
remove(Object): 해당 Object 와 같은 값 삭제
clear(): 데이터 모두 삭제
LinkedList<String> list = new LinkedList<String>(Arrays.asList("A", "B", "C", "D"));
// [A, B, C, D]
list.remove(); // [B, C, D]
list.remove(1); // [B, D]
list.remove("D"); // [B]
list.clear(); // []
LinkedList 전체 값 출력
LinkedList<String> list = new LinkedList<String>(Arrays.asList("A", "B", "C", "D"));
// for-each loop
for (String alphabet : list) {
System.out.print(alphabet + " ");
}
System.out.println(); // A B C D
// for loop
for (int i = 0; i < list.size(); ++i) {
System.out.print(list.get(i) + " ");
}
System.out.println(); // A B C D
// using iterator
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println(); // A B C D
// using listIterator
ListIterator<String> listIterator = list.listIterator(list.size());
while (listIterator.hasPrevious()) {
System.out.print(listIterator.previous() + " ");
}
System.out.println(); // D C B A
LinkedList 값 존재 유무
contains(Object): 해당 Object 가 존재 여부를 boolean 타입으로 리턴한다.
indexOf(Object): 해당 Object의 존재 여부와 위치를 리턴한다 (존재하지 않을 시 -1 를 리턴).
LinkedList<String> list = new LinkedList<String>(Arrays.asList("A", "B", "C", "D"));
list.contains("A"); // true
list.contains("E"); // false
list.indexOf("A"); // 0
list.indexOf("E"); // -1 : 값이 없음
ArrayList VS LinkedList
사실 사용 방법은 ArrayList 와 거의 같다고 해도 될 정도로 굉장히 유사하다!
그럼 그 둘의 차이는 무엇일까? 위에 언급한 것 처럼 LinkedList는 ArrayList와 달리 몇 개의 참조자만 바꿈으로써 자료의 삽입, 삭제를 용이하게 할 수 있다. 또한 연산 속도 때문에 자료의 최대 개수에 영향을 받는ArrayList(포하상태에 이르게 됨)와는 달리, LinkedList는 특별한 제약 없이 무한 개의 자료를 삽입할 수 있다.
하지만 LinkedList는 순차적 접근만이 가능하고 (랜덤 접근 불가능), 단방향성 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않다.
n 개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 저장한다고 하면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다. 즉, 메모리가 이곳저곳에 산재되어 저장되어있는 노드에 접근하기 때문에 이런 경우에는 ArrayList보다 소요되는 시간이 더 길다.
장점
- 자료의 삽입과 삭제가 용이하다
- 리스트 내에서 자료의 이동이 필요하지 않다
- 사용 후 장소의 재활용이 가능하다
단점
- 포인터의 사용으로 인해 저장 공간의 낭비가 있다
- 특정 자료의 탐색 시간이 많이 소요된다
따라서 탐색 또는 정렬을 자주 사용해야하는 경우에는 ArrayList, 데이터의 추가 / 삭제가 많은 경우 LinkedList 를 이용하는 것이 좋다.
[참고]
https://coding-factory.tistory.com/552
https://psychoria.tistory.com/767
'𝑷𝒓𝒐𝒈𝒓𝒂𝒎𝒎𝒊𝒏𝒈 > 𝐽𝐴𝑉𝐴' 카테고리의 다른 글
[JAVA] Collection - Set (HashSet) (0) | 2022.11.23 |
---|---|
[JAVA] Collection - List (Vector) (0) | 2022.11.22 |
[JAVA] Collection - List (ArrayList) (0) | 2022.11.21 |
[디자인패턴] 프록시(Proxy) 패턴 (0) | 2022.11.19 |
[디자인패턴] 싱글톤(Singleton) 패턴 (0) | 2022.11.19 |