[자료구조] 배열 (Array)

두번째로 알아 볼 자료구조는 배열이다.

 

앞서 공부했던 리스트와 마찬가지로 많이 사용했던 자료구조인데 크기를 지정해야한다는 것 외에 아는 내용이 없다

이번에 어떤 자료 구조인지 한번 공부해 보겠다.

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

배열은 데이터를 한 열로 연속해서 정렬하는 데이터 구조이다.

리스트와 달리 데이터에 접근할 때는 편리하지만, 추가하거나 삭제하려면 시간이 오래걸린다.

 

배열 개념도

데이터는 메모리의 연속된 영역에 순차적으로 저장된다.

a는 배열의 이름이고, 그 뒤 [] 안에 있는 숫자가 몇 번째 인지를 의미한다. 이를 인덱스라고 하며 0부터 시작한다.

a[1]은 배열 a의 2번째 항목이라는 뜻이다.

 

데이터 접근

연속된 영역에 저장되기 때문에 메모리의 주소, 즉 메모리의 위치는 인덱스를 바탕으로 계산할 수 있고, 각 데이터에 직접 접근할 수 있다. 이를 랜덤 접근이라 한다.

 

랜덤 접근

예를 들어 Yellow에 접근하고 싶다면 a[2]로 바로 직접 접근할 수 있다.

 

데이터 추가

배열의 단점은 데이터를 추가하거나 삭제할 때 비용이 많이 발생한다.

Green을 두번째 위치인 a[1]에 추가하겠다.

 

데이터 추가1

먼저 배열의 마지막에 공간인 a[3]을 먼저 확보 한다.

 

데이터 추가2

그다음 Yellow를 a[3]으로 한칸 보내고, 다음 Blue를 a[2]로 보낸 다음에야 Green을 a[1]에 추가할 수 있다.

 

추가 완료

 

데이터 삭제

이번엔 다시 Green을 삭제해 보겠다

 

데이터 삭제1

먼저 Green을 a[1]에서 삭제한다.

 

데이터 삭제2

데이터 추가 때와 마찬가지로 Blue 먼저 한칸 옮기고 다음 Yellow를 한칸 옮긴다.

 

데이터 삭제 완료

마지막으로 비워진 a[3]을 삭제하면 삭제 완료가 된다.

 

⏱️ 시간복잡도

배열에 저장된 데이터의 개수가 n개라면

데이터에 접근할 때는 인덱스를 통해 바로 접근하면 되기 때문에 시간복잡도는 O(1)이 된다.

데이터를 추가하거나 삭제할 때 젤앞의 데이터를 추가하거나 삭제할때 n개의 데이터가 한번씩 움직여야 하기 때문에 O(n)이 된다.

---

📌 추가 내용

이전의 리스트와 오늘의 배열을 공부하면서 생긴 의문이 있다.

평소 코딩을 할때 리스트를 사용하면 분명 index를 통해 접근을 했는데 지금 보고있는 책은 index는 배열에만 있는 것 처럼 알려준다.

 

그래서 한번 알아보기로했다. 최근 공부하고있는 언어는 C#이기 때문에 C#의 문법으로 공부를 진행했다.

 

우선 배열(Array)은 C#에서 위의 공부했던 내용과 동일한 의미로 쓰이는 것 같다.

대신 크기가 고정적이다.

int[] intArr = new int[3]{}; // 크기가 3인 배열 생성

 

하지만 리스트의 경우는 List, ArrayList, LinkedList 등 다양한 자료구조가 있었는데

이전에 배운 리스트의 개념은 LinkedList에 해당되는 내용이다.

LinkedList<string> list = new LinkedList<string>();

 

다음이 문제인데..

List와 ArrayList이다.

일단 둘의 차이점은 데이터를 담을때 같은 자료형인가 아닌가의 차이인데 그건 다음에 기회가 되면 자세하게 포스팅해보겠다.

 

다시 자료구조 이야기를 하자면 List와 ArrayList는 리스트와 배열의 특징을 모두 가지고 있다.

인덱스를 가지고 있으면서 포인터로 연결되어있다. 그래서 성능도 그 두개의 중간지점이다.

 

LinkedList와 비교하면 항목에 접근할땐 인덱스를 통해 빠르게 가능하지만 데이터 추가/삭제가 늦고

Array와 비교하면 데이터 추가/삭제는 빠르지만 항목에 접근할땐 늦다는 특징있다.

ArrayList item = new ArrayList();

List list = new List();

 

💡정리

정해진 크기가 있으며 데이터의 변경보단 데이터를 검색하는 경우가 많을 경우는 Array

정해진 크기가 없고 데이터 변경이 자주 일어나지만 데이터를 검색할 경우가 많이 없다면 LinkedList

정해진 크기가 없고 데이터 변경과 검색 둘다 빈번하면 중간인 List

List와 같은 조건이지만 다양한 데이터 타입이 함께 들어가야 한다면 ArrayList 를 사용해야한다.

 

혹시 틀린내용이 있다면 댓글로 알려주세요 !!

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

C# ArrayList와 List 사용방법 및 차이점 : 개발자 소믈리에 블로그  https://bm4904.tistory.com/60

[C# 기초] #18.연결 리스트(Linked List)란? : 극꼼이 이야기 (GG_Tales) https://geukggom.tistory.com/160

[c#] list, array, arraylist의 차이? : my organized clipboard https://dev-yeon.tistory.com/8