💚 자료구조 - ArrayList, LinkedList 대해 설명하시오.

10) 자료구조 - ArrayList, LinkedList

List

어떤 순서가 있는 데이터의 집합

• ArrayList, LinkedList가 있음.

ex) 올림픽에서 마라톤을 했을 때, 1등부터 리스트를 쭉 저장

ArrayList

연속적인 공간에 순차적으로 데이터를 저장

배열 기반 자료 구조

만약 로또 번호를 저장한다고 했을 때 4, 12, 5, 43, 28, 31, 24 가 나왔다고 했을 때

ArrayList의 장점 : indexing이 가능하다.

그렇다면 idx[4] = 28임을 알 수 있다.

• 읽기와 검색이 빠르다.

ArrayList의 단점 : 추가 / 삭제가 어렵다.

• 만약 idx[2]를 삭제한다면 뒤의 숫자들이 한 칸씩 앞으로 와야되기 때문에 오래걸린다.

• 즉, 중간에 데이터를 삽입하거나 삭제할 때는 배열을 재배열 하므로 시간이 오래걸리고 중간의 데이터를 삭제하면 빈 공간이 남게되어 공간 낭비가 발생할 수 있다.

ArrayList는 내부에서 배열을 사용해 데이터를 저장한다. 초기 크기가 고정되어 있고 배열이 꽉 차면 새로운 더 큰 배열을 생성한 후 기존 데이터를 복사하여 확장한다.

즉, 사이즈가 고정되어 있어서 만약 사이즈를 늘리려면 복사를 통해 사이즈를 늘려야 된다.

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // ArrayList 선언
        ArrayList<String> arrayList = new ArrayList<>();

        // 요소 추가
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Cherry");
        System.out.println("ArrayList after additions: " + arrayList);

        // 특정 위치에 요소 추가
        arrayList.add(1, "Orange"); // 1번째 위치에 "Orange" 추가
        System.out.println("ArrayList after inserting 'Orange' at index 1: " + arrayList);

        // 요소 삭제
        arrayList.remove("Banana"); // "Banana" 삭제
        System.out.println("ArrayList after removing 'Banana': " + arrayList);

        // 인덱스로 요소 삭제
        arrayList.remove(1); // 인덱스 1에 있는 요소 삭제
        System.out.println("ArrayList after removing element at index 1: " + arrayList);

        // 요소 수정
        arrayList.set(0, "Mango"); // 0번째 인덱스의 요소를 "Mango"로 변경
        System.out.println("ArrayList after setting 'Mango' at index 0: " + arrayList);

        // 특정 요소 찾기
        boolean containsCherry = arrayList.contains("Cherry");
        System.out.println("Contains 'Cherry': " + containsCherry);

        // 리스트 크기 확인
        int size = arrayList.size();
        System.out.println("ArrayList size: " + size);

        // 리스트가 비어 있는지 확인
        boolean isEmpty = arrayList.isEmpty();
        System.out.println("Is ArrayList empty: " + isEmpty);
    }
}

LinkedList

비연속적인 공간에 순서대로 데이터를 저장

노드와 포인터를 이용한 동적 자료 구조

각 노드가 있고 좌측은 데이터를 저장하는 공간이고 우측은 다음 노드를 가리키는 포인터(Next) 구조이다. 따라서 동일한 데이터를 저장할 때 ArrayList보다 메모리를 더 많이 사용한다.

하지만 동적 자료 구조이므로 데이터를 추가할 때마다 포인터를 연결하는 방식으로 크기를 조정할 수 있어 ArrayList처럼 배열을 복사하여 크기를 확장하는 과정이 필요하지 않다.

LinkedList 장점 : 추가 / 삭제가 쉽다.

위의 그림을 예를 들어 B와 C 사이 G를 추가한다고 할 때 쉽게 A -> B -> G -> C -> D를 만들 수 있다.

LinkedList 단점 : 위치를 탐색하는 게 ArrayList에 비해 오래걸린다.

• 인덱스로 접근할 수 없으며 원하는 데이터를 찾으려면 처음부터 노드를 순차적으로 탐색해야한다. 그래서 읽기와 검색 속도가 ArrayList보다 오래걸리는 것!

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList 선언
        LinkedList<String> linkedList = new LinkedList<>();

        // 요소 추가
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");
        System.out.println("LinkedList after additions: " + linkedList);

        // 첫 번째와 마지막에 요소 추가
        linkedList.addFirst("Orange"); // 맨 앞에 "Orange" 추가
        linkedList.addLast("Mango"); // 맨 뒤에 "Mango" 추가
        System.out.println("LinkedList after addFirst and addLast: " + linkedList);

        // 요소 삭제
        linkedList.remove("Banana"); // "Banana" 삭제
        System.out.println("LinkedList after removing 'Banana': " + linkedList);

        // 첫 번째와 마지막 요소 삭제
        linkedList.removeFirst(); // 첫 번째 요소 삭제
        linkedList.removeLast(); // 마지막 요소 삭제
        System.out.println("LinkedList after removeFirst and removeLast: " + linkedList);

        // 특정 위치의 요소 가져오기
        String element = linkedList.get(1); // 인덱스 1에 있는 요소 가져오기
        System.out.println("Element at index 1: " + element);

        // 특정 위치에 요소 추가
        linkedList.add(1, "Strawberry"); // 1번째 위치에 "Strawberry" 추가
        System.out.println("LinkedList after inserting 'Strawberry' at index 1: " + linkedList);

        // 리스트 크기 확인
        int size = linkedList.size();
        System.out.println("LinkedList size: " + size);

        // 리스트가 비어 있는지 확인
        boolean isEmpty = linkedList.isEmpty();
        System.out.println("Is LinkedList empty: " + isEmpty);
    }
}