Array VS ArrayList VS LinkedList

코난·2023년 10월 8일

CS 면접 정리

목록 보기

2/67

Array

Array의 특징

논리적 저장 순서와 물리적 저장 순서가 일치함
인덱스로 해당 원소에 접근 가능
random access 가능
삭제 또는 삽입 과정에서는 시간 복잡도가 커짐
선언시 크기로 크기 고정
같은 타입 데이터를 여러개 나열한 선형 자료구조

Array 사용이 유리한 상황

데이터 개수가 확실하게 저장되어 있을 때
삽입/삭제 작업이 적을때
배열에 저장된 데이터를 검색하는 작업이 많을 때

배열 회전 프로그램

기본 회전 프로그램

<새로운 배열을 사용하는 경우>

public static void l_rotation(int arr[], int count) {
	int[] newArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
    	newArr[(arr.length - (count - i)) % arr.length] = arr[i];
    }
    arr = newArr;
}

<새로운 배열을 사용하지 않는 경우>

public static void l_rotations(int arr[], int count) {
	for (int i = 0; i < count; i++) {
    	int temp = arr[0];
        for (int j = 0; j < arr.length - 1; j++) {
        	arr[j] = arr[j + 1];
        }
        arr[j] = temp;
    }
}

temp 변수를 활용하여 첫번째 인덱스 값을 저장, arr[n]값을 arr[n - 1]에 넣어주고, arr[n]에는 temp 값을 넣어주면 완성!

저글링 알고리즘

최대공약수 gcd를 이용하여 집합을 나누고, 여러 요소를 한꺼번에 이동시키는 알고리즘

public static int gcd(int a, int b) {
	if (b == 0)
    	return a;
    else
    	return gcd(b, a % b);
}
public static void l_rotations(int arr[], int count) {
	for (int i = 0; i < gcd(count, arr.length); i++) {
    	int temp = arr[i];
        int j = i;
        while (1) {
        	int k = j + count;
            if (k >= arr.length)
            	k = k - arr.length;
            if (k == 1)
            	break;
            arr[j] = arr[k];
            j = k;
        }
        arr[j] = temp;
    }
}

역전 알고리즘

reverse를 이용하여 회전하는 알고리즘

public static void reverseArr(int arr[], int start, int end) {
	while (start < end) {
    	int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
public static void l_rotations(int arr[], int count) {
	reverseArr(arr, 0, count - 1);
    reverseArr(arr, count, arr.length - 1);
    reverseArr(arr, 0, arr.length - 1);
}

i * arr[i]의 sum 최대값

arr[i]의 전체합과 i x arr[i]의 전체합을 저장할 변수 선언
가장 큰 sum 값을 최종적으로 저장할 변수 선언
배열을 회전시키면서 i x arr[i]의 전체합 값을 저장하고, 가장 큰 값을 저장해서 출력

public static int maxVal(int arr[]) {
	int arrSum = 0; //arr 전체합
    int curSum = 0; //i*arr[i] 전체합
    
    for (int i = 0; i < arr.length; i++) {
    	arrSum = arrSum + arr[i];
        curSum = curSum + (i * arr[i]);
    } 
    int maxSum = curSum;
    for (int i = 1; i < arr.length; i++) {
    	curSum = curSum + arrSum - arr.length * arr[arr.length - i];
        if (curSum > maxSum)
        	max = curSum;
    }
    return maxSum;
}

arr[i] = i로 재배열

arr[i] = i가 없으면 -1로 채움
arr[i]가 -1이 아니고 arr[i]이 i가 아닐때가 우선 조건
해당 arr[i]값을 변수 x에 저장해두고 arr[x] 값이 -1이 아니고 x가 아닌 동안 반복
arr[x]값을 변수 y에 저장해두고 arr[x]에 위에서 저장해둔 x값을 대입, x값에는 y값을 대입
arr[x]에 x값을 넣어두고 만약 arr[i]가 i가 아니라면 arr[i]에 -1 대입

public static int fix(int arr[]) {
	for (int i = 0; i < arr.length; i++) {
    	if (arr[i] != -1 && arr[i] != i) {
        	int x = arr[i];
            while (arr[x] != -1 && arr[x] != x) {
            	int y = arr[x];
                arr[x] = x;
                x = y;
            }
            arr[x] = x;
            if (arr[i] != i) {
            	arr[i] = -1;
            }
        }
    }
}

LinkedList

LinkedList란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
각 노드는 다음 노드를 가리키는 포인터를 포함함
다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가짐
각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가짐

LinkedList 사용 이유

배열의 한계를 극복하기 위해 사용하게 되었음

배열의 단점
- 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함
- 새로운 요소를 삽입하는 것은 비용이 많이 듦

LinkedList의 장점

동적 크기
삽입/삭제 용이

LinkedList의 단점

임의로 엑세스 허용 불가능. 첫번째 노드부터 순차적으로 요소에 엑세스해야함(이진 검색 수행 불가능 -> 검색 느림)
포인터의 여분의 메모리 공간이 목록의 각 요소에 필요

LinkedList 사용법(JAVA)

import java.util.LinkedList;

LinkedList<Integer> i = new LinkedList<Integer>();

//값 추가
i.add(1);
i.add(2);

//n번째에 값 추가
i.add(1, 4); //index, 넣을 값

//값 수정
i.set(1, 3); //index, 바꿀 값

//첫번째 데이터 삭제
i.removeFirst();

//마지막 데이터 삭제
i.removeLast();

//n번째 데이터 삭제
i.remove(0); //명시하지 않으면 첫번째 데이터 삭제

//모든 데이터 삭제
i.clear();

//LinkedList의 크기
i.size();

ArrayList

ArrayList란?

연속적인 데이터의 리스트
인덱스를 이용하여 요소에 빠르게 접근 가능
배열과 달리 가변적으로 공간 늘리거나 줄이기 가능
삽입/삭제 동작 느림
검색 속도 빠름
객체로 데이터를 다루기에 적은양의 데이터만 사용할 경우 배열에 비해 차지하는 메모리가 커짐

ArrayList 사용법(JAVA)

import java.util.ArrayList;

ArrayList<Integer> i = new ArrayList<>(10);
ArrayList<Integer> i2 = new ArrayList<>(10);

//값 추가
i.add(1);
i.add(2);
i2.add(3);
i2.add(4);

//i에 i2의 데이터 추가
i.addAll(i2);

//n번째에 값 추가
i.add(2, 5);

//n번째 값 수정
i.set(1, 1); //index, 바꿀 값

//n번째 데이터 삭제
i.remove(2);

//모든 데이터 삭제
i.clear();

//값 있는지 검색
i.contains(3);

//값 있는지 검색하고 index 반환(없으면 -1)
i.indexOf(3);

//값 있는지 뒤에서부터 검색하고 index 반환(없으면 -1)
i.lastIndexOf(3);

//n번째 요소 얻기
i.get(3);

//부분 배열 반환
i.subList(0, 3); //0부터 3까지 인덱스의 값 list 형태로 반환

//ArrayList 크기
i.size();