Array

Q.Array는 어떠한 자료구조인가

---

💡 Array
연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다

Linked List와의 차이점

Array와 Linked List의 가장 큰 차이점은 메모리에 저장되는 방식과
이에 따른 operation(삽입/삭제/조회)등의 연산 속도가 달라지게 된다

---

Array의 데이터들은 어떻게 저장되는지 알아보자

const array = [1, 2, 3, 4] 

여기서 기억해야 될 포인트는 2개이다

1. DATA의 주소값은 할당된 주소중 가장 첫번째 값이라는것이다

   예를들어 1의 주소값은 0X4AF55번이 되는 것 이며

   2의 주소값은 0X4AF59번이 되는 것 이다

   추가적으로 현재 한 데이터는 4Byte씩 차지하고 있음을 알 수 있다

2. 배열은 메모리에 저장이 될 경우 연속적으로 저장이 된다

---

Array 특징

• Array 특징

  • 고정된 저장 공간(fixed-size)
  • 순차적인 데이터 저장(order)

• Array operation들의 시간 복잡도

  • 조회: O(1) - random access
  • 마지막 인덱스에 추가(append): O(1)
  • 마지막 인데스 삭제: O(1)
  • 삽입(inset): O(n)
  • 삭제(delete): O(n)
  • 탐색(search): O(n)

💡 radon access란?

1~4번째 index를 전부 조회하지 않고 연속적으로 저장된 것을 알기 때문에
(첫번째 index 주소값 + 4x3)의 공식을 이용하여 해당 index를 조회한다
그리고 이러한점을 radom acces라고 한다

💡 삽입/삭제 O(n)의 원리

Array에 무엇을 insert혹은 delete하기 위해서는
해당 데이터를 제외한 나머지 데이터를 뒤로 밀거나 땡겨야 된다
그렇기 때문에 O(데이터의 개수)의 시간 복잡도가 형성이 되는 것

💡 Array탐색의 원리

탐색은 조회와 다른 방식으로 4라는 데이터를 조회하기 위해서는
일일이 array를 순회할수 밖에 없음 따라서 O(n)의 복잡도가 형성된다

---

Array의 장단점

Array의 장점은 조회와 append가 빠르다는 것이다.
따라서 조회를 자주 해야되는 작업에는 Array의 구조가 많이 사용된다

반면에 Array의 단점은 fixed-size 특성상 선언시 Array의 크기를
미리 정해야 된다는 것 이는 메모리의 낭비, overhead가 발생할 수 있다

💡 overhead

오버헤드란 프로그램의 실행흐름에서 나타나는 현상중 하나로 예를 들어 , 프로그램의 실행흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때 , 추가적으로 시간,메모리,자원이 사용되는 현상.

한마디로 정의하자면, 오버 헤드는 특정 기능을 수행하는데 드는 간접적인 시간, 메모리 등 자원을 말한다.

예를 들어보자 배열의 크기를 100으로 잡아놨는데 데이터가 10개만 들어온다면 90만큼의 오버헤드가 발생한다

반대로 사이즈를 100으로 잡아놨는데 101이 들어온다면 200크기의 배열을 다시 생성후 데이터를 옮겨주어야 한다 이러한 추가작업을 오버헤드가 발생한다 한다