array-vs-arraylist-vs-linkedlist.md

Array vs ArrayList vs LinkedList 차이

출처 : https://gyoogle.dev/blog/computer-science/data-structure/Array%20vs%20ArrayList%20vs%20LinkedList.html

1. tmi 정리하는 이유

오늘 스터디 하는 데 다른 팀원분들을 얘기해준 것을 바탕으로 이해한 것과 찾아본 거 기반으로 좀 더 정리해야 할 것 같아서 정리함 + 8/17 수업시간 정리 내용 추가

2. Array(배열)

1. 선언할 때 크기와 데이터 타입을 지정해야 한다.

int arr[10];
String arr[5];

int[] myArray = new int[10];

2. 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다.
3. 데이터 크기가 정해져 있는 경우 메모리 관리에 용이

🍁 단점

1. 정적 할당(static allocation) : 고정된 크기의 데이터 구조로 선언 할 때 크기를 지정하며, 한 번 생성된 배열의 크기를 변경하는 것은 어렵다.
2. 배열의 크기를 변경하거나 요소를 추가하거나 삭제하는 것은 번거롭다. 왜냐하면 원래값을 밀어내고 해당 INDEX에 덮어씌워야 하기 때문이다.

3. ArrayList

List는 array처럼 크기를 정해주지 않아도 되기 때문에 크기의 문제인 것을 해결하기 위해서 나온 것으로 array에서는 index가 중요했다면, List에서는 순서가 중요하다.

1. ArrayList는 크기가 동적으로 확장되는 배열의 구현체로 요소를 추가하거나 삭제해도 내부적으로 크기가 자동으로 조절된다.
2. ArrayList는 객체에 저장하며, 객체 추가/삭제에 용이하도록 구현되어 있다.
3. ArrayList는 내부적으로 배열로 구현되지만, 크기가 동적으로 확장되므로 배열의 크기 제한 극복 가능
4. Java의 제네릭(Generic) 기능을 이용하면 ArrayList의 타입을 미리 지정하여 사용함으로써 타입 안정성을 확보

🍁 특징

1. 연속적인 데이터의 리스트(중간에 빈 공간이 있으면 안된다.)
2. ArrayList 클래스는 내부적으로 Object[] 배열을 이용하여 요소를 저장
3. 배열을 이용하기 때문에 인덱스를 이용해서 요소에 빠르게 접근 가능
4. 데이터의 적재량(Capacity)에 따라 가변적으로 공간을 늘리거나 줄일 수 있다.

🍁 단점

1. 중간에 데이터를 리스트 중간에 삽입/삭제 시, 시간이 오래걸리는 단점이 존재한다. (더하거나 뺄때마다 줄줄이 당겨지거나 밀려날 때 진행되는 연산이 추가, 메모리도 낭비..) 빈 공간이 생기지 않도록 인덱스를 조정해야 하는 과정이 필요하며 동작이 느리다.
2. 배열과 마찬가지로 동일한 타입의 요소를 저장하는데 사용하기 때문에 한 번 생성한 ArrayList는 그 내부의 요소 타입 변경하기는 어렵다.
3. 조회 기능에 적합한 데이터 구조

import java.util.ArrayList;

// ArrayList 생성
ArrayList<Integer> myList = new ArrayList<>();

// 요소 추가
myList.add(10);
myList.add(20);

// 요소 접근
int element = myList.get(0);

// 요소 삭제
myList.remove(0);

4. LinkedList

연결리스트에는 단일, 다중 등 여러가지가 존재한다. 종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식

1. 이런 방식을 활용하면서, 데이터의 중간에 삽입 및 삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.
2. 이렇게만 보면 가장 좋은 방법 같아보이지만, List의 k번째 값을 찾아라에서는 비효율적

🍁 단점

1. array나 arrayList에서 index를 갖고 있기 때문에 검색이 빠르지만, LinkedList는 처음부터 살펴봐야하므로(순차) 검색에 있어서는 시간이 더 걸린다는 단점
2. 상황에 맞게 하는 것이 좋음

5. 전체 비교 요약

🍁 크기 제한

배열: 고정 크기, 변경이 어려움. ArrayList: 크기 동적 조절 가능. Linked List: 크기 동적 조절 가능.

🍁요소 추가/삭제

배열: 요소 추가/삭제에 제약이 있음. ArrayList: 요소 추가/삭제 용이. Linked List: 요소 추가/삭제 용이 (특히 중간에 삽입/삭제).

🍁 검색 속도

배열: 인덱스를 통한 빠른 접근 가능. ArrayList: 인덱스를 통한 빠른 접근 가능. (검색은 배열과 유사) Linked List: 검색 속도가 배열, ArrayList에 비해 느림.

🍁 메모리 사용

배열: 연속된 메모리에 저장. ArrayList: 내부적으로 배열 사용, 크기 조절 가능. Linked List: 각 요소가 노드로 연결되어 메모리 공간 더 사용.

🍁 사용 사례

배열: 크기 변경이 거의 없는 경우, 빠른 인덱스 접근이 중요한 경우. ArrayList: 크기 변경이 필요한 경우, 빠른 인덱스 접근이 중요한 경우. Linked List: 요소의 추가/삭제가 빈번한 경우.

6. 참고

8/23 국비에서 테스트 보다가 놓친 부분인 것 같아 추가함

🍁 모든 리스트는 먼저 들어온 데이터가 제일 먼저 나간다라는 말은 맞는 말일까?

일단 답은 NO이다

1. ArrayList

• 내부적으로 배열을 사용하여 데이터를 저장한다.
• 데이터가 순차적으로 저장되며, 인덱스로 접근할 수 있다.
• 이 때문에 ArrayList에서 데이터를 삭제하면 그 다음 인덱스에 있던 데이터가 앞으로 당겨진다.
• 따라서 "먼저 들어온 데이터가 제일 먼저 나간다"는 것은 삭제된 데이터가 있더라도 해당 위치에 null 또는 다른 값이 들어있는 채로 남아있게 된다.

2. LinkedList

• 각 데이터는 이전 데이터와 다음 데이터의 참조를 가지고 있다.
• 따라서 데이터를 추가하거나 삭제할 때 이전 데이터와 다음 데이터의 참조만 변경되므로, "먼저 들어온 데이터가 제일 먼저 나간다"는 규칙이 일반적으로 유지

따라서 "모든 리스트는 먼저 들어온 데이터가 제일 먼저 나간다"는 설명은 ArrayList와 같은 배열 기반 리스트에서는 정확하지 않을 수 있다.

🍁 LinkedList에도 인덱스는 있다.

1. LinkedList도 각 요소에 인덱스가 있다. 하지만 ArrayList와는 다르게 LinkedList의** 인덱스로 직접적인 접근은 성능상의 이유로 권장되지 않는다.**
2. LinkedList는 각 요소가 다음 요소와 이전 요소에 대한 참조만을 가지고 있기 때문에, 원하는 위치로 바로 접근하려면 **처음부터 순차적으로 찾아가야 한다. **반면에 ArrayList는 내부적으로 배열을 사용하고 인덱스로 직접 접근이 가능하기 때문에 빠른 접근이 가능하다.

7. 회고

스터디에서 좋은 점은 내가 놓친 부분 한번 더 정리 가능하다는 것이다. 화이팅