[Java Study] 09-1. Array & ArrayList & Linked List

public static void main(String[] args) { int[] arr = new int[5]; //index 입력: O(1) System.out.println("==index 입력: O(1)=="); arr[0] = 1; arr[1] = 2; arr[2] = 3; System.out.println(Arrays.toString(arr)); //index 변경: O(1) System.out.println("==index 변경: O(1)=="); arr[2] = 10; System.out.println(Arrays.toString(arr)); //index 조회: O(1) System.out.println("==index 조회: O(1)=="); System.out.println("arr[2] = " + arr[2]); //검색: O(n) System.out.println("==배열 검색: O(n)=="); System.out.println(Arrays.toString(arr)); int value = 10; for (int i = 0; i < arr.length; i++) { System.out.println("arr[" + i + "]:" + arr[i]); if (arr[i] == value) { System.out.println(value + " 찾음"); break; } } }

public static void main(String[] args) { int[] arr = new int[5]; arr[0] = 1; arr[1] = 2; System.out.println("Arrays.toString(arr) = " + Arrays.toString(arr)); // 처음 위치에 추가 System.out.println("배열의 1번째 위치에 3추가 O(n)"); addFirst(arr, 3); System.out.println(Arrays.toString(arr)); // 인덱스 위치에 추가 System.out.println("배열의 index(2) 위치에 4 추가 O(n)"); addAtIndex(arr, 2, 4); System.out.println(Arrays.toString(arr)); // 마지막 위치에 추가 System.out.println("배열의 마지막 위치에 5 추가"); addLast(arr, 5); System.out.println(Arrays.toString(arr)); } // 처음 위치 추가 private static void addFirst(int[] arr, int newValue) { for (int i = arr.length - 1; i > 0; i--) { arr[i] = arr[i - 1]; } arr[0] = newValue; } // 인덱스 위치에 추가 private static void addAtIndex(int[] arr, int index, int newValue) { for (int i = arr.length - 1; i > index; i--) { arr[i] = arr[i - 1]; } arr[index] = newValue; } // 마지막 위치에 추가 private static void addLast(int[] arr, int newValue) { arr[arr.length - 1] = newValue; }

public static void main(String[] args) { // List 생성 List<String> list = new ArrayList<>(); // add(E e): 리스트의 끝에 지정된 요소를 추가합니다. list.add("Apple"); list.add("Banana"); list.add("Cherry"); System.out.println("After add: " + list); // addAll(Collection c): 컬렉션의 모든 요소를 추가합니다. List<String> anotherList = List.of("Peach", "Grapes"); list.addAll(anotherList); System.out.println("list = " + list); // addAll(int idx, Collection c): 지정된 위치에 컬렉션의 모든 요소를 추가합니다. List<String> anotherList2 = List.of("Orange", "Grapes"); list.addAll(2, anotherList2); System.out.println("list = " + list); // set(int idx, E element): 요소변경 list.set(3, "Kiwi"); // remove(int idx) idx 요소 제거 String isRemove1 = list.remove(4); System.out.println("isRemove1 = " + isRemove1); // remove(E element) element 제거 boolean isRemove2 = list.remove("Banana"); System.out.println("isRemove2 = " + isRemove2); // contains(E element) element 검색결과 boolean contains = list.contains("Cherry"); System.out.println("contains = " + contains); // sort(Comparator c): 비교자에 따라 정렬 list.sort(null); list.sort(Comparator.naturalOrder()); // subList(int fromIdx, int toIndex) 리스트 일부분 반환 List<String> subList = list.subList(1, 3); System.out.println("subList = " + subList); // iterator(): 리스트의 반복자 반환 Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { String next = iterator.next(); System.out.println("next = " + next); } }

public class MyArrayListV4<E> { // 최초 크기 private static final int DEFAULT_CAPACITY = 5; private Object[] elementData; private int size = 0; // 생성자 // 제네릭은 new를 사용할 수 없어 Object사용 public MyArrayListV4(){ elementData = new Object[DEFAULT_CAPACITY]; } public MyArrayListV4(int initialCapacity){ elementData = new Object[initialCapacity]; } // 현재 크기반환 public int size(){ return size; } // 추가 public void add(E e) { // 길이 초과시, 동적 리사이징 if (size == elementData.length) { grow(); } elementData[size] = e; size++; } // 특정 인덱스위치에 추가 public void add(int index, E e) { // 길이 초과시, 동적 리사이징 if (size == elementData.length) { grow(); } shiftRightFrom(index); elementData[index] = e; size++; } // 제거 public E remove(int index) { E oldValue = get(index); shiftLeftFrom(index); size--; elementData[size] = null; return oldValue; } // -> 1칸씩 이동 private void shiftRightFrom(int index) { for (int i = size; i > index; i--) { elementData[i] = elementData[i - 1]; } } // <- 1칸씩 이동 private void shiftLeftFrom(int index) { for (int i = index; i < size - 1; i++) { elementData[i] = elementData[i + 1]; } } // 동적배열 크기 확장(2배) private void grow() { int oldCapacity = elementData.length; int newCapacity = oldCapacity * 2; elementData = Arrays.copyOf(elementData, newCapacity); } // 특정 인덱스 값 조회 // Object -> E 변환 @SuppressWarnings("unchecked") public E get(int index) { return (E) elementData[index]; } // 특정 인덱스 수정 public E set(int index, E element) { E oldValue = get(index); elementData[index] = element; return oldValue; } // 검색 public int indexOf(E o) { for (int i = 0; i < size; i++) { if (o.equals(elementData[i])) { return i; } } return -1; } public String toString(){ return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" + size + ", capacity=" + elementData.length; } }

public static void main(String[] args) { collection.array.MyArrayListV4<String> stringList = new collection.array.MyArrayListV4<>(); stringList.add("a"); stringList.add("b"); stringList.add("c"); String string = stringList.get(0); System.out.println("string = " + string); collection.array.MyArrayListV4<Integer> intList = new collection.array.MyArrayListV4<>(); intList.add(1); intList.add(2); intList.add(3); Integer integer = intList.get(0); System.out.println("integer = " + integer); }

public class MyLinkedListV3<E> { // Node 변수 private Node<E> first; private int size = 0; // 추가 public void add(E e) { Node<E> newNode = new Node(e); if (first == null) { first = newNode; }else { Node<E> lastNode = getLastNode(); lastNode.next = newNode; } size++; } // 추가 index public void add(int index, E e) { Node<E> newNode = new Node<>(e); if (index == 0) { newNode.next = first; first = newNode; }else{ Node<E> prev = getNode(index - 1); newNode.next = prev.next; prev.next = newNode; } size++; } // 제거 public E remove(int index) { Node<E> removeNode = getNode(index); E removedItem = removeNode.item; if (index == 0) { first = removeNode.next; }else{ Node<E> prev = getNode(index - 1); prev.next = removeNode.next; } removeNode.item = null; removeNode.next = null; size--; return removedItem; } // 수정 public E set(int index, E element) { Node<E> x = getNode(index); E oldValue = x.item; x.item = element; return oldValue; } // 인덱스 조회 public E get(int index) { Node<E> node = getNode(index); return node.item; } // 특정 값 검색 public int indexOf(E o) { int index = 0; for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { return index; } index++; } return -1; } public int size(){ return size; } // 마지막 노드 조회 private Node<E> getLastNode() { Node<E> x = first; while (x.next != null) { x = x.next; } return x; } // index 노드 조회 private Node<E> getNode(int index) { Node<E> x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } // 노드 중첩 클래스 private static class Node<E>{ E item; Node<E> next; public Node(E item) { this.item = item; } @Override public String toString() { StringBuilder sb = new StringBuilder(); Node<E> x = this; sb.append("["); while (x != null) { sb.append(x.item); if (x.next != null) { sb.append("->"); } x = x.next; } sb.append("]"); return sb.toString(); } } }

public static void main(String[] args) { int size = 100_000; int loop = 10_000; // ArrayList System.out.println("===ArrayList 추가==="); addFirst(new ArrayList<>(), size); addMid(new ArrayList<>(), size); ArrayList<Integer> arrayList = new ArrayList<>(); addLast(arrayList, size); System.out.println("===ArrayList 조회==="); getIndex(arrayList, loop, 0); getIndex(arrayList, loop, size /2); getIndex(arrayList, loop, size -1); System.out.println("===ArrayList 검색==="); search(arrayList, loop, 0); search(arrayList, loop, size /2); search(arrayList, loop, size -1); // LinkedList System.out.println("===LinkedList 추가==="); addFirst(new LinkedList<>(), size); addMid(new LinkedList<>(), size); LinkedList<Integer> linkedList = new LinkedList<>(); addLast(linkedList, size); System.out.println("===LinkedList 조회==="); getIndex(linkedList, loop, 0); getIndex(linkedList, loop, size /2); getIndex(linkedList, loop, size -1); System.out.println("===LinkedList 검색==="); search(linkedList, loop, 0); search(linkedList, loop, size /2); search(linkedList, loop, size -1); // List.of List<Integer> immutableList = createImmutableList(size); System.out.println("===List.of 조회==="); getIndex(immutableList, loop, 0); getIndex(immutableList, loop, size / 2); getIndex(immutableList, loop, size - 1); System.out.println("===List.of 검색==="); search(immutableList, loop, 0); search(immutableList, loop, size / 2); search(immutableList, loop, size - 1); } private static List<Integer> createImmutableList(int size) { Integer[] array = new Integer[size]; for (int i = 0; i < size; i++) { array[i] = i; } return List.of(array); } private static void addFirst(List<Integer> list, int size) { long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.add(0, i); } long endTime = System.currentTimeMillis(); System.out.println("앞에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms"); } private static void addMid(List<Integer> list, int size) { long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.add(i / 2, i); } long endTime = System.currentTimeMillis(); System.out.println("중간에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms"); } private static void addLast(List<Integer> list, int size) { long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.add(i); } long endTime = System.currentTimeMillis(); System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms"); } // loop 만큼 index 조회 private static void getIndex(List<Integer> list, int loop, int index) { long startTime = System.currentTimeMillis(); for (int i = 0; i < loop; i++) { list.get(index); } long endTime = System.currentTimeMillis(); System.out.println("index: " + index + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms"); } // loop 만큼 findValue 검색 private static void search(List<Integer> list, int loop, int findValue) { long startTime = System.currentTimeMillis(); for (int i = 0; i < loop; i++) { list.indexOf(findValue); } long endTime = System.currentTimeMillis(); System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms"); }

public class BatchProcessor { private final MyList<Integer> list; public BatchProcessor(MyList<Integer> list) { this.list = list; // 구체타입에 의존하지 않음 } public void logic(int size) { // 로직 수행 } }

public static void main(String[] args) { MyArrayList<Integer> list1 = new MyArrayList<>(); BatchProcessor process1 = new BatchProcessor(list1); process1.logic(100_000); MyLinkedList<Integer> list2 = new MyLinkedList<>(); BatchProcessor process2 = new BatchProcessor(list2); process2.logic(100_000); }

public interface MyList<T> { void add(T element); T get(int index); int size(); } public class MyArrayList<T> implements MyList<T> { // 구현 코드 } public class MyLinkedList<T> implements MyList<T> { // 구현 코드 } public class BatchProcessor { private final MyList<Integer> list; public BatchProcessor(MyList<Integer> list) { this.list = list; } public void logic(int size) { // 로직 수행 } }

public interface MyList<T> { void add(T element); T get(int index); int size(); } public class MyArrayList<T> implements MyList<T> { // 구현 코드 } public class MyLinkedList<T> implements MyList<T> { // 구현 코드 } public class BatchProcessor { private final MyList<Integer> list; public BatchProcessor(MyList<Integer> list) { this.list = list; } public void logic(int size) { // 로직 수행 } }